Robust Sparse Signal Recovery for Compressed Sensing with Sampling and Dictionary Uncertainties

Yipeng Liu, Maarten De Vos, Sabine Van HuffelarXiv 2013 · arXiv

Introduction

Classical compressed sensing (CS) relies on the assumption that measurement and dictionary matrices are known perfectly. In practice, however, hardware limitations such as circuit noise, timing jitter, and "off-grid" signal mismatches introduce significant uncertainties into these matrices. When the actual sensing matrix deviates from the model, standard recovery methods like Basis Pursuit (BP) or Orthogonal Matching Pursuit (OMP) often fail, as they attempt to fit a signal to a flawed representation. This paper proposes a generalized framework and robust optimization models to address these sampling and dictionary uncertainties.

Problem Formulation

In an ideal CS scenario, a sparse signal $x$ is recovered from measurements $y = \Phi \Psi \theta$, where $\Phi$ is the sampling matrix and $\Psi$ is the dictionary. This paper addresses the more realistic case where the sensing matrix $A = \Phi \Psi$ is subject to an error matrix $E$, such that $y = (\bar{A} + E)\theta + n$, where $\bar{A}$ is the known nominal matrix and $n$ is additive noise. This "multiplicative noise" $E\theta$ is fundamentally different from additive noise because it scales with the signal itself, necessitating a more robust recovery approach.

Methodology

The authors introduce the Robust $\ell_0$ (RL0) optimization model. Instead of minimizing a standard least-squares residual, the RL0 model minimizes the expected data-fitting error under a stochastic framework. This leads to a constraint that incorporates a quadratic term $\theta^T P \theta$, where $P$ is the error covariance matrix, acting as a safety margin against matrix uncertainties.

Two primary algorithms are developed to solve this robust formulation:

  1. Convex Robust $\ell_1$ (CR-L1): A convex relaxation that replaces the $\ell_0$ norm with an $\ell_1$ norm. The paper provides theoretical guarantees (Theorem 1) on the number of measurements required for stable recovery despite matrix errors.
  2. Robust Orthogonal Multiple Matching Pursuit (ROMMP): A fast, greedy algorithm that transforms the sensing problem into a new coordinate system where uncertainty is implicitly handled, allowing for efficient computation.
Geometric interpretation of sparse recovery under uncertainty using L0 (a) and L1 (b) minimization.

Key Insights: The Mixed Ball Geometry

A central contribution of this work is the geometric interpretation of robust recovery. In standard $\ell_1$ minimization, the solution is found where an $\ell_1$ "ball" (a diamond shape in 2D) first touches the hyperplane defined by the measurements. Under matrix uncertainty, the slope of this hyperplane is uncertain.

The proposed robust model effectively replaces the standard $\ell_1$ ball with a "mixed ball"—a combination of the diamond-shaped $\ell_1$ ball and an ellipsoidal constraint derived from the error covariance. This hybrid geometry is significantly more resilient to shifts in the sensing matrix's orientation, increasing the likelihood of identifying the true sparse support.

The 'mixed ball' geometry proposed for robust recovery, combining diamond and ellipsoidal constraints to handle matrix uncertainty.

Experimental Results

The proposed methods were evaluated using both synthetic simulations and real-world electrocardiogram (ECG) data from the Physiobank database.

  • Simulated Data: CR-L1 consistently outperformed standard Basis Pursuit Denoising (BPDN) and Sparsely Regularized Total Least Squares (SRTLS) in terms of reconstruction error, particularly as the level of matrix uncertainty increased.
  • ECG Data: ECG signals are naturally compressible in the wavelet domain but often suffer from grid mismatches. ROMMP produced cleaner reconstructions than standard OMP, demonstrating its practical utility in biomedical signal processing.
  • Efficiency: ROMMP showed improved convergence rates, suggesting that the robust formulation provides a more favorable optimization landscape for greedy search.

Conclusion and Future Work

This research provides a robust framework for compressed sensing that accounts for the inevitable discrepancies between mathematical models and physical hardware. While the methods show significant promise, challenges remain in automatically tuning hyperparameters and handling scenarios where error covariance is unknown. Future research may focus on structured uncertainties that reflect specific physical phenomena, such as sensor drift or calibration errors.

Summary updated

BibTeX
@misc{liu2013robust,
  author = {Yipeng Liu and Maarten De Vos and Sabine Van Huffel},
  title = {{Robust Sparse Signal Recovery for Compressed Sensing with Sampling and Dictionary Uncertainties}},
  year = {2013},
  eprint = {1311.4924},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1311.4924},
}
Figure