Generalized Orthogonal Matching Pursuit

Abstract

As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ''correct'' indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signals ($K>1$), provided that the sensing matrix satisfies the RIP with ${\delta }_{NK}<\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to ${\ell }_1$-minimization technique with fast processing speed and competitive computational complexity.

References in corpus (4)

• Sparsity and Incoherence in Compressive Sampling
• Improved RIP Analysis of Orthogonal Matching Pursuit
• RIP-Based Near-Oracle Performance Guarantees for Subspace-Pursuit, CoSaMP, and Iterative Hard-Thresholding
• Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?

Cited by in corpus (55)

• Nearly Optimal Bounds for Orthogonal Least Squares
• Support Recovery with Orthogonal Matching Pursuit in the Presence of Noise: A New Analysis
• Successive Bayesian Reconstructor for Channel Estimation in Fluid Antenna Systems
• MAP Support Detection for Greedy Sparse Signal Recovery Algorithms in Compressive Sensing
• Sensing User's Channel and Location with Terahertz Extra-Large Reconfigurable Intelligent Surface under Hybrid-Field Beam Squint Effect
• Swift-Link: A compressive beam alignment algorithm for practical mmWave radios
• Statistical Recovery of Simultaneously Sparse Time-Varying Signals from Multiple Measurement Vectors
• Improved Bounds on RIP for Generalized Orthogonal Matching Pursuit
• Hyperspectral Image Classification Based on Sparse Modeling of Spectral Blocks
• Joint Sparse Recovery With Semisupervised MUSIC
• Robust Non-linear Regression: A Greedy Approach Employing Kernels with Application to Image Denoising
• Greedy permanent magnet optimization
• 3D Single-pixel imaging with active sampling patterns and learning based reconstruction
• A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
• Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Compressive Spectrum Sensing for Cognitive Radio Networks
• A Comparative Study of Compressive Sensing Algorithms for Hyperspectral Imaging Reconstruction
• Greedy Algorithms for Hybrid Compressed Sensing
• Deep Neural Network Based Active User Detection for Grant-free NOMA Systems
• Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit
• Subspace Phase Retrieval
• Study of the gOMP Algorithm for Recovery of Compressed Sensed Hyperspectral Images
• Estimating Doubly-Selective Channels for Hybrid mmWave Massive MIMO Systems: A Doubly-Sparse Approach
• Online Recovery Guarantees and Analytical Results for OMP
• Deep Learning Techniques for Compressive Sensing-Based Reconstruction and Inference -- A Ubiquitous Systems Perspective
• Greedy Sparse Signal Recovery Algorithm Based on Bit-wise MAP detection
• Recovery of Sparse Signals Using Multiple Orthogonal Least Squares
• Efficient iterative thresholding algorithms with functional feedbacks and convergence analysis
• Low-Rank Matrix Completion: A Contemporary Survey
• Multipath Matching Pursuit
• Preconditioned Multiple Orthogonal Least Squares and Applications in Ghost Imaging via Sparsity Constraint
• Sparse Detection of Non-Sparse Signals for Large-Scale Wireless Systems
• Sparse Vector Coding for Ultra-Reliable and Low Latency Communications
• Asymptotic Performance Prediction for ADMM-Based Compressed Sensing
• Joint Sparse Recovery Using Signal Space Matching Pursuit
• Sampling Requirements and Accelerated Schemes for Sparse Linear Regression with Orthogonal Least-Squares
• Recovery of signals by a weighted ${\ell }_2/{\ell }_1$ minimization under arbitrary prior support information
• Subspace Thresholding Pursuit: A Reconstruction Algorithm for Compressed Sensing
• Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis
• Joint Frame Synchronization and Channel Estimation: Sparse Recovery Approach and USRP Implementation
• A Dynamic Aggregation Strategy Enhanced Efficient Global Optimization Algorithm for Solving High-Dimensional Turbomachinery Design Problems
• Tree Search Network for Sparse Regression
• Greedy Sparse Signal Recovery with Tree Pruning
• Bayesian Approach with Extended Support Estimation for Sparse Regression
• Hyperspectral Image Classification Based on Adaptive Sparse Deep Network
• Random Access for Massive Machine-Type Communications
• Efficient ${\ell }_q$ Minimization Algorithms for Compressive Sensing Based on Proximity Operator
• A Quasi-Orthogonal Matching Pursuit Algorithm for Compressive Sensing
• Greedy Sparse Signal Reconstruction Using Matching Pursuit Based on Hope-tree
• Channel aware sparse transmission for ultra low-latency communications in TDD systems
• Noise Resilient Recovery Algorithm for Compressed Sensing
• On the Fundamental Recovery Limit of Orthogonal Least Squares
• Sparse Vector Transmission: An Idea Whose Time Has Come
• A Robust Matching Pursuit Algorithm Using Information Theoretic Learning
• Sparse Approximation by Semidefinite Programming