Robust Lasso with missing and grossly corrupted observations

This paper studies the problem of accurately recovering a sparse vector β? from highly corrupted linear measurements y = Xβ? + e? + w where e? 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 consider-ation sparse prior information of both β? and e?. Our first result shows that the extended Lasso can faithfully recover both the regression and the corruption vec-tors. Our analysis is relied on a notion of extended restricted eigenvalue for the design matrix X. Our second set of results applies to a general class of Gaus-sian design matrix X with i.i.d rows N (0,Σ), for which we provide a surprising phenomenon: the extended Lasso can recover exact signed supports of both β? and e? from only Ω(k log p log n) observations, even 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 optimal.