Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit

2012/02/01 by David L. Donoho, Yaakov Tsaig, Iddo Drori +2 · 1,507 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Compressed sensing #Computer science #Image and Signal Denoising Methods #Linear system #Matching (statistics) #Matching pursuit #Mathematical analysis #Mathematical optimization #Mathematics #Matrix Theory and Algorithms #Sparse and Compressive Sensing Techniques #Statistics #Underdetermined system

paper · doi:10.1109/tit.2011.2173241

published in IEEE Transactions on Information Theory 58(2), 1094-1121 (Institute of Electrical and Electronics Engineers)

openalex publication_date 2012/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Finding the sparsest solution to underdetermined systems of linear equationsy= Φxis NP-hard in general. We show here that for systems with “typical”/“random” Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residualr0=y, at thes-th stage it forms the “matched filter” ΦTrs-1, identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new residual. After a fixed number of stages (e.g., 10), it stops. In contrast to Orthogonal Matching Pursuit (OMP), many coefficients can enter the model at each stage in StOMP while only one enters per stage in OMP; and StOMP takes a fixed number of stages (e.g., 10), while OMP can take many (e.g.,n). We give both theoretical and empirical support for the large-system effectiveness of StOMP. We give numerical examples showing that StOMP rapidly and reliably finds sparse solutions in compressed sensing, decoding of error-correcting codes, and overcomplete representation.

Citations

• Compressed sensing

Cited by

• Sparse Approximation by Semidefinite Programming
• Convergence of the Generalized Alternating Projection Algorithm for Compressive Sensing
• The Convergence Guarantees of a Non-convex Approach for Sparse Recovery
• Greedy Sparse Signal Recovery Algorithm Based on Bit-wise MAP detection
• Semi-supervised Stacked Label Consistent Autoencoder for Reconstruction and Analysis of Biomedical Signals
• SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits
• Joint User Activity and Data Detection in Grant-Free NOMA using Generative Neural Networks
• Greedy metrics in orthogonal greedy learning
• Spark-level sparsity and the ℓ1 tail minimization
• Beer Organoleptic Optimisation: Utilising Swarm Intelligence and Evolutionary Computation Methods
• ATP-Net: An Attention-based Ternary Projection Network For Compressed Sensing
• Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
• Robust Compressed Sensing and Sparse Coding with the Difference Map
• Analysis of Democratic Voting Principles used in Distributed Greedy Algorithms
• Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
• Using the LASSO's Dual for Regularization in Sparse Signal Reconstruction from Array Data
• Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices
• Exact Recovery Conditions for Sparse Representations with Partial Support Information
• Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
• The convergence guarantee of the iterative thresholding algorithm with suboptimal feedbacks for large systems
• CS reconstruction of the speech and musical signals
• Greedy Sparse Signal Reconstruction Using Matching Pursuit Based on Hope-tree
• Collaborative Annotation of Semantic Objects in Images with Multi-granularity Supervisions
• Deep Learning Based Fast Multiuser Detection for Massive Machine-Type Communication
• Multipath Matching Pursuit
• Compressed Sensing and Reconstruction of Unstructured Mesh Datasets
• A comprehensive study of sparse codes on abnormality detection
• Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
• Boosting on the shoulders of giants in quantum device calibration
• Partial Correlation Screening for Estimating Large Precision Matrices, with Applications to Classification
• Sparse Solution of Underdetermined Linear Equations via Adaptively Iterative Thresholding
• A Generalized LDPC Framework for Robust and Sublinear Compressive Sensing
• Adaptive Iterative Soft-Thresholding Algorithm with the Median Absolute Deviation
• Learning and approximation capability of orthogonal super greedy algorithm
• Beamforming for Multiuser Massive MIMO Systems: Digital versus Hybrid Analog-Digital
• Greedy Criterion in Orthogonal Greedy Learning
• Coherence-based Partial Exact Recovery Condition for OMP/OLS
• Sampling Requirements and Accelerated Schemes for Sparse Linear Regression with Orthogonal Least-Squares
• RODEO: Robust DE-aliasing autoencOder for Real-time Medical Image Reconstruction
• Matrix of Polynomials Model based Polynomial Dictionary Learning Method for Acoustic Impulse Response Modeling
• Spark Level Sparsity and the ℓ₁ Tail Minimization
• Deep Learning Techniques for Compressive Sensing-Based Reconstruction and Inference -- A Ubiquitous Systems Perspective
• Generalized orthogonal matching pursuit for multiple measurements - A structural approach
• The finite steps of convergence of the fast thresholding algorithms with feedbacks
• Analysis of Gaussian Spatial Models with Covariate Measurement Error
• Active Deep Learning for Classification of Hyperspectral Images
• Recursive Sparse Parameter Identification of Multivariate ARMAX Systems with Non-stationary Observations and Colored Noise
• Compressed Sensing in Astronomy
• A Method for Robust Online Classification using Dictionary Learning:\n Development and Assessment for Monitoring Manual Material Handling Activities\n Using Wearable Sensors
• A Novel Efficient Approach with Data-Adaptive Capability for OMP-based Sparse Subspace Clustering
• A wavelet-based single-view reconstruction approach for cone beam x-ray luminescence tomography imaging. [europepmc]
• An Online Dictionary Learning-Based Compressive Data Gathering Algorithm in Wireless Sensor Networks. [europepmc]
• Cell Selection Technique for Millimeter-Wave Cellular Systems with Hybrid Beamforming. [europepmc]
• Reconstruction of Complex Network based on the Noise via QR Decomposition and Compressed Sensing. [europepmc]
• A Two-Stage Reconstruction Processor for Human Detection in Compressive Sensing CMOS Radar. [europepmc]
• Improving mesoscopic fluorescence molecular tomography via preconditioning and regularization. [europepmc]
• A Prediction-Based Spatial-Spectral Adaptive Hyperspectral Compressive Sensing Algorithm. [europepmc]
• Adaptive Compressive Sensing and Data Recovery for Periodical Monitoring Wireless Sensor Networks. [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]
• CBN-VAE: A Data Compression Model with Efficient Convolutional Structure for Wireless Sensor Networks. [europepmc]
• Low Energy Consumption Compressed Spectrum Sensing Based on Channel Energy Reconstruction in Cognitive Radio Network. [europepmc]
• Quantifying the Computational Efficiency of Compressive Sensing in Smart Water Network Infrastructures. [europepmc]
• Fuzzy Adaptive-Sampling Block Compressed Sensing for Wireless Multimedia Sensor Networks. [europepmc]
• GWRA: grey wolf based reconstruction algorithm for compressive sensing signals. [europepmc]
• Deterministic clustering based compressive sensing scheme for fog-supported heterogeneous wireless sensor networks. [europepmc]
• Highly Efficient Spatial-Temporal Correlation Basis for 5G IoT Networks. [europepmc]
• A novel hyperspectral compressive sensing framework of plant leaves based on multiple arbitrary-shape regions of interest. [europepmc]
• Compressive sensing based secure data aggregation scheme for IoT based WSN applications. [europepmc]
• A hybrid with distributed pooling blockchain protocol for image storage. [europepmc]
• Non-Contact Detection of Vital Signs Based on Improved Adaptive EEMD Algorithm (July 2022). [europepmc]
• Feasibility of a Real-Time Embedded Hyperspectral Compressive Sensing Imaging System. [europepmc]
• IEF-CSNET: Information Enhancement and Fusion Network for Compressed Sensing Reconstruction. [europepmc]
• Pilot Lightweight Denoising Algorithm for Multiple Sclerosis on Spine MRI. [europepmc]
• Research on deep unfolding network reconstruction method based on scalable sampling of transient signals. [europepmc]

Related

• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• Fast Sparse Decomposition by Iterative Detection-Estimation
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• Efficient Batched CPU/GPU Implementation of Orthogonal Matching Pursuit for Python
• Lifting ℓ₁-optimization strong and sectional thresholds