The LASSO Risk for Gaussian Matrices

By Mohsen Bayati, Andrea Montanari. IEEE Transactions on Information Theory, 2010

333 citations recorded by the source corpus.

We consider the problem of learning a coefficient vector xο ∈ RN from noisy linear observation y = Axo + ∈ Rn. In many contexts (ranging from model selection to image processing), it is desirable to construct a sparse estimator x̂. In this case, a popular approach consists in solving an ℓ1-penalized least-squares problem known as the LASSO or basis pursuit denoising. For sequences of matrices A of increasing dimensions, with independent Gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. Our result is the first rigorous derivation of an explicit formula for the asymptotic mean square error of the LASSO for random instances. The proof technique is based on the analysis of AMP, a recently developed efficient algorithm, that is inspired from graphical model ideas. Simulations on real data matrices suggest that our results can be relevant in a broad array of practical applications.

Subfields: Aerospace Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/0f65f2055810d2158e874cd4fa113ab3ce9fd595

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

A modern maximum-likelihood theory for high-dimensional logistic regression (2018, methodology): “Finally, we remark that the AMP machinery has been successfully applied to study other statistical problems, including but not limited to the mean square estimation error of the Lasso [10], the tradeoff between the type I and type II errors along the Lasso path [94], power and prediction analysis of”
On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators (2018, background): “Hence these families of distributions for Xi ’s have the same covariance, but as we will see they yield estimators whose performance vary quite substantially with the distribution of λi ’s.”
SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax (2015, methodology): “This is already apparent when scanning the literature on penalized sparse estimation procedures such as the Lasso, SCAD [33], the Dantzig selector [24] and MC+ [58], see e.g. [37, 23, 59, 22, 11, 52, 55, 44, 57, 7, 29] for a highly incomplete list of references.”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “In the asymptotic case, stable signal recovery has been demonstrated for the Gaussian measurement ensemble in a regime in which the RIP does not necessarily hold [22], [4].”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, neutral): “Similarly, another class of nonconvex algorithms that have recently been proposed in the literature are iterative algorithms based on Generalized Approximate Message Passing (GAMP), see [59], [63] as well as [9], [10], [23] for some background literature on AMP.”
Robust Subspace Clustering (2013, background): “It might be possible to compute a precise relationship between λ and the expected number of true discoveries in an asymptotic regime in which the number of points and the dimension of the subspace both increase to infinity in a fixed ratio by adapting ideas from [8, 9].”
The Noise-Sensitivity Phase Transition in Compressed Sensing (2010, methodology): “We argue that the ideas developed here and in companion papers give access to a richer set of operational predictions, to efficient reconstruction algorithms (such as AMP) [14] and opens the way to rigorous work [3], [2].”
Debiasing the lasso: Optimal sample size for Gaussian designs (2015, positive): “ sequence model. A similar connection was anticipated {for instance{ in [DMM11,DJM13]. An asymptotic characterizations of the Lasso mean square error for standard Gaussian designs was rst obtained in [BM12]. However, in the present case we recover this as a corollary of a result for general Gaussian”
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, background): “Hence, a necessary condition for rejecting H 0 ,j with non-negligible probability is as stated in Section 1.”
High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification (2015, methodology): “Various regression and M-estimation problems have been studied in high dimensions using approximate message passing (Bayati and Montanari, 2012; Donoho and Montanari, 2015) as well as methods inspired by random matrix theory (Bean et al., 2013).”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, methodology): “μ=1 u′Yt,μ (St,μ)u ′ Yt,μ (st,μ)−r(t) (Q−q(t))〉 t , [17]”
Living on the edge: phase transitions in convex programs with random data (2013, background): “For the compressed sensing problem, two recent papers [12,13] provide a rigorous explanation for this coincidence.”
Orthogonal AMP (2016, methodology): “, LASSO [11]) with IID Gaussian sensing matrices [12]–[14] and SE provides a tool to predict the related performance [13].”
Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results (2013, methodology): “Our heuristic led to the formulation of a natural variational problem, which we solved in Bean et al. (2013). Interestingly, the solution of the variational problem depends in general on p/n, i.e the dimensionality of the problem. (El Karoui et al. (2012) is the long form of the paper El Karoui et a”