General Deviants: An Analysis of Perturbations in Compressed Sensing

Abstract

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.

11 pages, 1 figure, preprint

Cited by in corpus (48)

• Structured Compressed Sensing: From Theory to Applications
• Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling
• Self-Calibration and Biconvex Compressive Sensing
• Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation
• Noise Folding in Compressed Sensing
• Low-complexity Multiclass Encryption by Compressed Sensing
• Convex Optimization Approaches for Blind Sensor Calibration using Sparsity
• On Known-Plaintext Attacks to a Compressed Sensing-based Encryption: A Quantitative Analysis
• Bi-level Protected Compressive Sampling
• Sparse Bayesian learning with uncertainty models and multiple dictionaries
• Atomic Norm Minimization for Modal Analysis from Random and Compressed Samples
• Perturbation Analysis of Orthogonal Matching Pursuit
• Compressed Genotyping
• Peak Reduction and Clipping Mitigation by Compressive Sensing
• Group Testing with Probabilistic Tests: Theory, Design and Application
• Signal Recovery from Unlabeled Samples
• Compressive Radar with Off-Grid Targets: A Perturbation Approach
• Efficient Algorithms for Outlier-Robust Regression
• On the Performance Bound of Sparse Estimation with Sensing Matrix Perturbation
• Estimating Sparse Signals Using Integrated Wideband Dictionaries
• MUSIC for Single-Snapshot Spectral Estimation: Stability and Super-resolution
• A Non-Convex Blind Calibration Method for Randomised Sensing Strategies
• Compressed Remote Sensing of Sparse Objects
• Accurate detection of moving targets via random sensor arrays and Kerdock codes
• Robust High Dimensional Sparse Regression and Matching Pursuit
• Oracle-order Recovery Performance of Greedy Pursuits with Replacement against General Perturbations
• Through the Haze: a Non-Convex Approach to Blind Gain Calibration for Linear Random Sensing Models
• Blind Demixing and Deconvolution at Near-Optimal Rate
• Model-Based Calibration of Filter Imperfections in the Random Demodulator for Compressive Sensing
• Robustness to unknown error in sparse regularization
• A null space analysis of the L1 synthesis method in dictionary-based compressed sensing
• Mismatch in the Classification of Linear Subspaces: Sufficient Conditions for Reliable Classification
• Robust reconstruction of sparse network dynamics
• Spectral Compressed Sensing via Projected Gradient Descent
• Mixed Operators in Compressed Sensing
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix
• Signal Recovery in Perturbed Fourier Compressed Sensing
• Efficient Two-Dimensional Line Spectrum Estimation Based on Decoupled Atomic Norm Minimization
• Noise Folding based on General Complete Perturbation in Compressed Sensing
• A Compressive Sensing Approach to Community Detection with Applications
• Compressive Sensing for cut improvement and local clustering
• Reconstruction under outliers for Fourier-sparse functions
• Sparse linear regression from perturbed data
• Robust lEarned Shrinkage-Thresholding (REST): Robust unrolling for sparse recover
• You Need to Calm Down: Calmness Regularity for a Class of Seminorm Optimization Problems
• One Bit to Rule Them All : Binarizing the Reconstruction in 1-bit Compressive Sensing
• Sparse regression with highly correlated predictors
• On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions