Course Information

Day/Time/Room:    Tue, 11:00am-12:50pm, CEPSR 414

Instructors:  Irina Rish and Genady Grabarnik


Sparse modeling is a quickly developing area on the intersection of statistics, machine-learning and signal processing. In statistical applications, its aim is variable selection when building predictive models. Examples include identifying a few genes most relevant to a particular disease from microarray data over thousands of genes, or finding brain areas most relevant to predicting certain mental states from fMRI data. Another application is probabilistic diagnosis of rare events, such as identifying a small number of slow links responsible for slowdowns in large-scale computer networks. Finally, one of the most prominent applications of sparse modeling is compressed sensing, a rapidly growing and extremely popular area of signal processing concerned with efficient recovery of high-dimensional sparse signals from a small number of observations.

The aim of this course is to provide an overview of the key recent developments in sparse statistical learning and compressed sensing, maintaining a balance among the following three aspects: theoretical basis for sparse modeling, algorithmic approaches, and practical applications.  We plan to cover theoretical conditions for sparse signal recovery (Restricted Isometry Property, Mutual Incoherence, Irrepresentability Conditions, etc.)  in various settings, such as noiseless and noisy, finite-sample and asymptotic cases, and discuss various bounds on sample complexity (sparsity vs. number of samples trade-offs). Besides the basic LASSO problem, we aim to cover its multiple recent extensions towards (1) other likelihoods, such as multivariate Gaussians (sparse inverse covariance problem), (2) other regularizers: Elastic Net, fused LASSO, block-norms (l1/lp) in group- and simultaneous LASSO (multi-task prediction), and (3) sparse dimensionality reduction and dictionary learning. We plan to discuss a range of popular algorithms that include greedy search methods, l1-regularized optimization, and Bayesian approaches.

Course prerequisites include basic knowledge of probability theory, statistics, optimization and linear algebra.   This course is intended for intermediate/advanced graduate students.

Course Outline

Jan 18 (week 1):               Introduction to Sparse Modeling  (slides, HW1, HW1 solutions)

Jan 25 (week 2):               Variable selection, Greedy Search and Lasso (slides)

Feb 1  (week 3):                Sparse Linear Regression: Optimization Algorithms (slides)

Feb 8,15 (weeks 4,5):      Compressed Sensing: Sparse Signal Recovery from Linear Observations (slides, HW2 - see Columbia courseworks) 

Feb 22 (week 6):               Beyond LASSO: other regularizers (slides)

Mar 1 (week 7):                 Beyond LASSO: other losses (slides) 

Mar 8 (week 8)                   Project proposals presentation and discussions

Mar 15 (week 9):               Spring Break

Mar 22 (week 10):             Guest Lecture: Structured Sparsity and Greedy Methods: Theory and Applications (slides)

Mar 29 (week 11):             Probabilistic aspects of compressed sensing

Apr 5 (week 12):                Deterministic Compressed Sensing

Apr 12 (week 13):              Matrix Factorization and Dictionary Learning (slides)

Apr 19 (week 14):              Gradient-based Sparse Optimization: Proximal Methods and Iterative Thresholding (slides)

Apr 26 (week 15):              Dantzig Selector and Asymptotic Consistency of LASSO

May 3,10 (weeks 16, 17):  Project presentations



Grading Policy

Homework:  40% of the grade

Project60% of the grade