Near-ideal model selection by _1 minimization

DOI10.1214/08-AOS653MaRDI QIDQ834335zbMATH OpenOpenAlexFDO

Authors Emmanuel J. Candès, Y. Plan

Publication date 19 August 2009

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.0345

zbMATH Keywords

compressed sensingeigenvalues of random matricesincoherencelassomodel selectionoracle inequalities

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08) Estimation in multivariate analysis (62H12) Linear regression; mixed models (62J05) Quadratic programming (90C20) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the fundamental problem of estimating the mean of a vector $$, where $X$ is an $nimesp$ 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 $$ 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 $$ 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 $$ 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.

Recommendations

• Model selection and sharp asymptotic minimaxity
• Minimal penalties for Gaussian model selection
• Model Selection when There is "Minimal" Prior Information
• Model selection: a Lagrange optimization approach
• Model selection for regularized least-squares algorithm in learning theory
• Nearly unbiased variable selection under minimax concave penalty
• scientific article; zbMATH DE number 2212144
• Approximate Laplace Approximations for Scalable Model Selection
• The Lasso as an \(\ell _{1}\)-ball model selection procedure
• scientific article; zbMATH DE number 5356146

Cites work

• A new look at the statistical model identification
• Adaptive Lasso for sparse high-dimensional regression models
• Aggregation for Gaussian regression
• Atomic Decomposition by Basis Pursuit
• Best subset selection, persistence in high-dimensional statistical learning and optimization under l₁ constraint
• Estimating the dimension of a model
• Gaussian model selection
• High-dimensional graphs and variable selection with the Lasso
• scientific article; zbMATH DE number 5957408 (Why is no real title available?)
• scientific article; zbMATH DE number 1465030 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Lasso-type recovery of sparse representations for high-dimensional data
• Linear Inversion of Band-Limited Reflection Seismograms
• Neural networks: A review from a statistical perspective. With comments and a rejoinder by the authors
• New tight frames of curvelets and optimal representations of objects with piecewise C² singularities
• Norms of random submatrices and sparse approximation
• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• Quantitative robust uncertainty principles and optimally sparse decompositions
• Risk bounds for model selection via penalization
• Simultaneous analysis of Lasso and Dantzig selector
• Some Comments on C P
• Some sharp performance bounds for least squares regression with L₁ regularization
• Sparse Approximate Solutions to Linear Systems
• Sparsity oracle inequalities for the Lasso
• Stable recovery of sparse overcomplete representations in the presence of noise
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• The risk inflation criterion for multiple regression

Cited in

(91)

• LOL selection in high dimension
• False discoveries occur early on the Lasso path
• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• On the sensitivity of the Lasso to the number of predictor variables
• Variable selection with Hamming loss
• Space alternating penalized Kullback proximal point algorithms for maximizing likelihood with nondifferentiable penalty
• \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
• Compressed sensing and matrix completion with constant proportion of corruptions
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• The Lasso problem and uniqueness
• Honest variable selection in linear and logistic regression models via \(\ell _{1}\) and \(\ell _{1}+\ell _{2}\) penalization
• On the conditions used to prove oracle results for the Lasso
• The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
• Least squares after model selection in high-dimensional sparse models
• The generalized Lasso problem and uniqueness
• Sampling from non-smooth distributions through Langevin diffusion
• The sparsity of LASSO-type minimizers
• Inadequacy of linear methods for minimal sensor placement and feature selection in nonlinear systems: a new approach using secants
• Adaptive decomposition-based evolutionary approach for multiobjective sparse reconstruction
• Statistical analysis of sparse approximate factor models
• A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Rejoinder: ``A significance test for the lasso
• Pivotal estimation via square-root lasso in nonparametric regression
• A global homogeneity test for high-dimensional linear regression
• Prediction error bounds for linear regression with the TREX
• Sharp oracle inequalities for low-complexity priors
• Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation
• Refined analysis of sparse MIMO radar
• High-dimensional change-point estimation: combining filtering with convex optimization
• Error bounds for compressed sensing algorithms with group sparsity: A unified approach
• The degrees of freedom of partly smooth regularizers
• Estimation and variable selection with exponential weights
• Concentration of \(S\)-largest mutilated vectors with \(\ell_p\)-quasinorm for \(0<p\leq 1\) and its applications
• Consistency of \(\ell_1\) recovery from noisy deterministic measurements
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• A resampling approach for confidence intervals in linear time-series models after model selection
• Randomized pick-freeze for sparse Sobol indices estimation in high dimension
• Best subset selection via a modern optimization lens
• High-dimensional variable selection with sparse random projections: measurement sparsity and statistical efficiency
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Adventures in compressive sensing based MIMO radar
• Discrete a priori bounds for the detection of corrupted PDE solutions in exascale computations
• A new approach to select the best subset of predictors in linear regression modelling: bi-objective mixed integer linear programming
• Conjugate gradient acceleration of iteratively re-weighted least squares methods
• Deterministic convolutional compressed sensing matrices
• An introduction to compressed sensing
• Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
• Phase transition in limiting distributions of coherence of high-dimensional random matrices
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Two are better than one: fundamental parameters of frame coherence
• Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
• UPS delivers optimal phase diagram in high-dimensional variable selection
• Sparse signal recovery via non-convex optimization and overcomplete dictionaries
• The accessible Lasso models
• Adapting to unknown noise level in sparse deconvolution
• Short-term sparse portfolio optimization based on alternating direction method of multipliers
• Covariate assisted screening and estimation
• Normalized and standard Dantzig estimators: two approaches
• Understanding large text corpora via sparse machine learning
• Submatrices with nonuniformly selected random supports and insights into sparse approximation
• _1-penalised ordinal polytomous regression estimators with application to gene expression studies
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• Chaotic Binary Sensing Matrices
• scientific article; zbMATH DE number 6438182 (Why is no real title available?)
• Reconstructing DNA copy number by penalized estimation and imputation
• Compressed sensing with coherent and redundant dictionaries
• Combined \(\ell_1\) and greedy \(\ell_0\) penalized least squares for linear model selection
• A general theory of concave regularization for high-dimensional sparse estimation problems
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Controlling False Discovery Rate Using Gaussian Mirrors
• Decomposition of dynamical signals into jumps, oscillatory patterns, and possible outliers
• \(\ell_{1}\)-penalization for mixture regression models
• Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low
• Adaptive Dantzig density estimation
• Limiting laws of coherence of random matrices with applications to testing covariance structure and construction of compressed sensing matrices
• MuSP: a multistep screening procedure for sparse recovery
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• Regularized scalar-on-function regression analysis to assess functional association of critical physical activity window with biological age
• Portfolio selection balancing concentration and diversification
• Accelerated stochastic approximation with state-dependent noise
• The impact of contamination and correlated design on the Lasso: an average case analysis
• Analysis of sparse MIMO radar
• Group sparse optimization for learning predictive state representations
• Controlling the false discovery rate via knockoffs
• Optimal dual certificates for noise robustness bounds in compressive sensing
• High-dimensional Gaussian model selection on a Gaussian design

Describes a project that uses

Uses Software

• PDCO

This page was built for publication: Near-ideal model selection by \(\ell _{1}\) minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834335)