LASSO risk and phase transition under dependence

Abstract

We consider the problem of recovering a $k$-sparse signal ${\mbox{$β$}}_0\in\mathbb{R}^p$ from noisy observations $\bf y={\bf X}\mbox{$β$}_0+{\bf w}\in\mathbb{R}^n$. One of the most popular approaches is the $l_1$-regularized least squares, also known as LASSO. We analyze the mean square error of LASSO in the case of random designs in which each row of $\mathbf{X}$ is drawn from distribution $N(0,{\mbox{$Σ$}})$ with general ${\mbox{$Σ$}}$. We first derive the asymptotic risk of LASSO in the limit of $n,p\to \infty$ with $n/p\to \delta$. We then examine conditions on $n$, $p$, and $k$ for LASSO to exactly reconstruct ${\mbox{$β$}}_0$ in the noiseless case $\mathbf{w}=0$. A phase boundary ${\delta }_c=\delta (\epsilon )$ is precisely established in the phase space defined by $0\le \delta ,\epsilon \le 1$, where $\epsilon =k/p$. Above this boundary, LASSO perfectly recovers ${\mbox{$β$}}_0$ with high probability. Below this boundary, LASSO fails to recover $\mbox{$β$}_0$ with high probability. While the values of the non-zero elements of ${\mbox{$β$}}_0$ do not have any effect on the phase transition curve, our analysis shows that ${\delta }_c$ does depend on the signed pattern of the nonzero values of $\mbox{$β$}_0$ for general ${\mbox{$Σ$}}\ne{\bf I}_p$. This is in sharp contrast to the previous phase transition results derived in i.i.d. case with $\mbox{$Σ$}={\bf I}_p$ where ${\delta }_c$ is completely determined by $\epsilon$ regardless of the distribution of $\mbox{$β$}_0$. Underlying our formalism is a recently developed efficient algorithm called approximate message passing (AMP) algorithm. We generalize the state evolution of AMP from i.i.d. case to general case with ${\mbox{$Σ$}}\ne{\bf I}_p$. Extensive computational experiments confirm that our theoretical predictions are consistent with simulation results on moderate size system.

40 pages, 7 figures

References in corpus (2)

• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Sharp thresholds for high-dimensional and noisy recovery of sparsity