Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing

Abstract

This paper concerns the performance of the LASSO (also knows as basis pursuit denoising) for recovering sparse signals from undersampled, randomized, noisy measurements. We consider the recovery of the signal $x_o\in {\mathbb{R}}^N$ from $n$ random and noisy linear observations $y=A{x}_o+w$, where $A$ is the measurement matrix and $w$ is the noise. The LASSO estimate is given by the solution to the optimization problem $x_o$ with ${\hat{x}}_{\lambda }=\arg {\min }_x\frac{1}{2}\Vert y-Ax{\Vert }_2^2+\lambda \Vert x{\Vert }_1$. Despite major progress in the theoretical analysis of the LASSO solution, little is known about its behavior as a function of the regularization parameter $\lambda$. In this paper we study two questions in the asymptotic setting (i.e., where $N\to \infty$, $n\to \infty$ while the ratio $n/N$ converges to a fixed number in $(0,1)$): (i) How does the size of the active set $\Vert {\hat{x}}_{\lambda }{\Vert }_0/N$ behave as a function of $\lambda$, and (ii) How does the mean square error $\Vert {\hat{x}}_{\lambda }-x_o{\Vert }_2^2/N$ behave as a function of $\lambda$? We then employ these results in a new, reliable algorithm for solving LASSO based on approximate message passing (AMP).

References in corpus (4)

• On the "degrees of freedom" of the lasso
• Universality in polytope phase transitions and message passing algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Living on the edge: Phase transitions in convex programs with random data

Cited by in corpus (8)

• ICR: Iterative Convex Refinement for Sparse Signal Recovery Using Spike and Slab Priors
• Parameterless Optimal Approximate Message Passing
• A scalable estimate of the extra-sample prediction error via approximate leave-one-out
• False Discoveries Occur Early on the Lasso Path
• Does ${\ell }_p$-minimization outperform ${\ell }_1$-minimization?
• Bayesian Optimal Approximate Message Passing to Recover Structured Sparse Signals
• Consistent Risk Estimation in Moderately High-Dimensional Linear Regression
• Enhanced Signal Recovery via Sparsity Inducing Image Priors