Precise Error Analysis of the ℓ_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∈R^n from underdetermined, noisy, linear measurements y=Ax_0 + z ∈ R^m. One standard approach is to solve the following convex program x^=arg min_x ∥y−Ax∥_2 + λ∥x∥_1, which is known as the ℓ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 σ2. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we precisely characterize the limiting behavior of the normalized squared-error ∥x^−x_0∥^2_2/σ^2. Our numerical illustrations validate our theoretical predictions.

Files

Additional details