Precise error analysis of the LASSO

Abstract

A classical problem that arises in numerous signal processing applications asks for the reconstruction of an unknown, k-sparse signal x_0 ∈ ℝ^n from underdetermined, noisy, linear measurements y = Ax_0 + z ∈ ℝ^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