Robust Lasso with missing and grossly corrupted observations
Authors:
- Nam H. NguyenNNNam H. Nguyen
- Trac D. TranTTTrac D. Tran
Preprint
Abstract
This paper studies the problem of accurately recovering a sparse vector $\beta^{\star}$ from highly corrupted linear measurements $y = X \beta^{\star} + e^{\star} + w$ where $e^{\star}$ is a sparse error vector whose nonzero entries may be unbounded and $w$ is a bounded noise. 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 $\oper 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 the fraction of corruption is arbitrarily close to one. 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 25 references indexed in Scilit:
- Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-MinimizationIEEE Transactions on Information Theory, 2013
- Compressed Sensing and Matrix Completion with Constant Proportion of CorruptionsConstructive Approximation, 2012
- Dense Error Correction Via $\ell^1$-MinimizationIEEE Transactions on Information Theory, 2010
- Sparse Additive ModelsJournal of the Royal Statistical Society Series B: Statistical Methodology, 2009
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- Robust Regression Shrinkage and Consistent Variable Selection Through the LAD-LassoJournal of Business & Economic 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
- Model Selection and Estimation in Regression with Grouped VariablesJournal of the Royal Statistical Society Series B: Statistical Methodology, 2005
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996