Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
share
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 ∈R^N from n random and noisy linear observations y= Ax_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 x̂_λ = _x 1/2y-Ax_2^2 + λx_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 λ. In this paper we study two questions in the asymptotic setting (i.e., where N →∞, n →∞ while the ratio n/N converges to a fixed number in (0,1)): (i) How does the size of the active set x̂_λ_0/N behave as a function of λ, and (ii) How does the mean square error x̂_λ - x_o_2^2/N behave as a function of λ? We then employ these results in a new, reliable algorithm for solving LASSO based on approximate message passing (AMP).
READ FULL TEXT