Precise Error Analysis of the $\ell_2$-LASSO

Christos Thrampoulidis, Ashkan Panahi, Daniel X. Guo, Babak HassibiarXiv 2015 · DOI · arXiv

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=Ax_0+z\in R^m$. One standard approach is to solve the following convex program $\hat x=\arg\min_x \|y-Ax\|_2 + λ\|x\|_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 $σ^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 $\|\hat x-x_0\|^2_2/σ^2$. Our numerical illustrations validate our theoretical predictions.

Introduction

In signal processing, reconstructing a sparse signal from a limited number of noisy linear measurements is a fundamental challenge. The $\ell_2$-LASSO (or square-root LASSO) is a popular convex optimization approach for this task, defined by the objective function $\|y - Ax\|_2 + \lambda \|x\|_1$. Unlike the standard LASSO, which uses a squared $\ell_2$-norm, the $\ell_2$-LASSO is particularly attractive because its optimal tuning parameter $\lambda$ is independent of the noise level $\sigma$, facilitating practical implementation.

Despite its widespread use, a precise characterization of its reconstruction error has remained elusive. Previous works typically provided order-wise bounds that lack the specificity needed for exact performance prediction. This study addresses this gap by providing an exact asymptotic formula for the Normalized Squared Error (NSE) in high-dimensional settings.

Methodology

The analysis is conducted in the "large system limit," where the signal length ($n$), number of measurements ($m$), and sparsity ($k$) grow to infinity at fixed ratios. The core theoretical framework utilizes Gordon’s Gaussian min-max theorem (GMT). This probabilistic tool enables the reduction of the complex, high-dimensional vector optimization problem into a simpler, scalar deterministic optimization.

The methodology involves two primary steps:

  1. Scalarization: Transforming the original problem into one involving a few scalar variables.
  2. Concentration: Applying the Law of Large Numbers to demonstrate that the random behavior of the Gaussian sensing matrix concentrates around a predictable deterministic value as the system size increases.

Theoretical predictions were validated using synthetic data with i.i.d. Gaussian sensing matrices, $k$-sparse signals, and Gaussian noise. Simulations were performed with dimensions $n=500$, $m=150$, and $k=20$, averaged over 20 realizations.

Results and Discussion

The primary contribution of this work is a deterministic formula (Theorem 3.1) that accurately predicts reconstruction error based on measurement rate, sparsity, and noise level. Numerical simulations show a near-perfect alignment with these theoretical predictions across various noise levels.

Theoretical vs. numerical optimal cost for the $\ell_2$-LASSO across various noise levels.

A significant finding is the "Low Noise Paradox": the Normalized Squared Error (NSE) is actually maximized in the low-noise regime ($\sigma^2 \to 0$). This implies that formulas derived for noiseless scenarios provide a conservative upper bound for error in noisier environments.

Normalized Squared Error (NSE) as a function of the regularization parameter $\lambda$, illustrating the stability threshold and the low-noise performance peak.

The results also characterize the "phase transitions" of the recovery process, identifying specific thresholds for the number of measurements $m$ required for stable recovery relative to sparsity and the regularization parameter $\lambda$. Recovery is stable only when $m$ exceeds a threshold determined by the signal's sparsity.

Conclusion

This research provides the first precise characterization of the $\ell_2$-LASSO's error behavior. While the current proof assumes Gaussian distributions for the sensing matrix and noise, the insights are expected to be universal across a broader class of distributions. Future work will focus on rigorously proving the worst-case nature of the low-noise regime and extending these results to non-Gaussian matrices.

Summary updated

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=Ax_0+z\in R^m$. One standard approach is to solve the following convex program $\hat x=\arg\min_x \|y-Ax\|_2 + λ\|x\|_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 $σ^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 $\|\hat x-x_0\|^2_2/σ^2$. Our numerical illustrations validate our theoretical predictions.
BibTeX
@misc{thrampoulidis2015precise,
  author = {Christos Thrampoulidis and Ashkan Panahi and Daniel X. Guo and Babak Hassibi},
  title = {{Precise Error Analysis of the $\textbackslash\{\}ell\_2$-LASSO}},
  year = {2015},
  eprint = {1502.04977},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.04977},
}
Figure