Guaranteed sparse signal recovery with highly coherent sensing matrices

Guangliang Chen, Atul Divekar, Deanna Needell

Abstract

Traditional compressive sensing (CS) relies on the Restricted Isometry Property (RIP), which is often violated by structured sensing matrices in practical applications like image super-resolution. This paper introduces Partial Inversion (PartInv), a greedy algorithm that replaces the standard adjoint-based proxy with a pseudo-inverse step to mitigate internal interference from correlated columns. Theoretical and experimental results demonstrate that PartInv significantly expands the success region for signal recovery compared to standard methods like CoSaMP and $\ell_1$-minimization.

Introduction

Compressive Sensing (CS) enables the reconstruction of sparse signals from sub-Nyquist samples. However, its theoretical foundations often assume sensing matrices with low coherence, typically satisfied by random Gaussian or Bernoulli matrices. In real-world scenarios, such as image super-resolution, the sensing process involves blurring and downsampling, resulting in highly structured matrices where neighboring columns are strongly correlated.

Visualization of a highly coherent sensing matrix where off-diagonal elements indicate strong column correlations.

This high coherence introduces significant "self-noise" during recovery. Standard greedy algorithms (like CoSaMP) and convex optimization techniques ($\ell_1$-minimization) often struggle because the high correlation between columns causes signal energy to "leak" into neighboring components, making it difficult to identify the true underlying signal.

The Partial Inversion (PartInv) Algorithm

To address this, the authors propose Partial Inversion (PartInv), a modification of the popular CoSaMP algorithm.

  • The Standard Approach (CoSaMP): Uses the adjoint of the sensing matrix ($\Phi^* y$) to create a "proxy" of the signal. If columns are correlated, this proxy becomes noisy due to mutual interference.
  • The PartInv Approach: Instead of a simple adjoint, it uses a pseudo-inverse ($\Phi_I^\dagger y$) on a selected subset of columns ($I$).
  • Mechanism: The pseudo-inverse step explicitly cancels out the mutual interference term that arises from column correlation within the active set. This allows the algorithm to "see through" the coherence of the matrix.

The authors also provide a version of the algorithm specifically for signals sparse in the wavelet domain, leveraging the natural quadtree structure of images to improve selection accuracy.

Experimental Evaluation

The performance of PartInv was evaluated across three settings:

  1. Gaussian Random Matrices: A standard benchmark to ensure performance in "ideal" CS conditions.
  2. Correlated Column Subset Matrices: Synthetic matrices designed with heavy intra-subset correlation to simulate the "clumpy" coherence found in structured sensing.
  3. 2D Wavelet Patches: $32 \times 32$ image patches using Daubechies-5 wavelets, with sensing matrices constructed by simulating a $5 \times 5$ blurring kernel followed by various downsampling patterns.

Results and Discussion

The primary finding is that PartInv significantly outperforms existing methods in the presence of high coherence. Phase transition plots reveal a much larger success region (the area where signals are recovered with high probability) for PartInv compared to CoSaMP and $\ell_1$-minimization.

Phase transition plots comparing recovery success rates across different algorithms and settings. PartInv (bottom row) shows a significantly larger success region (black) compared to baseline methods.

Key insights include:

  • Eliminating Self-Noise: By treating the recovery as a local system of equations via pseudo-inversion, PartInv effectively removes the interference that typically masks true signal components in coherent matrices.
  • Relaxed Theoretical Bounds: The authors provide a theoretical guarantee showing that PartInv can recover signals under conditions milder than the standard RIP. Recovery is possible if the active columns are invertible and the off-support columns are not excessively correlated with them.
  • Parameter Sensitivity: The size of the inversion set ($L$) is a critical hyperparameter. While larger $L$ can improve performance in highly correlated settings, it may also amplify external noise, necessitating careful tuning.

Conclusion

PartInv offers a robust alternative for sparse recovery in structured sensing environments. While it incurs higher computational costs due to repeated pseudo-inverse calculations, its ability to maintain accuracy despite matrix coherence makes it particularly suitable for applications like image super-resolution. Future work aims to automate parameter tuning and extend theoretical guarantees to a broader class of signals.

Summary updated

BibTeX
@inproceedings{chen2014guaranteed,
  author = {Guangliang Chen and Atul Divekar and Deanna Needell},
  title = {{Guaranteed sparse signal recovery with highly coherent sensing matrices}},
  booktitle = {Sampling},
  year = {2014},
  doi = {10.1007/bf03549574},
}
Figure