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.
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:
- Gaussian Random Matrices: A standard benchmark to ensure performance in "ideal" CS conditions.
- Correlated Column Subset Matrices: Synthetic matrices designed with heavy intra-subset correlation to simulate the "clumpy" coherence found in structured sensing.
- 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.
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