Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO

Abstract

Given an unknown signal ${\mathbf{x}}_0\in {\mathbb{R}}^n$ and linear noisy measurements $\mathbf{y}=\mathbf{A}{\mathbf{x}}_0+\sigma \mathbf{v}\in {\mathbb{R}}^m$, the generalized ${\ell }_2^2$-LASSO solves $\hat{\mathbf{x}}:=\arg {\min }_{\mathbf{x}}\frac{1}{2}\Vert \mathbf{y}-\mathbf{Ax}{\Vert }_2^2+\sigma \lambda f(\mathbf{x})$. Here, $f$ is a convex regularization function (e.g. ${\ell }_1$-norm, nuclear-norm) aiming to promote the structure of ${\mathbf{x}}_0$ (e.g. sparse, low-rank), and, $\lambda \ge 0$ is the regularizer parameter. A related optimization problem, though not as popular or well-known, is often referred to as the generalized ${\ell }_2$-LASSO and takes the form $\hat{\mathbf{x}}:=\arg {\min }_{\mathbf{x}}\Vert \mathbf{y}-\mathbf{Ax}{\Vert }_2+\lambda f(\mathbf{x})$, and has been analyzed in [1]. [1] further made conjectures about the performance of the generalized ${\ell }_2^2$-LASSO. This paper establishes these conjectures rigorously. We measure performance with the normalized squared error $\mathrm{NSE}(\sigma ):=\Vert \hat{\mathbf{x}}-{\mathbf{x}}_0{\Vert }_2^2/{\sigma }^2$. Assuming the entries of $\mathbf{A}$ and $\mathbf{v}$ be i.i.d. standard normal, we precisely characterize the "asymptotic NSE" $\mathrm{aNSE}:={\lim }_{\sigma \to 0}\mathrm{NSE}(\sigma )$ when the problem dimensions $m,n$ tend to infinity in a proportional manner. The role of $\lambda ,f$ and ${\mathbf{x}}_0$ is explicitly captured in the derived expression via means of a single geometric quantity, the Gaussian distance to the subdifferential. We conjecture that $\mathrm{aNSE}={\sup }_{\sigma >0}\mathrm{NSE}(\sigma )$. We include detailed discussions on the interpretation of our result, make connections to relevant literature and perform computational experiments that validate our theoretical findings.

References in corpus (7)

• Simultaneous analysis of Lasso and Dantzig selector
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• A framework to characterize performance of LASSO algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Living on the edge: Phase transitions in convex programs with random data
• The Gaussian min-max theorem in the Presence of Convexity
• Sharp MSE Bounds for Proximal Denoising

Cited by in corpus (2)

• The Gaussian min-max theorem in the Presence of Convexity
• Sparsity Order Estimation from a Single Compressed Observation Vector