Fast Orthogonal Matching Pursuit through Successive Regression

Huiyuan Yu, Jia He, Maggie Cheng
3/29/2024
cs.CVmath.OC

No confident code implementation found for this paper.

Abstract

Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal recovery and approximation. However, OMP suffers computational issues when the signal has a large number of non-zeros. This paper advances OMP and its extension called generalized OMP (gOMP) by offering fast algorithms for the orthogonal projection of the input signal at each iteration. The proposed modifications directly reduce the computational complexity of OMP and gOMP. Experiment results verified the improvement in computation time. This paper also provides sufficient conditions for exact signal recovery. For general signals with additive noise, the approximation error is at the same order as OMP (gOMP), but is obtained within much less time.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds

80% match1 repo662018

A Fast and Provable Algorithm for Sparse Phase Retrieval

79% match2023

Optimal sparse phase retrieval via a quasi-Bayesian approach

79% match1 repo2025

Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery

79% match1 repo32023

Adaptive Block Sparse Regularization under Arbitrary Linear Transform

79% match2024

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

77% match2025

Cite this paper

@article{yu2024fast,
  title  = {Fast Orthogonal Matching Pursuit through Successive Regression},
  author = {Huiyuan Yu and Jia He and Maggie Cheng},
  year   = {2024},
  eprint = {2404.00146},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2404.00146v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2404.00146.svg)](https://codeofpaper.com/paper/2404.00146)

Discussion