Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization

By Nam H. Nguyen, Trac Duy Tran. 2011

123 citations recorded by the source corpus.

This paper confirms a surprising phenomenon first observed by Wright under a different setting: given m highly corrupted measurements y = AΩ·x* + e*, where AΩ· is a submatrix whose rows are selected uniformly at random from rows of an orthogonal matrix A and e* is an unknown sparse error vector whose nonzero entries may be unbounded, we show that with high probability, ℓ1-minimization can recover the sparse signal of interest x* exactly from only m = C μ2k (logn)2, where k is the number of nonzero components of x* and μ = n maxij Aij2, even if a significant fraction of the measurements are corrupted. We further guarantee that stable recovery is possible when measurements are polluted by both gross sparse and small dense errors: y = AΩ·x* + e*+ ν, where ν is the small dense noise with bounded energy. Numerous simulation results under various settings are also presented to verify the validity of the theory as well as to illustrate the promising potential of the proposed framework.

Subfields: Acoustics and Ultrasonics, Biomedical Engineering, Computational Mechanics

How researchers see this paper

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

In Acoustics and Ultrasonics

In Biomedical Engineering

In Computational Mechanics

Citations in the corpus

Byzantine Stochastic Gradient Descent (2018, neutral): “However, traditional efficient algorithms for robust optimization only worked in very limited models of corruption, or in very low dimensions [6, 7, 25, 27].”
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.”
Robust Regression via Hard Thresholding (2015, methodology): “We would like to stress three key advantages of our result over the results of [4, 5]: a) we allow b to be adversarial, i.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, methodology): “The problems of recovering the data under gross error has gained increasing attentions recently with many interesting practical applications [18] [6] [7] as well as theoretical consideration [9] [13] [8].”
Consistent Robust Regression (2017, methodology): “It is also notable that the result allows the corruption index to be k ∗ = Ω( n ) , i.e. allows upto a constant factor of the total number of data points to be arbitrarily corrupted, while ensuring consistency, which existing results [3, 6, 16] do not ensure.”
Non-convex Optimization for Machine Learning (2017, methodology): “, 2017]) compares Extended LASSO, a stateof-the-art relaxation method by Nguyen and Tran [2013b], AM-RR and the gPGD method from § 9.”
Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, background): “We also show that the ‘1-regularization solved by soft-thresholding function has a dual relationship to Huber M-estimator, which theoretically guarantees the performance of robust sparse representation in terms of M-estimation.”