Precise Error Analysis of the ${\ell }_2$-LASSO

Abstract

A classical problem that arises in numerous signal processing applications asks for the reconstruction of an unknown, $k$-sparse signal $x_0\in R^n$ from underdetermined, noisy, linear measurements $y=A{x}_0+z\in R^m$. One standard approach is to solve the following convex program $\hat{x}=\arg {\min }_x\Vert y-Ax{\Vert }_2+\lambda \Vert x{\Vert }_1$, which is known as the ${\ell }_2$-LASSO. We assume that the entries of the sensing matrix $A$ and of the noise vector $z$ are i.i.d Gaussian with variances $1/m$ and ${\sigma }^2$. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we \emph{precisely} characterize the limiting behavior of the normalized squared-error $\Vert \hat{x}-x_0{\Vert }_2^2/{\sigma }^2$. Our numerical illustrations validate our theoretical predictions.

in 40th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2015