Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing

Abstract

In compressed sensing one measures sparse signals directly in a compressed form via a linear transform and then reconstructs the original signal. However, it is often the case that the linear transform itself is known only approximately, a situation called matrix uncertainty, and that the measurement process is noisy. Here we present two contributions to this problem: first, we use the replica method to determine the mean-squared error of the Bayes-optimal reconstruction of sparse signals under matrix uncertainty. Second, we consider a robust variant of the approximate message passing algorithm and demonstrate numerically that in the limit of large systems, this algorithm matches the optimal performance in a large region of parameters.

5 pages, 4 figures

References in corpus (3)

• Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction

Cited by in corpus (5)

• Statistical physics of inference: Thresholds and algorithms
• Parametric Bilinear Generalized Approximate Message Passing
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Non-adaptive pooling strategies for detection of rare faulty items
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix