Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

2007/12/01 by Joel A. Tropp, Anna C. Gilbert · 216 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Blind Source Separation Techniques #Microwave Imaging and Scattering Analysis

paper · doi:10.1109/tit.2007.909108

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with <emphasis><formula formulatype="inline"><tex>m</tex></formula></emphasis> nonzero entries in dimension <emphasis><formula formulatype="inline"><tex>d</tex> </formula></emphasis> given <emphasis><formula formulatype="inline"><tex> \rm O(m ln d)</tex></formula></emphasis> random linear measurements of that signal. This is a massive improvement over previous results, which require <emphasis><formula formulatype="inline"><tex>\rm O(m²)</tex></formula></emphasis> measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems. </para>

Citations

• Compressed sensing

Cited by

• Deterministic Construction of Binary, Bipolar, and Ternary Compressed Sensing Matrices
• LDPC Codes for Compressed Sensing
• Deterministic Constructions of Compressed Sensing Matrices From Unitary Geometry
• Channel estimation strategies for underwater acoustic (UWA) communication: An overview
• Internet of Underwater Things Infrastructure: A Shared Underwater Acoustic Communication Layer Scheme for Real-world Underwater Acoustic Experiments
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Triple IRS-Aided Communications: Row-Column Sparsity Enhanced Bayesian Tensor Learning for Channel Estimation
• ST-DDA: Dynamic Channel Estimation in the Doppler-Delay-Angle Domain via Sparse Subspace Tracking for TDD Systems
• A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization
• Enforcing Orderedness to Improve Feature Consistency
• Computing a k-sparse n-length Discrete Fourier Transform using at most\n 4k samples and O(k log k) complexity
• Optimal Sensor Placement and Enhanced Sparsity for Classification
• Compressive Sampling for the Packet Loss Recovery in Audio Multimedia Streaming
• Convergence of the Generalized Alternating Projection Algorithm for Compressive Sensing
• The Convergence Guarantees of a Non-convex Approach for Sparse Recovery
• Deep Sparse Coding Using Optimized Linear Expansion of Thresholds
• Multi-Focus Image Fusion Using Sparse Representation and Coupled Dictionary Learning
• On the Fundamental Recovery Limit of Orthogonal Least Squares
• Bias-variance tradeoff in MIMO channel estimation
• Segment-Sliding Reconstruction of Pulsed Radar Echoes with Sub-Nyquist Sampling
• Common Codebook Millimeter Wave Beam Design: Designing Beams for Both Sounding and Communication with Uniform Planar Arrays
• Channel Estimation for RIS-Aided mmWave MIMO Systems via Atomic Norm Minimization
• Modified Frame Reconstruction Algorithm for Compressive Sensing
• Toward Alias-Free Channel Extrapolation in Upper Mid-Band Systems: A Spatial-Frequency-Temporal Tensor Learning Approach
• Structured Sparsity Models for Multiparty Speech Recovery from Reverberant Recordings
• Extension of Sparse Randomized Kaczmarz Algorithm for Multiple\n Measurement Vectors
• Hybrid Analog-Digital Transceiver Designs for Cognitive Large-Scale Antenna Array Systems
• On-Off Random Access Channels: A Compressed Sensing Framework
• Sparse Inverse Problems Over Measures: Equivalence of the Conditional\n Gradient and Exchange Methods
• One-Shot Neural Architecture Search via Compressive Sensing
• Ramanujan sums in signal recovery and uncertainty principle inequalities
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing
• Greedy Sparse Signal Recovery Algorithm Based on Bit-wise MAP detection
• Semi-supervised Stacked Label Consistent Autoencoder for Reconstruction and Analysis of Biomedical Signals
• Enhancing Channel Estimation for OTFS systems using Sparse Bayesian Learning with Adaptive Threshold
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• Joint Channel Estimation and Data Detection for Multi-LEO-Satellite Cell-Free OTFS Uplinks
• Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity
• Compressed Sensing for Block-Sparse Smooth Signals
• Discriminative Local Sparse Representations for Robust Face Recognition
• Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
• Passive Beamforming and Information Transfer via Large Intelligent Surface
• Alternating Direction Algorithms for ℓ₁-Problems in Compressive Sensing
• Compressive Spectrum Sensing for Cognitive Radio Networks
• Sparse regression with highly correlated predictors
• Channel-Wise Early Stopping without a Validation Set via NNK Polytope\n Interpolation
• Secure and efficient compressed sensing based encryption with sparse matrices
• Axon Hillock Currents Allow Single-Neuron-Resolution 3-Dimensional Functional Neural Imaging Using Diamond Quantum Defect-Based Vector Magnetometry
• FPGA system for real-time computational extended depth of field imaging using phase aperture coding
• An unsupervised posterior sampling framework for multi-purpose seismic data recovery
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing
• Recovery of Sparse Signals Using Multiple Orthogonal Least Squares
• Fourier Domain Beamforming: The Path to Compressed Ultrasound Imaging
• Channel Estimation for Extremely Large-Scale Massive MIMO Systems
• Bayesian compressed sensing with new sparsity-inducing prior
• Environment-Aware MIMO Channel Estimation in Pilot-Constrained Upper Mid-Band Systems
• LAMP: A Locally Adapting Matching Pursuit Framework for Group Sparse Signatures in Ultra-Wide Band Radar Imaging
• From Generality to Specificity: Prior-Driven Optimal Sparse Transformation in Compressed Sensing
• UNILocPro: Unified Localization Integrating Model-Based Geometry and Channel Charting
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• High-speed real-time single-pixel microscopy based on Fourier sampling
• Non-Coherent Direction of Arrival Estimation via Frequency Estimation
• Automatic scoring of apnea and hypopnea events using blood oxygen saturation signals
• Two-Timescale End-to-End Learning for Channel Acquisition and Hybrid Precoding
• Site-specific online compressive beam codebook learning in mmWave vehicular communication
• Support Recovery of Sparse Signals
• Millimeter Wave Channel Estimation via Exploiting Joint Sparse and Low-Rank Structures
• Millimeter Wave Communications for Future Mobile Networks
• Optimal data recovery and forecasting with dummy long-horizon forecasts
• Efficient Compressed Sensing Based Image Coding by Using Gray Transformation
• DO-CGI: deep-optimized illumination patterns for computational ghost imaging at low sampling ratios
• A Greedy Algorithm for Matrix Recovery with Subspace Prior Information
• Dictionary Learning With BLOTLESS Update
• An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
• Unsupervised Blind Image Quality Evaluation via Statistical Measurements of Structure, Naturalness, and Perception
• Hybrid Transceivers Design for Large-Scale Antenna Arrays Using Majorization-Minimization Algorithms
• Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
• Ordered Sequence Detection and Barrier Signal Design for Digital Pulse Interval Modulation in Optical Wireless Communications
• New Beam Tracking Technique for Millimeter Wave-band Communications
• SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits
• Data-Driven Time-Frequency Analysis
• Random Sampling of Sparse Trigonometric Polynomials
• Iterative hard thresholding for compressed sensing
• Unsupervised Adaptive Neural Network Regularization for Accelerated Radial Cine MRI
• Channel Estimation for Reconfigurable Intelligent Surface Aided Multi-User mmWave MIMO Systems
• Rapid T2 mapping of mouse heart using the carr–purcell–meiboom–gill sequence and compressed sensing reconstruction
• Stability results for random sampling of sparse trigonometric polynomials
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• The Physics of Compressive Sensing and the Gradient-Based Recovery Algorithms
• TV-min and Greedy Pursuit for Constrained Joint Sparsity and Application to Inverse Scattering
• Compressed Blind De-convolution
• Deterministic Compressed Sensing Matrices from Additive Character Sequences
• Reconstruction of Frequency Hopping Signals From Multi-Coset Samples
• Dictionary-Based Deblurring for Unpaired Data
• Various thresholds for ℓ₁-optimization in compressed sensing
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Image Block Loss Restoration Using Sparsity Pattern as Side Information
• ATP-Net: An Attention-based Ternary Projection Network For Compressed Sensing
• Bayesian Hypothesis Test for Sparse Support Recovery using Belief Propagation
• Compressive sensing based Bayesian sparse channel estimation for OFDM communication systems: high performance and low complexity
• Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
• Knowledge-Informed Neural Network for Complex-Valued SAR Image Recognition
• Pseudo-Random TDM-MIMO FMCW Based Millimeter-Wave Sensing and Communication Integration for UAV Swarm
• Discriminative models for robust image classification
• Simultaneous Orthogonal Matching Pursuit With Noise Stabilization: Theoretical Analysis
• Robust Compressed Sensing and Sparse Coding with the Difference Map
• Density Evolution Analysis of Node-Based Verification-Based Algorithms\n in Compressive Sensing
• Hybrid Beamforming for Massive MIMO - A Survey
• Analysis of Democratic Voting Principles used in Distributed Greedy Algorithms
• Inference of Stochastic Dynamical Systems from Cross-Sectional\n Population Data
• An unsupervised deep learning framework for medical image denoising
• Optimality and computational barriers in variable selection under dependence
• The Sliding Frank-Wolfe Algorithm and its Application to\n Super-Resolution Microscopy
• A Coordinate-wise Optimization Algorithm for Sparse Inverse Covariance Selection
• Random sketching of operators with application to learning preconditioners
• Analysis of The Ratio of ℓ₁ and ℓ₂ Norms in Compressed Sensing
• Deterministic Construction of Binary, Bipolar and Ternary Compressed\n Sensing Matrices
• A Sub-Nyquist Radar Prototype: Hardware and Algorithms
• Scalable Nonlinear Learning with Adaptive Polynomial Expansions
• Efficient iterative thresholding algorithms with functional feedbacks and convergence analysis
• Random linear systems with sparse solutions -- asymptotics and large deviations
• COSPADI: Compressing LLMs via Calibration-Guided Sparse Dictionary Learning
• Channel Estimation for Opportunistic Spectrum Access: Uniform and Random Sensing
• Exact Recovery Conditions for Sparse Representations with Partial Support Information
• Multi-Chirp AFDM for Rydberg Atomic Quantum Receivers: Waveform and Algorithm Design
• Measurement-Adaptive Sparse Image Sampling and Recovery
• Signal Recovery in Uncorrelated and Correlated Dictionaries Using\n Orthogonal Least Squares
• Sparsity in time-frequency representations
• Random Sampling Using Shannon Interpolation and Poisson Summation Formulae
• Sparse Legendre expansions via ℓ₁ minimization
• Mixed Operators in Compressed Sensing
• Convex Optimization without Projection Steps
• Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
• Deep Active Learning Approach to Adaptive Beamforming for mmWave Initial Alignment
• Iterative Hard Thresholding for Compressed Sensing
• CS reconstruction of the speech and musical signals
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Novel Realization of Adaptive Sparse Sensing with Sparse Least Mean Fourth Algorithm
• Tuning Free Orthogonal Matching Pursuit
• A Block Decomposition Algorithm for Sparse Optimization
• Primordial Physics in the Nonlinear Universe: mapping cosmological collider models to weak-lensing observables
• A James-Stein Estimator based Generalized OMP Algorithm for Robust Signal Recovery using Sparse Representation
• Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data
• Change Detection with Sparse Signals using Quantum Designs
• Beam Allocation for Millimeter-Wave MIMO Tracking Systems
• 2D Sparse Signal Recovery via 2D Orthogonal Matching Pursuit
• Efficient Beam Training and Channel Estimation for Millimeter Wave Communications Under Mobility
• Deterministic Construction of Partial Fourier Compressed Sensing Matrices Via Cyclic Difference Sets
• Cooperative Sparsity Pattern Recovery in Distributed Networks Via\n Distributed-OMP
• Compressive sensing: a paradigm shift in signal processing
• A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
• VLSI Friendly Framework for Scalable Video Coding based on Compressed Sensing
• Weighted algorithms for compressed sensing and matrix completion
• Sparse Estimation with Generalized Beta Mixture and the Horseshoe Prior
• Dictionary Learning Using Rank-One Projection (ROP)
• Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints
• Group-based Sparse Representation for Image Compressive Sensing Reconstruction with Non-Convex Regularization
• Distributed Compressive Sensing: Performance Analysis with Diverse Signal Ensembles
• Networked Estimation using Sparsifying Basis Prediction
• Channel Estimation for Flexible Intelligent Metasurfaces: From Model-Based Approaches to Neural Operators
• Learning with Structured Sparsity
• A Class of Novel STAP Algorithms Using Sparse Recovery Technique
• Distributed Compressed Wideband Sensing in Cognitive Radio Sensor Networks
• Spatiotemporal KSVD Dictionary Learning for Online Multi-target Tracking
• Iterative Null-space Projection Method with Adaptive Thresholding in Sparse Signal Recovery and Matrix Completion
• A Fast Non-Gaussian Bayesian Matching Pursuit Method for Sparse\n Reconstruction
• Sparse Recovery from Group Orbits
• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• SparseGAN: Sparse Generative Adversarial Network for Text Generation
• Sparseness helps: Sparsity Augmented Collaborative Representation for Classification
• Newtonalized Orthogonal Matching Pursuit for Linear Frequency Modulated Pulse Frequency Agile Radar
• Multipath Matching Pursuit
• Robust Multi-subspace Analysis Using Novel Column L0-norm Constrained Matrix Factorization
• A Robust Matching Pursuit Algorithm Using Information Theoretic Learning
• Fusion of Greedy Pursuits for Compressed Sensing Signal Reconstruction
• A robust sub-linear time R-FFAST algorithm for computing a sparse DFT
• Reducing ADC Sampling Rate with Compressive Sensing
• Hashing Pursuit for Online Identification of Heavy-Hitters in High-Speed\n Network Streams
• A note relating ridge regression and OLS p-values to preconditioned sparse penalized regression
• Greedy type algorithms for RIP matrices. A study of two selection rules
• Maximum Correntropy Adaptive Filtering Approach for Robust Compressive Sensing Reconstruction
• A Robust Indoor Scene Recognition Method based on Sparse Representation
• Sparse recovery via Orthogonal Least-Squares under presence of Noise
• 1-Bit Compressive Sensing via Approximate Message Passing with Built-in Parameter Estimation
• Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Coded Compressive Sensing: A Compute-and-Recover Approach
• Greedy Subspace Clustering
• Reconstruction of Sub-Nyquist Random Sampling for Sparse and Multi-Band Signals
• A Memristor-Based Optimization Framework for AI Applications
• Density Evolution Analysis of Sparse-Block IDMA
• Secure Transmission for Intelligent Reflecting Surface-Assisted mmWave and Terahertz Systems
• Conditions for Unique Reconstruction of Sparse Signals Using Compressive Sensing Methods
• Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information
• Removing ballistocardiogram (BCG) artifact from full-scalp EEG acquired inside the MR scanner with Orthogonal Matching Pursuit (OMP). [europepmc]
• A Model of Regularization Parameter Determination in Low-Dose X-Ray CT Reconstruction Based on Dictionary Learning. [europepmc]
• A Compressed Sensing-Based Wearable Sensor Network for Quantitative Assessment of Stroke Patients. [europepmc]
• A New Elliptical Model for Device-Free Localization. [europepmc]
• Low-dose CT reconstruction via L1 dictionary learning regularization using iteratively reweighted least-squares. [europepmc]
• When machine vision meets histology: A comparative evaluation of model architecture for classification of histology sections. [europepmc]
• A Novel Partial Discharge Localization Method in Substation Based on a Wireless UHF Sensor Array. [europepmc]
• Electrocardiograph signal denoising based on sparse decomposition. [europepmc]
• Dictionary learning-based reverberation removal enables depth-resolved photoacoustic microscopy of cortical microvasculature in the mouse brain. [europepmc]
• Infrared Image Super Resolution by Combining Compressive Sensing and Deep Learning. [europepmc]
• A super-resolution method-based pipeline for fundus fluorescein angiography imaging. [europepmc]
• A Regularized Weighted Smoothed L ₀ Norm Minimization Method for Underdetermined Blind Source Separation. [europepmc]
• A Comprehensive Survey on Spectrum Sensing in Cognitive Radio Networks: Recent Advances, New Challenges, and Future Research Directions. [europepmc]
• Enhanced Cerenkov luminescence tomography analysis based on Y 2 O 3 :Eu 3+ rare earth oxide nanoparticles. [europepmc]
• Bayesian Compress Sensing Based Countermeasure Scheme Against the Interrupted Sampling Repeater Jamming. [europepmc]
• Compressive Sensing Inference of Neuronal Network Connectivity in Balanced Neuronal Dynamics. [europepmc]
• A Perspective on MR Fingerprinting. [europepmc]
• Combining Denoising Autoencoders and Dynamic Programming for Acoustic Detection and Tracking of Underwater Moving Targets. [europepmc]
• Manifold learning based data-driven modeling for soft biological tissues. [europepmc]
• 3-D compressed sensing optical coherence tomography using predictive coding. [europepmc]
• Compressed Sensing of Extracellular Neurophysiology Signals: A Review. [europepmc]
• Discovery of nonlinear dynamical systems using a Runge-Kutta inspired dictionary-based sparse regression approach. [europepmc]
• Deep Compressive Sensing on ECG Signals with Modified Inception Block and LSTM. [europepmc]
• Motion-compensated T 1 mapping in cardiovascular magnetic resonance imaging: a technical review. [europepmc]
• A compressive hyperspectral video imaging system using a single-pixel detector. [europepmc]

Related

• Exact Recovery of Sparse Signals via Orthogonal Matching Pursuit: How Many Iterations Do We Need?
• Sparse Signals Recovery from Noisy Measurements by Orthogonal Matching Pursuit
• Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
• Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit
• Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information