On A Class of Greedy Sparse Recovery Algorithms

1. Problem Statement

The paper addresses the Sparse Signal Recovery problem, specifically finding the sparsest solution $s^*$ to an under-determined linear system $x = Qs$, where $Q \in \mathbb{R}^{N \times L}$ with $N < L$.

• Mathematical Formulation: The goal is to solve the $\ell_0$-minimization problem: $\min \|s\|_0$ subject to $x = Qs$. This problem is known to be NP-hard.
• Challenges:
  • Accuracy vs. Complexity: Classical greedy methods (e.g., OMP, CoSaMP) are computationally efficient but often lack the recovery accuracy of convex relaxation methods (e.g., Basis Pursuit, IRLS). Conversely, high-accuracy methods like Iteratively Re-weighted Least Squares (IRLS) are computationally expensive and suffer from numerical instability when the system matrix $Q$ is ill-conditioned.
  • Robustness: Existing algorithms struggle with low-rank interference (noise) in measurements and degrade significantly when the condition number of $Q$ is high.

2. Methodology

The authors propose a novel framework that transforms the sparse recovery problem from the measurement space ($x$-space) directly into the solution space ($s$-space) using a specific characterization of the solution set.

2.1 Core Characterization

Using the Singular Value Decomposition (SVD) of $Q = U \Sigma V^T$, the authors characterize the solution set of $x = Qs$ as:
$$s = s_0(x) + Wz$$
Where:

• $s_0(x) = V_1 \Sigma^{-1} U_1^T x$ is a particular solution (initial estimate).
• $W$ spans the null space of $Q$.
• $z$ is a free vector variable.

This transforms the constrained problem into an unconstrained minimization in the $z$-domain:
$$z^* = \arg \min_z \|s_0 + Wz\|_0$$

2.2 Proposed Greedy Strategy

Instead of selecting atoms based on the correlation between the residual in $x$-space and columns of $Q$ (as in OMP), the proposed approach iteratively selects indices based on the residual in the $s$-space.

• Iteration: At step $k$, the algorithm solves a sub-problem to find the sparsest element in the set of possible solutions given the currently detected indices.
• Index Selection: The next index is chosen as the one corresponding to the largest magnitude entry in the updated residual vector $\tilde{s}_k$ within the $s$-space.
• Key Insight: By working in the $s$-space, the algorithm ensures that if the current support is a subset of the true support, the next selected index is guaranteed (under ideal conditions) to belong to the true support, unlike classical OMP which can make irreversible errors.

2.3 Algorithm Variants

The authors derive a family of algorithms based on different sparsity measures ($\chi$) and update strategies:

1. AlgGL2 ($\ell_2$-relaxation): Uses $\ell_2$-minimization. It is computationally similar to OMP but operates on the transformed system $s_0 = \bar{Q}s$.
2. AlgGL1 ($\ell_1$-relaxation): Uses $\ell_1$-minimization (solved via Linear Programming/BP) iteratively. It selects one atom per iteration.
3. AlgGLQ ($\ell_q$-relaxation, $0<q<1$): Uses a non-convex $\ell_q$-norm approximated via an Iteratively Re-weighted Least Squares (IRLS) scheme. This enhances sparsity promotion.
4. Fast Variants (AlgFGL1, AlgFGLQ): Incorporate a CoSaMP-style strategy, selecting multiple atoms ($\kappa_p$) per iteration to accelerate convergence.
5. Robust Extension: The framework is extended to handle low-rank disturbances ($x = Qs + \Gamma\alpha$) by augmenting the null space matrix $W$ to include the interference basis $\Gamma$.

3. Key Contributions

• Novel Framework: Introduction of a solution-set characterization that allows greedy algorithms to operate directly in the $s$-domain, bypassing the limitations of $x$-space residual minimization.
• Performance Superiority:
  • AlgGL2 significantly outperforms classical OMP in accuracy while maintaining comparable computational complexity.
  • AlgGL1 and AlgGLQ significantly outperform classical Basis Pursuit (BP) and CoSaMP in recovery accuracy.
• Robustness to Ill-Conditioning: The proposed algorithms are shown to be highly robust against ill-conditioned system matrices (high condition number $C_Q$), whereas classical IRLS and OMP fail or degrade significantly under such conditions.
• Low-Rank Interference Handling: The method provides a unified framework for separating sparse signals from low-rank noise, achieving exact recovery where classical Oracle estimators fail due to numerical singularity.
• Efficient Variants: Development of fast, multi-atom selection variants (AlgFGL) that reduce the computational burden of the iterative $\ell_1/\ell_q$ solvers.

4. Experimental Results

Extensive simulations were conducted on synthetic data and image reconstruction tasks.

• Recovery Accuracy:
  • In synthetic tests ($N=64, L=128$), AlgGL1 achieved a 100% success rate, outperforming OMP (65.8%), BP (94.3%), and matching/exceeding IRLSC.
  • In high-sparsity scenarios ($\kappa/N \approx 0.5$), AlgGLQ and AlgFGLQ maintained near-perfect recovery rates where OMP and CoSaMP failed completely.
• Computational Efficiency:
  • AlgGL2 is as fast as OMP but much more accurate.
  • The fast variants (AlgFGL1/GLQ) offer a favorable trade-off, approaching the speed of OMP while retaining the high accuracy of the slower iterative versions.
• Robustness to Condition Number:
  • When the condition number $C_Q$ increased to $10^{10}$, classical IRLSC failed due to numerical instability.
  • The proposed algorithms (AlgGL2, AlgGLQ, AlgFGLQ) maintained perfect recovery rates ($\varrho_{ok} = 1$) and stable computation times regardless of $C_Q$.
• Image Reconstruction:
  • In image transmission with low-rank interference, the proposed algorithms achieved significantly higher PSNR (Peak Signal-to-Noise Ratio) compared to OMPC and IRLSC. For example, on MRI data, proposed methods achieved ~50 dB PSNR vs. ~25 dB for classical methods.

5. Significance

This paper presents a significant advancement in sparse recovery by fundamentally changing the perspective of greedy algorithms. By shifting the search space from measurements to the solution space, the authors overcome the "myopic" nature of classical greedy methods (like OMP) that rely on local correlations.

The proposed class of algorithms bridges the gap between the computational efficiency of greedy methods and the high accuracy/robustness of convex relaxation and re-weighted methods. Crucially, their ability to handle ill-conditioned matrices and low-rank interference makes them highly suitable for real-world applications in compressed sensing, medical imaging, and signal processing where system matrices are often imperfect and noisy.