LASSO risk and phase transition under dependence

DOI10.1214/22-EJS2092MaRDI QIDQ6364076arXivFDO

Authors Hanwen Huang

Publication date 29 March 2021

Published in arXiv

Full work available at URL https://doi.org/10.1214/22-EJS2092

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12)

arXiv classification

math.STstat.COstat.TH

Abstract: We consider the problem of recovering a $k$-sparse signal $$�eta$$ from noisy observations $$�eta$$. 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 $$ is drawn from distribution $$Sigma$$ with general $$Sigma$$. We first derive the asymptotic risk of LASSO in the limit of $n,pightarrowinfty$ with $n/pightarrowdelta$. We then examine conditions on $n$, $p$, and $k$ for LASSO to exactly reconstruct $$�eta$$ in the noiseless case $$. A phase boundary $delt{a}_c=delta(epsilon)$ is precisely established in the phase space defined by $0ledelta,epsilonle1$, where $epsilon=k/p$. Above this boundary, LASSO perfectly recovers $$�eta$$ with high probability. Below this boundary, LASSO fails to recover $$�eta$$ with high probability. While the values of the non-zero elements of $$�eta$$ do not have any effect on the phase transition curve, our analysis shows that $delt{a}_c$ does depend on the signed pattern of the nonzero values of $$�eta$$ for general $$Sigma$$. This is in sharp contrast to the previous phase transition results derived in i.i.d. case with $$Sigma$$ where $delt{a}_c$ is completely determined by $epsilon$ regardless of the distribution of $$�eta$$. 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 $$Sigma$$. Extensive computational experiments confirm that our theoretical predictions are consistent with simulation results on moderate size system.

This page was built for publication: LASSO risk and phase transition under dependence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6364076)