Lasso-type recovery of sparse representations for high-dimensional data

Abstract

The Lasso is an attractive technique for regularization and variable selection for high-dimensional data, where the number of predictor variables $p_n$ is potentially much larger than the number of samples $n$. However, it was recently discovered that the sparsity pattern of the Lasso estimator can only be asymptotically identical to the true sparsity pattern if the design matrix satisfies the so-called irrepresentable condition. The latter condition can easily be violated in the presence of highly correlated variables. Here we examine the behavior of the Lasso estimators if the irrepresentable condition is relaxed. Even though the Lasso cannot recover the correct sparsity pattern, we show that the estimator is still consistent in the ${\ell }_2$-norm sense for fixed designs under conditions on (a) the number $s_n$ of nonzero components of the vector ${\beta }_n$ and (b) the minimal singular values of design matrices that are induced by selecting small subsets of variables. Furthermore, a rate of convergence result is obtained on the ${\ell }_2$ error with an appropriate choice of the smoothing parameter. The rate is shown to be optimal under the condition of bounded maximal and minimal sparse eigenvalues. Our results imply that, with high probability, all important variables are selected. The set of selected variables is a meaningful reduction on the original set of variables. Finally, our results are illustrated with the detection of closely adjacent frequencies, a problem encountered in astrophysics.

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

References in corpus (20)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• LISA Data Analysis using MCMC methods
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• LISA source confusion: identification and characterization of signals

Cited by in corpus (59)

• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• On asymptotically optimal confidence regions and tests for high-dimensional models
• On the conditions used to prove oracle results for the Lasso
• Least squares after model selection in high-dimensional sparse models
• Variable selection in nonparametric additive models
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• High-dimensional additive modeling
• High-dimensional generalized linear models and the lasso
• High-dimensional variable selection
• Support union recovery in high-dimensional multivariate regression
• Near-ideal model selection by ${\ell }_1$ minimization
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Statistical significance in high-dimensional linear models
• Least angle and ${\ell }_1$ penalized regression: A review
• Information-Based Optimal Subdata Selection for Big Data Linear Regression
• L1-Penalization for Mixture Regression Models
• Correlated variables in regression: clustering and sparse estimation
• Valid Post-Selection and Post-Regularization Inference: An Elementary, General Approach
• Regularization for Cox's proportional hazards model with NP-dimensionality
• Calibrating nonconvex penalized regression in ultra-high dimension
• Estimation for High-Dimensional Linear Mixed-Effects Models Using ${\ell }_1$-Penalization
• Pivotal estimation via square-root Lasso in nonparametric regression
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• The Lasso for High-Dimensional Regression with a Possible Change-Point
• Oracle inequalities for the lasso in the Cox model
• A new perspective on least squares under convex constraint
• High-dimensional regression adjustments in randomized experiments
• Convex Biclustering
• Honest variable selection in linear and logistic regression models via ${\ell }_1$ and ${\ell }_1+{\ell }_2$ penalization
• Rates of convergence of the Adaptive LASSO estimators to the Oracle distribution and higher order refinements by the bootstrap
• Rejoinder: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Developing a large scale population screening tool for the assessment of Parkinson's disease using telephone-quality voice
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• Estimation in high-dimensional linear models with deterministic design matrices
• Minimax-optimal nonparametric regression in high dimensions
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• Regression on manifolds: Estimation of the exterior derivative
• Selection of variables and dimension reduction in high-dimensional non-parametric regression
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• Sparse regression algorithm for activity estimation in $\gamma$ spectrometry
• DIF Statistical Inference without Knowing Anchoring Items
• A general theory of regression adjustment for covariate-adaptive randomization: OLS, Lasso, and beyond
• PAC-Bayesian Estimation and Prediction in Sparse Additive Models
• Accuracy guarantees for L1-recovery
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Extensions of stability selection using subsamples of observations and covariates
• Monte Carlo Simulation for Lasso-Type Problems by Estimator Augmentation
• Structured Estimation in Nonparameteric Cox Model
• On the Null Space Constant for $l_p$ Minimization
• General nonexact oracle inequalities for classes with a subexponential envelope
• A review of Gaussian Markov models for conditional independence
• An efficient and robust approach to Mendelian randomization with measured pleiotropic effects in a high-dimensional setting
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• An analysis of penalized interaction models
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models