General Perturbations of Sparse Signals in Compressed Sensing

Matthew A. Herrman, Thomas Strohmer, Hal Id Hal, Matthew A. Herman2010

TL;DR

This paper tackles the challenge of recovering sparse signals in compressed sensing (CS) when both the measurement matrix and the observed data are subject to general perturbations. They introduce a "completely perturbed" model that accounts for multiplicative noise in the sensing matrix, extending previous work that only considered additive noise. Their findings show that the accuracy of signal recovery is fundamentally limited by the noise level, even in this more general scenario.

What Problem Does This Paper Address?

Compressed sensing (CS) is a powerful technique for reconstructing sparse signals from fewer measurements than traditionally required. The foundational work in CS often assumed an ideal scenario where the measurement matrix ($A$) and the observed signal ($b$) were perfectly known and noise-free ($b = Ax$). More recent research has relaxed this by considering additive noise in the observation ($b = Ax + e$). However, real-world applications often face more complex scenarios where the sensing mechanism itself can be imperfect. This paper addresses this gap by introducing a "completely perturbed" model where the measurement matrix is also subject to perturbations, represented as $\hat{A} = A + E$. This $\hat{A}$ can arise from precision errors in physical implementations or inaccuracies in modeling transmission channels. The authors aim to understand how these combined perturbations affect the stability and accuracy of signal recovery using the Basis Pursuit (BP) algorithm.

Methods

The core of the paper lies in analyzing the impact of these general perturbations on the Basis Pursuit (BP) algorithm. They extend the concept of the Restricted Isometry Property (RIP), which is crucial for CS guarantees, to the perturbed matrix $\hat{A}$. They define a new RIP constant, $\delta_{\hat{A}}$, that accounts for the perturbations $E$.

The key theoretical tools used are:

  • Restricted Isometry Property (RIP): This property quantifies how well a matrix preserves distances for sparse vectors. The paper extends the analysis of RIP to the perturbed matrix $\hat{A}$.
  • Basis Pursuit (BP): This is an $l_1$-minimization problem used to recover sparse signals. The paper analyzes the BP solution under the completely perturbed model.
  • Perturbation Analysis: The authors derive bounds on the error of the recovered signal in terms of the noise levels in both the measurement matrix ($E$) and the observation vector ($e$). They introduce a combined perturbation term $\epsilon'_{A, \kappa, b}$ to capture the overall noise.
  • Classical $l_2$ Perturbation Analysis: For comparison, they also analyze the performance of a least-squares approach when the support of the sparse signal is known (the "oracle" case).

Datasets

Not discussed in the paper. The authors use synthetic data generated for numerical simulations.

Key Insights and Ideas

  • Fundamental Noise Limit: Even with a perturbed sensing matrix, the accuracy of the recovered sparse signal is fundamentally limited by the overall noise level (both in the matrix and the observation). This is a crucial takeaway, suggesting that no algorithm can overcome this inherent noise floor.
  • Multiplicative Noise Impact: The introduction of multiplicative noise (via the perturbed matrix $E$) generally degrades the accuracy of the BP solution compared to scenarios with only additive noise. This is demonstrated through theoretical bounds and numerical examples.
  • Linear Scaling with Perturbation: The theoretical analysis and numerical simulations suggest that the error in the BP solution scales roughly linearly with the relative perturbation in the sensing matrix ($\epsilon_A^{(K)}$). This provides a clear understanding of how matrix imperfections affect recovery.
  • Rank Preservation: A key lemma shows that under certain conditions, the rank of submatrices of the perturbed matrix $\hat{A}$ remains the same as the original matrix $A$. This is important for ensuring that the underlying structure needed for recovery is not destroyed by the perturbations.
  • BP vs. Least Squares: The paper highlights that while both BP and least squares (with known support) are limited by noise, BP represents a "worst, of the worst-case" scenario. The oracle least squares solution provides a benchmark for the best possible recovery given the noise.

Key Results

  • Theorem 1: Establishes the RIP constant for the perturbed matrix $\hat{A} = A + E$, showing how it depends on the original RIP constant of $A$ and the relative perturbation $\epsilon_A^{(K)}$.
  • Theorem 2: Provides an upper bound on the error of the Basis Pursuit solution ($z^*$) for a K-sparse signal $x$ under the completely perturbed model: $||z^* - x||_2 \le C_{BP} \epsilon'_{A, \kappa, b}$. The constant $C_{BP}$ quantifies the degradation due to perturbations.
  • Numerical Simulations: Figure 1 demonstrates that the relative error of the BP solution increases with sparsity $K$ and scales roughly linearly with the relative perturbation $\epsilon_A$.
  • Comparison with Least Squares: The paper shows that the error bound for the oracle least squares solution is $||z^{\#} - x||_2 < C_{LS} \epsilon'_{A, \kappa, b}$, where $C_{LS} = 1/(1-\delta_\kappa)$. This confirms that BP is generally less accurate than ideal least squares but shares the same fundamental noise limitation.

Limitations and Future Work

  • K-Sparse Assumption: The current analysis is limited to strictly K-sparse signals. The authors mention that their results can be extended to compressible signals (signals with a few large coefficients and many small ones), as discussed in their related work [6].
  • Worst-Case Analysis: The theoretical bounds and the derived constants ($C_{BP}$) represent worst-case scenarios. In practice, performance is often better, as suggested by the authors and observed in simulations.
  • Specific Perturbation Models: The paper focuses on a specific model of perturbation ($E$). Future work could explore other types of matrix perturbations.
  • Algorithm Development: While the paper analyzes the stability of BP, it doesn't propose new algorithms. Future research could focus on developing more robust algorithms that are less sensitive to these general perturbations.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@misc{herrman2010general,
  author = {Matthew A. Herrman and Thomas Strohmer and Hal Id Hal and Matthew A. Herman and Thomas Strohmer},
  title = {{General Perturbations of Sparse Signals in Compressed Sensing}},
  year = {2010},
}
Figure