General Deviants: An Analysis of Perturbations in Compressed Sensing

By Matthew A. Herman, Thomas Strohmer. IEEE Journal on Selected Topics in Signal Processing, 2009

361 citations recorded by the source corpus.

We analyze the Basis Pursuit recovery of signals with general perturbations. Previous studies have only considered partially perturbed observations Ax + e. Here, x is a signal which we wish to recover, A is a full-rank matrix with more columns than rows, and e is simple additive noise. Our model also incorporates perturbations E to the matrix A which result in multiplicative noise. This completely perturbed framework extends the prior work of Candes, Romberg, and Tao on stable signal recovery from incomplete and inaccurate measurements. Our results show that, under suitable conditions, the stability of the recovered signal is limited by the noise level in the observation. Moreover, this accuracy is within a constant multiple of the best-case reconstruction using the technique of least squares. In the absence of additive noise, numerical simulations essentially confirm that this error is a linear function of the relative perturbation.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Signal Processing

View Paper: https://www.semanticscholar.org/paper/17a1e2b0840de35a05d7feadfdb34af1d30059ae

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 Electrical and Electronic Engineering

In Signal Processing

Citations in the corpus

Sensitivity to Basis Mismatch in Compressed Sensing (2010, background): “We refer the reader to [44] and [45] for more details and simply focus on contrasting their analysis to ours in the context of basis mismatch.”
Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling (2010, methodology): “PerformanceanalysisofCSandBPapproachesforthepartiallyperturbed linear model with perturbations only in the basis matrix, as well as for the fully perturbed one with perturbations present also in the measurements, was pursued recently in [12], [ 20 ], and [10].”
Structured Compressed Sensing: From Theory to Applications (2011, background): “…sources of inaccuracies in the measurements: inaccuracies due to noise at the sensing stage (in the form of additive noise ), and inaccuracies due to mismatches between the CS matrix used during recovery, , and that implemented during acquisition, (in the form of multiplicative noise [35], [36]).”
Robust Sparse Regression under Adversarial Corruption (2013, background): “Another line of work has developed approaches to handle stochastic noise or small bounded noise in the covariates (Herman & Strohmer, 2010; Rosenbaum & Tsybakov, 2010; 2011; Loh & Wainwright, 2012; Chen & Caramanis, 2013).”
Robust High Dimensional Sparse Regression and Matching Pursuit (2013, background): “ingly, we show that the brute force algorithm itself has remarkably weak performance. Another line of work has developed approaches to handle stochastic noise or small bounded noise in the covariates [17], [26], [27], [23], [9]. The corruption models in there, however, are different from ours which ”