Robust Lasso with missing and grossly corrupted observations
arXiv:1112.0391
Abstract
This paper studies the problem of accurately recovering a sparse vector from highly corrupted linear measurements where is a sparse error vector whose nonzero entries may be unbounded and is a bounded noise. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both and . 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 . Our second set of results applies to a general class of Gaussian design matrix with i.i.d rows $\oper N(0, Σ)$, for which we can establish a surprising result: the extended Lasso can recover exact signed supports of both and from only 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.
arXiv comment19 pages, 3 figures. Partial of this work is presented at NIPS 2011 conference in Granda, Spain, December 2011
References in corpus (7)
- Simultaneous analysis of Lasso and Dantzig selector
- On the conditions used to prove oracle results for the Lasso
- The composite absolute penalties family for grouped and hierarchical variable selection
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- High-dimensional additive modeling
- Support union recovery in high-dimensional multivariate regression
- Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions