Fast OMP for Exact Recovery and Sparse Approximation

• URL: http://arxiv.org/abs/2404.00146v1
• Date: Fri, 29 Mar 2024 20:39:37 GMT
• Title: Fast OMP for Exact Recovery and Sparse Approximation
• Authors: Huiyuan Yu, Jia He, Maggie Cheng,
• Abstract summary: This paper advances Orthogonal Matching Pursuit (OMP) in two fronts. It offers a fast algorithm for the projection of the input signal at each iteration, and a new selection criterion for making the greedy choice. Experiment results show significant improvement over the classical OMP in computation time.
• Score: 4.915061940934031
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal recovery and approximation. However OMP suffers computational issue when the signal has large number of non-zeros. This paper advances OMP in two fronts: it offers a fast algorithm for the orthogonal projection of the input signal at each iteration, and a new selection criterion for making the greedy choice, which reduces the number of iterations it takes to recover the signal. The proposed modifications to OMP directly reduce the computational complexity. Experiment results show significant improvement over the classical OMP in computation time. The paper also provided a sufficient condition for exact recovery under the new greedy choice criterion. For general signals that may not have sparse representations, the paper provides a bound for the approximation error. The approximation error is at the same order as OMP but is obtained within fewer iterations and less time.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  A quantum-based feature selection algorithm for the multi-classification problem, namely, QReliefF, is proposed. Our algorithm is superior in finding the nearest neighbor, reducing the complexity from O(M) to O(sqrt(M)).
  arXiv  Detail & Related papers  (2023-10-01T03:57:13Z)
• Provably Convergent Subgraph-wise Sampling for Fast GNN Training [122.68566970275683]
  We propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC) LMC retrieves the discarded messages in backward passes based on a message passing formulation of backward passes. Experiments on large-scale benchmarks demonstrate that LMC is significantly faster than state-of-the-art subgraph-wise sampling methods.
  arXiv  Detail & Related papers  (2023-03-17T05:16:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering [18.888312436971187]
  This paper proposes a new SSC scheme using generalized OMP (GOMP) GOMP involves fewer iterations, thereby enjoying lower algorithmic complexity. The proposed stopping rule is free from off-line estimation of subspace dimension and noise power.
  arXiv  Detail & Related papers  (2022-04-06T04:20:35Z)
• Fast, Accurate and Memory-Efficient Partial Permutation Synchronization [15.813217907813778]
  We propose an improved algorithm, CEMP-Partial, for estimating the corruption levels of the observed partial permutations. We prove that under adversarial corruption, though without additive noise and with certain assumptions, CEMP-Partial is able to exactly classify corrupted and clean partial permutations. We demonstrate state-of-the-art accuracy, speed and memory efficiency of our method on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2022-03-30T17:41:17Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• DeepMP for Non-Negative Sparse Decomposition [14.790515227906257]
  Non-negative signals form an important class of sparse signals. greedy and convex relaxed algorithms are among the most popular methods. One such modification has been proposed for Matching Pursuit (MP) based algorithms.
  arXiv  Detail & Related papers  (2020-07-28T14:52:06Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.