CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

Joel A. Tropp, Deanna Needell

Introduction

In the realm of signal processing, the traditional approach to data acquisition has long been characterized by a certain inefficiency: we capture high-resolution data only to discard the vast majority of it during compression—a process exemplified by the JPEG standard. Compressed Sensing (CS) revolutionized this field by posing a provocative question: Can we capture only the essential information directly, bypassing the need for full-scale sampling?

While the mathematical theory of sampling was well-established by 2008, the reconstruction of these signals remained a bottleneck. Researchers faced a stark trade-off between two paradigms:

  1. Convex Optimization (e.g., Basis Pursuit): These methods offered high accuracy and noise robustness but were computationally intensive and slow for large-scale applications.
  2. Greedy Pursuits (e.g., Orthogonal Matching Pursuit): These were significantly faster but lacked the uniform theoretical guarantees required for reliability, often failing in the presence of noise.

Needell and Tropp introduced CoSaMP (Compressive Sampling Matching Pursuit) to bridge this gap, providing an algorithm that combines the speed of greedy searches with the mathematical rigor of convex optimization.

The CoSaMP Framework

CoSaMP is an iterative greedy pursuit algorithm designed for high-dimensional signal recovery. Unlike earlier greedy methods that incrementally add one signal component at a time, CoSaMP employs an aggressive "identify-and-prune" strategy. Each iteration of the algorithm follows five distinct stages:

  1. Identification: The algorithm generates a "proxy" of the signal residual using the adjoint of the sampling matrix. It then identifies the $2s$ largest components, where $s$ represents the target sparsity.
  2. Support Merger: These newly identified components are merged with the support set identified in the previous iteration.
  3. Estimation: The algorithm solves a least-squares problem to approximate the signal on this expanded support set. To maintain computational efficiency, the authors recommend using iterative solvers like Richardson’s iteration or Conjugate Gradient rather than direct matrix inversion.
  4. Pruning: To maintain the required sparsity, the algorithm retains only the $s$ largest entries from the least-squares estimate, discarding the rest.
  5. Sample Update: The residual is updated based on this new sparse approximation, and the process repeats.

This iterative cycle is underpinned by the Restricted Isometry Property (RIP). If the sampling matrix satisfies RIP—meaning it approximately preserves the Euclidean distance between sparse signals—CoSaMP is guaranteed to converge to the correct solution.

Key Insights and Theoretical Foundations

The success of CoSaMP stems from several critical design choices:

  • The Power of Pruning: By strictly enforcing $s$-sparsity in every iteration, the algorithm ensures the signal remains within the "safe zone" where RIP guarantees are valid. This prevents the algorithm from accumulating errors that typically plague simpler greedy methods.
  • Linear Convergence: The paper demonstrates that the error in the signal estimate drops by a constant factor in every iteration (approximately 3 decibels per iteration). This geometric convergence allows the algorithm to reach high precision with very few passes over the data.
  • Instance Optimality: The authors introduce a rigorous bound for "unrecoverable energy," accounting for both measurement noise and the "tail" of non-sparse (compressible) signals. This ensures that CoSaMP performs as well as any theoretical method could, given the inherent noise in the system.

Performance and Results

CoSaMP provides a suite of performance characteristics that make it suitable for massive, real-world datasets:

  • Computational Speed: For a signal of length $N$, the algorithm achieves a running time of $O(N \log^2 N)$ when paired with fast transform matrices (such as Partial Fourier matrices). This near-linear complexity is significantly faster than the interior-point methods used in convex optimization.
  • Sample Efficiency: The algorithm succeeds with $m = O(s \log N)$ samples, reaching the theoretical lower bound for signal recovery.
  • Robustness and Scalability: CoSaMP is provably stable; the reconstruction error is proportional to the noise level of the samples. Furthermore, it requires only $O(N)$ storage, making it feasible for signals where $N$ reaches into the millions.

Limitations and Future Directions

Despite its strengths, CoSaMP requires the user to provide the sparsity level $s$ (or a close estimate) as an input, which may not always be known in practice. Additionally, while random matrices satisfy the RIP with high probability, verifying that a specific, deterministic matrix satisfies this property remains an NP-hard problem. Future work in this area often focuses on adaptive versions of the algorithm that can estimate sparsity levels dynamically or further optimize the selection parameters during the identification and pruning phases.

Summary updated

BibTeX
@article{tropp2010cosamp,
  author = {Joel A. Tropp and Deanna Needell},
  title = {{CoSaMP: Iterative signal recovery from incomplete and inaccurate samples}},
  journal = {Communications of the ACM},
  year = {2010},
  doi = {10.1145/1859204.1859229},
}
Figure