Paper detail

Asymptotically Exact Error Analysis for the Generalized $\ell_2^2$-LASSO

Given an unknown signal $\mathbf{x}_0\in\mathbb{R}^n$ and linear noisy measurements $\mathbf{y}=\mathbf{A}\mathbf{x}_0+σ\mathbf{v}\in\mathbb{R}^m$, the generalized $\ell_2^2$-LASSO solves $\hat{\mathbf{x}}:=\arg\min_{\mathbf{x}}\frac{1}{2}\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2^2 + σλ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, $λ\geq 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}}\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2 + λ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}(σ):=\|\hat{\mathbf{x}}-\mathbf{x}_0\|_2^2/σ^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_{σ\rightarrow 0}\mathrm{NSE}(σ)$ when the problem dimensions $m,n$ tend to infinity in a proportional manner. The role of $λ,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_{σ>0}\mathrm{NSE}(σ)$. We include detailed discussions on the interpretation of our result, make connections to relevant literature and perform computational experiments that validate our theoretical findings.