Robust Lasso With Missing and Grossly Corrupted Observations

By Nam H. Nguyen, Trac Duy Tran. 2011

168 citations recorded by the source corpus.

This paper studies the problem of accurately recovering a <formula formulatype="inline"><tex Notation="TeX">$k$</tex> </formula>-sparse vector <formula formulatype="inline"><tex Notation="TeX">$\beta^{\star}\in\BBR^{p}$</tex> </formula> from highly corrupted linear measurements <formula formulatype="inline"><tex Notation="TeX">$y=X\beta^{\star}+e^{\star}+w$</tex> </formula>, where <formula formulatype="inline"> <tex Notation="TeX">$e^{\star}\in\BBR^{n}$</tex></formula> is a sparse error vector whose nonzero entries may be unbounded and <formula formulatype="inline"><tex Notation="TeX">$w$</tex></formula> is a stochastic noise term. We propose a so-called extended Lasso optimization which takes into consideration sparse prior information of both <formula formulatype="inline"><tex Notation="TeX">$\beta^{\star}$</tex> </formula> and <formula formulatype="inline"> <tex Notation="TeX">$e^{\star}$</tex></formula>. 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 <formula formulatype="inline"><tex Notation="TeX">$X$</tex></formula>. Our second set of results applies to a general class of Gaussian design matrix <formula formulatype="inline"><tex Notation="TeX">$X$</tex> </formula> with i.i.d. rows <formula formulatype="inline"><tex Notation="TeX">${\cal N}(0,\Sigma)$</tex></formula>, for which we can establish a surprising result: the extended Lasso can recover exact signed supports of both <formula formulatype="inline"> <tex Notation="TeX">$\beta^{\star}$</tex></formula> and <formula formulatype="inline"><tex Notation="TeX">$e^{\star}$</tex> </formula> from only <formula formulatype="inline"> <tex Notation="TeX">$\Omega(k\log p\log n)$</tex></formula> 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.

Subfields: Computational Mechanics, Mathematical Physics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Byzantine Stochastic Gradient Descent (2018, background): “Optimization and learning in the presence of adversarial noise is a well-studied problem [4, 5, 15, 20, 22, 28].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “A number of papers [NTN11, NT13, BJK15, BJKK17] have proposed eﬃcient algorithms for a type of robust linear regression.”
Certified Defenses for Data Poisoning Attacks (2017, background): “…(Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013; Bhatia et al., 2015) and crowdsourced data aggregation (Steinhardt et al., 2016).”
Is Feature Selection Secure against Training Data Poisoning? (2015, background): “Recent work on robust LASSO and robust regression may be another interesting future direction to implement secure feature selection against poisoning (Nasrabadi et al., 2011; Nguyen & Tran, 2013).”
Geometric median and robust estimation in Banach spaces (2013, background): “, the so-called Huber’s loss [26]), or by implementing a more flexible penalty term [35,47].”
Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, background): “In fact, we claim this conjecture in our upcoming paper for a class of Gaussian measurement matrices [33].”
Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, background): “In addition, robust sparse analysis is still an open and hot issue in information theory [18], [17], [35].”
Consistent Robust Regression (2017, methodology): “…algorithm of [3] which is a recently proposed method for performing robust least squares regression, and 3) the Extended Lasso (ex-Lasso) approach of [15] for which we use the FISTA implementation of [23] and choose the regularization paramaters for our model data as mentioned by the authors.”
Linear regression with sparsely permuted data (2017, background): “Prior works [27, 40] have considered a more general version of the problem in which β∗ is assumed to be sparse as well, thereby being able to cover the regime n < d, but it is not clear whether the results in [27, 40] can be specialized to match those of the present paper for the traditional n > d c”