Robust Lasso With Missing and Grossly Corrupted Observations
Authors:
- 11 December 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 59 (4) , 2036-2058
Abstract
This paper studies the problem of accurately recovering a $k$ -sparse vector $\beta^{\star}\in\BBR^{p}$ from highly corrupted linear measurements $y=X\beta^{\star}+e^{\star}+w$ , where $e^{\star}\in\BBR^{n}$ is a sparse error vector whose nonzero entries may be unbounded and $w$ is a stochastic noise term. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both $\beta^{\star}$ and $e^{\star}$. Our first result shows that the extended Lasso can faithfully recover both the regression as well as the corruption vector. Our analysis relies on the notion of extended restricted eigenvalue for the design matrix $X$. Our second set of results applies to a general class of Gaussian design matrix $X$ with i.i.d. rows ${\cal N}(0,\Sigma)$, for which we can establish a surprising result: the extended Lasso can recover exact signed supports of both $\beta^{\star}$ and $e^{\star}$ from only $\Omega(k\log p\log n)$ observations, even when a linear fraction of observations is grossly corrupted. Our analysis also shows that this amount of observations required to achieve exact signed support is indeed optimal.
Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Sparse signal recovery from sparsely corrupted measurements2011
- Robust Estimation for an Inverse Problem Arising in Multiview GeometryJournal of Mathematical Imaging and Vision, 2011
- Some sharp performance bounds for least squares regression with L1 regularizationThe Annals of Statistics, 2009
- Simultaneous analysis of Lasso and Dantzig selectorThe Annals of Statistics, 2009
- On the conditions used to prove oracle results for the LassoElectronic Journal of Statistics, 2009
- Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1+ℓ2 penalizationElectronic Journal of Statistics, 2008
- Robust Regression Shrinkage and Consistent Variable Selection Through the LAD-LassoJournal of Business & Economic Statistics, 2007
- Sparsity oracle inequalities for the LassoElectronic Journal of Statistics, 2007
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006