Near-ideal model selection by ${\ell }_1$ minimization

Abstract

We consider the fundamental problem of estimating the mean of a vector $y=X\beta +z$, where $X$ is an $n\times p$ design matrix in which one can have far more variables than observations, and $z$ is a stochastic error term--the so-called "$p>n$" setup. When $\beta$ is sparse, or, more generally, when there is a sparse subset of covariates providing a close approximation to the unknown mean vector, we ask whether or not it is possible to accurately estimate $X\beta$ using a computationally tractable algorithm. We show that, in a surprisingly wide range of situations, the lasso happens to nearly select the best subset of variables. Quantitatively speaking, we prove that solving a simple quadratic program achieves a squared error within a logarithmic factor of the ideal mean squared error that one would achieve with an oracle supplying perfect information about which variables should and should not be included in the model. Interestingly, our results describe the average performance of the lasso; that is, the performance one can expect in an vast majority of cases where $X\beta$ is a sparse or nearly sparse superposition of variables, but not in all cases. Our results are nonasymptotic and widely applicable, since they simply require that pairs of predictor variables are not too collinear.

Published in at http://dx.doi.org/10.1214/08-AOS653 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• Lasso-type recovery of sparse representations for high-dimensional data
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Best subset selection, persistence in high-dimensional statistical learning and optimization under $l_1$ constraint

Cited by in corpus (51)

• Structured Compressed Sensing: From Theory to Applications
• NESTA: A Fast and Accurate First-order Method for Sparse Recovery
• On the conditions used to prove oracle results for the Lasso
• Controlling the false discovery rate via knockoffs
• A significance test for the lasso
• Signal Recovery on Graphs: Variation Minimization
• Coherence-Based Performance Guarantees for Estimating a Sparse Vector Under Random Noise
• L1-Penalization for Mixture Regression Models
• An Overview of Enhanced Massive MIMO with Array Signal Processing Techniques
• On the Prediction Performance of the Lasso
• LDPC Codes for Compressed Sensing
• Gene Hunting with Knockoffs for Hidden Markov Models
• Information theoretic bounds for Compressed Sensing
• Pivotal estimation via square-root Lasso in nonparametric regression
• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Dynamic Updating for L1 Minimization
• Asynchronous Code-Division Random Access Using Convex Optimization
• Two are better than one: Fundamental parameters of frame coherence
• Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
• Why Gabor Frames? Two Fundamental Measures of Coherence and Their Role in Model Selection
• Peak Reduction and Clipping Mitigation by Compressive Sensing
• Joint Sensing Matrix and Sparsifying Dictionary Optimization for Tensor Compressive Sensing
• Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
• UPS delivers optimal phase diagram in high-dimensional variable selection
• Covariate assisted screening and estimation
• Sparse approximation property and stable recovery of sparse signals from noisy measurements
• Uncertainty Relations and Sparse Signal Recovery for Pairs of General Signal Sets
• The MUSIC Algorithm for Sparse Objects: A Compressed Sensing Analysis
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• A Class of Nonconvex Penalties Preserving Overall Convexity in Optimization-Based Mean Filtering
• Machine Learning Methods in the Computational Biology of Cancer
• State of the Art and Prospects of Structured Sensing Matrices in Compressed Sensing
• Reconstructing DNA copy number by penalized estimation and imputation
• Group Iterative Spectrum Thresholding for Super-Resolution Sparse Spectral Selection
• Recursive Sparse Point Process Regression with Application to Spectrotemporal Receptive Field Plasticity Analysis
• On U-Statistics and Compressed Sensing I: Non-Asymptotic Average-Case Analysis
• Restricted isometry property of random subdictionaries
• High Resolution Radar Sensing with Compressive Illumination
• Model Selection: Two Fundamental Measures of Coherence and Their Algorithmic Significance
• Accurate detection of moving targets via random sensor arrays and Kerdock codes
• Exact Localization and Superresolution with Noisy Data and Random Illumination
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• On the Sensitivity of the Lasso to the Number of Predictor Variables
• Inadequacy of Linear Methods for Minimal Sensor Placement and Feature Selection in Nonlinear Systems; a New Approach Using Secants
• Frame Coherence and Sparse Signal Processing
• Optimal Arrays for Compressed Sensing in Snapshot-Mode Radio Interferometry
• Interpretable Classification of Bacterial Raman Spectra with Knockoff Wavelets
• Convolutional Sparse Support Estimator Network (CSEN) From energy efficient support estimation to learning-aided Compressive Sensing
• Quantum Algorithms for the Pathwise Lasso
• On U-Statistics and Compressed Sensing II: Non-Asymptotic Worst-Case Analysis