Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?

Jian Wang, Byonghyo ShimIEEE TSP 2016 · OpenReview

TL;DR

This paper analyzes the Orthogonal Matching Pursuit (OMP) algorithm for recovering sparse signals from compressed measurements. The authors prove that OMP can accurately recover any K-sparse signal using just 2.8K iterations, provided the measurement matrix satisfies a specific property (RIP). This significantly reduces the previously known iteration count, bridging the gap between theoretical limits and practical performance.

What Problem Does This Paper Address?

Compressed sensing (CS) is a powerful technique that allows us to reconstruct a signal from far fewer measurements than traditional methods would require. This is possible if the signal is "sparse," meaning it has only a few non-zero components. The challenge lies in accurately recovering this original sparse signal from these limited measurements. The Orthogonal Matching Pursuit (OMP) algorithm is a popular, computationally efficient greedy method for this task. However, understanding how many iterations OMP needs to guarantee exact recovery has been an ongoing research question. Previous work established conditions for OMP's success, but often required a number of iterations that was much larger than the signal's sparsity (K), or relied on specific assumptions about the measurement matrix. This paper aims to find a tighter bound on the number of OMP iterations needed for guaranteed exact recovery, especially when the measurement matrix has a general "Restricted Isometry Property" (RIP).

Methods

The core of this paper is a theoretical analysis of the OMP algorithm. The authors use a combination of mathematical induction and careful bounding of signal and residual norms to derive their main result.

  • Restricted Isometry Property (RIP): This is a crucial property of the measurement matrix (Φ). It essentially states that the matrix approximately preserves the lengths of sparse vectors. The paper analyzes OMP's performance under the RIP condition.
  • Mathematical Induction: The proof relies on induction on the number of remaining unknown support indices (the indices of non-zero elements in the sparse signal). They show that if OMP can recover signals with fewer than γ-1 remaining indices in c(γ-1) iterations, it can also recover signals with γ remaining indices in cγ iterations.
  • Bounding Residuals: A key part of the proof involves carefully bounding the error (residual) at each iteration. They establish upper bounds on the residual norm and lower bounds on the difference in residual norms between consecutive iterations.
  • OMP_cK Notation: To distinguish OMP running more than K iterations, they use the notation OMP_cK, where c is a factor greater than 1.

Datasets

Not discussed in the paper. The analysis is theoretical and focuses on the properties of the measurement matrix and the signal's sparsity.

Key Insights and Ideas

  • Significantly Reduced Iteration Count: The most striking insight is the tight bound of 2.8K iterations for guaranteed exact recovery. This is a substantial improvement over previous results that might require 30K or more iterations.
  • Bridging the Gap: The result effectively bridges the gap between the theoretical "fundamental limit" of OMP (where exact recovery might not be uniformly guaranteed) and the practical performance observed in prior research.
  • Absolute Constant RIC: The analysis shows that OMP can achieve exact recovery with an absolute constant RIC, meaning the condition doesn't degrade as the sparsity K increases. This is a strong guarantee.
  • Trade-off Between Iterations and RIC: The paper highlights the interplay between the number of iterations (c) and the acceptable level of the Restricted Isometry Constant (RIC). A higher c allows for a less restrictive RIC, but at the cost of more computation.

Key Results

The main quantitative result is Theorem 2, which states that if a measurement matrix Φ satisfies the RIP of order [(c + 1)K] and c > 4 log 2 ≈ 2.8, then OMP_cK perfectly recovers any K-sparse signal x from measurements y = Φx. This implies that OMP can recover K-sparse signals in [2.8K] iterations.

Qualitatively, the paper demonstrates that OMP is more powerful than previously thought when allowed to run for more than K iterations, especially under the general RIP condition. The result is shown to be uniformly smaller than prior bounds, offering a more practical and tighter guarantee.

Limitations and Future Work

  • Theoretical Focus: The results are theoretical and based on the RIP condition. While RIP is a reasonable assumption for many practical measurement matrices (especially random ones), real-world scenarios might involve matrices that don't perfectly satisfy RIP.
  • Noisy Measurements: The current analysis focuses on exact recovery from noiseless measurements. Extending these results to handle noisy measurements would be a valuable future direction.
  • Computational Complexity: While the number of iterations is reduced, OMP's computational complexity per iteration can still be significant, especially for large K. Future work could explore how this theoretical bound translates to practical computational gains.
  • Comparison with Other Algorithms: The paper primarily focuses on OMP. Comparing the derived iteration bounds with other sparse recovery algorithms (like CoSaMP or Basis Pursuit) under similar conditions would provide further context.

Summary updated

Abstract

Orthogonal matching pursuit (OMP) is a greedy algorithm widely used for the recovery of sparse signals from compressed measurements. In this paper, we analyze the number of iterations required for the OMP algorithm to perform exact recovery of sparse signals. Our analysis shows that OMP can accurately recover all K-sparse signals within [2.8 K] iterations when the measurement matrix satisfies a restricted isometry property (RIP). Our result improves upon the recent result of Zhang and also bridges the gap between Zhang's result and the fundamental limit of OMP at which exact recovery of K-sparse signals cannot be uniformly guaranteed.
BibTeX
@article{wang2016exact,
  author = {Jian Wang and Byonghyo Shim},
  title = {{Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?}},
  journal = {IEEE Trans. Signal Process.},
  year = {2016},
  url = {https://openreview.net/forum?id=S2FWB_-eN0},
}
Figure