Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

DOI10.1109/TIT.2007.909108zbMath1288.94022WikidataQ56698225 ScholiaQ56698225MaRDI QIDQ3549018

Joel A. Tropp, Anna C. Gilbert

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Measures of association (correlation, canonical correlation, etc.) (62H20) Identification in stochastic control theory (93E12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

Pseudo-inverses of difference matrices and their application to sparse signal approximation, LOL selection in high dimension, Iteratively weighted thresholding homotopy method for the sparse solution of underdetermined linear equations, MOEA/D with chain-based random local search for sparse optimization, Surface inpainting with sparsity constraints, A model of regularization parameter determination in low-dose X-ray CT reconstruction based on dictionary learning, An orthogonal method for measurement matrix optimization, Compressed blind signal reconstruction model and algorithm, Design of wideband fractional-order differentiator using interlaced sampling method, Point source super-resolution via non-convex \(L_1\) based methods, Instrumental variable-based OMP identification algorithm for Hammerstein systems, Robust sparse phase retrieval made easy, A matching pursuit approach to solenoidal filtering of three-dimensional velocity measurements, A new sensor selection scheme for Bayesian learning based sparse signal recovery in WSNs, Prior model identification during subsurface flow data integration with adaptive sparse representation techniques, The essential ability of sparse reconstruction of different compressive sensing strategies, Waveform design and high-resolution imaging of cognitive radar based on compressive sensing, Sparse microwave imaging: principles and applications, Sparse SAR imaging based on \(L_{1/2}\) regularization, Improved FOCUSS method for reconstruction of cluster structured sparse signals in radar imaging, Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain, A novel cognitive ISAR imaging method with random stepped frequency chirp signal, MIMO radar imaging based on smoothed \(l_0\) norm, Backtracking-based simultaneous orthogonal matching pursuit for sparse unmixing of hyperspectral data, PROMP: a sparse recovery approach to lattice-valued signals, Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP, Approximation accuracy, gradient methods, and error bound for structured convex optimization, Iterative nearest neighbors, Relaxed sparse eigenvalue conditions for sparse estimation via non-convex regularized regression, Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions, Grouping strategies and thresholding for high dimensional linear models, Sparsity enabled cluster reduced-order models for control, RBF-network based sparse signal recovery algorithm for compressed sensing reconstruction, Adaptive projected gradient thresholding methods for constrained \(l_0\) problems, Comparison of parametric sparse recovery methods for ISAR image formation, Robust visual tracking with structured sparse representation appearance model, Exact recovery of sparse multiple measurement vectors by \(l_{2,p}\)-minimization, Wavelet compressive sampling signal reconstruction using upside-down tree structure, Kernel-based sparse representation for gesture recognition, A classification-oriented dictionary learning model: explicitly learning the particularity and commonality across categories, Sparse Legendre expansions via \(\ell_1\)-minimization, A novel sparsity reconstruction method from Poisson data for 3D bioluminescence tomography, A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit, Model reduction method using variable-separation for stochastic saddle point problems, From compression to compressed sensing, Improved stability conditions of BOGA for noisy block-sparse signals, A two-level method for sparse time-frequency representation of multiscale data, 2D sparse signal recovery via 2D orthogonal matching pursuit, Accelerating near-field 3D imaging approach for joint high-resolution imaging and phase error correction, Sparsity and incoherence in orthogonal matching pursuit, Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework, A computational study of the role of spatial receptive field structure in processing natural and non-natural scenes, Particle swarm optimization of compression measurement for signal detection, Roles of clustering coefficient for the network reconstruction, Sparse time-frequency representation of nonlinear and nonstationary data, A sharp nonasymptotic bound and phase diagram of \(L_{1/2}\) regularization, Efficient projected gradient methods for cardinality constrained optimization, Compressive sensing using chaotic sequence based on Chebyshev map, Noise folding in completely perturbed compressed sensing, Individual-specific, sparse inverse covariance estimation in generalized estimating equations, Accelerating a Gibbs sampler for variable selection on genomics data with summarization and variable pre-selection combining an array DBMS and R, Bayesian signal detection with compressed measurements, Minimization of transformed \(L_1\) penalty: theory, difference of convex function algorithm, and robust application in compressed sensing, GAITA: a Gauss-Seidel iterative thresholding algorithm for \(\ell_q\) regularized least squares regression, Sparse decomposition by iterating Lipschitzian-type mappings, Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset, Sparse signal recovery using a new class of random matrices, Surveying and comparing simultaneous sparse approximation (or group-lasso) algorithms, Two-dimensional random projection, Sparsity in time-frequency representations, Compressed sensing with coherent and redundant dictionaries, Sparse approximate solution of partial differential equations, Combinatorial sublinear-time Fourier algorithms, Mean squared error bounds for the Rangan-Goyal soft thresholding algorithm, On performance of greedy algorithms, Adaptive compressive learning for prediction of protein-protein interactions from primary sequence, Recovery of seismic wavefields by an \(l_{q}\)-norm constrained regularization method, Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem, Large-scale hyperspectral image compression via sparse representations based on online learning, Model recovery for Hammerstein systems using the hierarchical orthogonal matching pursuit method, Enhancing sparsity of Hermite polynomial expansions by iterative rotations, Sparse representation based binary hypothesis model for hyperspectral image classification, \(\ell_1\)- and \(\ell_2\)-norm joint regularization based sparse signal reconstruction scheme, Underdetermined separation of speech mixture based on sparse Bayesian learning, A novel STAP algorithm for airborne MIMO radar based on temporally correlated multiple sparse Bayesian learning, Iterative hard thresholding for compressed sensing, Discovering governing equations from data by sparse identification of nonlinear dynamical systems, DFT spectrum-sparsity-based quasi-periodic signal identification and application, Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery, Hard thresholding pursuit algorithms: number of iterations, Fast global convergence of gradient methods for high-dimensional statistical recovery, A constrained optimization reformulation and a feasible descent direction method for \(L_{1/2}\) regularization, GPU accelerated greedy algorithms for compressed sensing, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit, Compressive sensing for subsurface imaging using ground penetrating radar, DOA estimation with a rotational uniform linear array (RULA) and unknown spatial noise covariance, Compressive sensing-based wind speed estimation for low-altitude wind-shear with airborne phased array radar, On a simple derivation of the complementary matching pursuit, A new result on recovery sparse signals using orthogonal matching pursuit, Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method, Fast sparse reconstruction: Greedy inverse scale space flows, Average Performance of the Sparsest Approximation Using a General Dictionary, Estimation of block sparsity in compressive sensing, Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction, Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization, Fast Phase Retrieval from Local Correlation Measurements, A survey on compressive sensing: classical results and recent advancements, A Survey of Compressed Sensing, Compressed Sensing, Sparse Inversion, and Model Mismatch, Structured Sparsity: Discrete and Convex Approaches, Sparse signal recovery via non-convex optimization and overcomplete dictionaries, Nonlinear Variable Selection via Deep Neural Networks, Deterministic construction of compressed sensing matrices with characters over finite fields, Discriminative Sparse Representations, Sparsity Constrained Estimation in Image Processing and Computer Vision, Fixed-Size Confidence Regions in High-Dimensional Sparse Linear Regression Models, Exact reconstruction of extended exponential sums using rational approximation of their Fourier coefficients, A Greedy Algorithm for Sparse Precision Matrix Approximation, Quantifying Statistical Interdependence by Message Passing on Graphs—Part II: Multidimensional Point Processes, Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases, Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements, The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials, A Generalized Class of Hard Thresholding Algorithms for Sparse Signal Recovery, \(\mathrm{L_1RIP}\)-based robust compressed sensing, On recovery of discrete time signals with single-point spectrum degeneracy, Framework for segmented threshold \(\ell_0\) gradient approximation based network for sparse signal recovery, Heuristics for Finding Sparse Solutions of Linear Inequalities, Greedy Variable Selection for High-Dimensional Cox Models, Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping, An outlier detection and recovery method based on moving least squares quasi-interpolation scheme and \(\text{ł}_0\)-minimization problem, Sparse signal reconstruction via collaborative neurodynamic optimization, Smoothing inertial neurodynamic approach for sparse signal reconstruction via \(L_p\)-norm minimization, Dynamic reconstruction and data reconstruction for subsampled or irregularly sampled data, Locality constrained dictionary learning for human behaviour recognition, Weighted singular value decomposition basis of Szegő kernel and its applications to signal reconstruction and denoising, Kernel functions embed into the autoencoder to identify the sparse models of nonlinear dynamics, Unnamed Item, Classifier-based adaptive polynomial chaos expansion for high-dimensional uncertainty quantification, A Novel Variable-Separation Method Based on Sparse and Low Rank Representation for Stochastic Partial Differential Equations, Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems, Heavy-ball-based hard thresholding algorithms for sparse signal recovery, Nonconvex \(\ell_p-\alpha\ell_q\) minimization method and \(p\)-RIP condition for stable recovery of approximately \(k\)-sparse signals, Second order self-adaptive dynamical system for sparse signal reconstruction and applications to image recovery, A non-convex piecewise quadratic approximation of \(\ell_0\) regularization: theory and accelerated algorithm, A reduced half thresholding algorithm, Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms, Reconstruction of sparse recurrent connectivity and inputs from the nonlinear dynamics of neuronal networks, Scaled proximal gradient methods for sparse optimization problems, On optimal solutions of the constrained ℓ ₀ regularization and its penalty problem, Weighted ${\ell}_{{1}}$-minimization for sparse recovery under arbitrary prior information, Flavors of Compressive Sensing, Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets, Unnamed Item, Unnamed Item, Kernelized Elastic Net Regularization: Generalization Bounds, and Sparse Recovery, Improving the Incoherence of a Learned Dictionary via Rank Shrinkage, Combination of anisotropic diffusion and non-subsampled shearlet transform for image denoising, Optimized Sampling for Multiscale Dynamics, Reconstruction of Smooth 3D Color Functions from Keypoints: Application to Lossy Compression and Exemplar-Based Generation of Color LUTs, Orthogonal Nonnegative Tucker Decomposition, Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control, CHAOTIC ANALOG-TO-INFORMATION CONVERSION: PRINCIPLE AND RECONSTRUCTABILITY WITH PARAMETER IDENTIFIABILITY, An adaptive inverse scale space method for compressed sensing, The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty, A Tight Bound of Hard Thresholding, Adaptive surface-related multiple subtraction using sparse norm minimization method, Unnamed Item, Chaotic Binary Sensing Matrices, The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy, Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems, Discussion on “Two-Stage Procedures for High-Dimensional Data” by Makoto Aoshima and Kazuyoshi Yata, COMPRESSED SENSING BY ITERATIVE THRESHOLDING OF GEOMETRIC WAVELETS: A COMPARING STUDY, CURVELET-WAVELET REGULARIZED SPLIT BREGMAN ITERATION FOR COMPRESSED SENSING, Sequential Lasso Cum EBIC for Feature Selection With Ultra-High Dimensional Feature Space, Deterministic Construction of Compressed Sensing Matrices from Codes, Solving inverse problems using data-driven models, Sparse Inverse Problems over Measures: Equivalence of the Conditional Gradient and Exchange Methods, Binary sparse signal recovery with binary matching pursuit ^*, Robust network structure reconstruction based on Bayesian compressive sensing, Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark, Perturbation Analysis of Orthogonal Least Squares, Unnamed Item, Unnamed Item, A time continuation based fast approximate algorithm for compressed sensing related optimization, Where did the tumor start? An inverse solver with sparse localization for tumor growth models, Learning Optimal Forecast Aggregation in Partial Evidence Environments, Minimization of $\ell_{1-2}$ for Compressed Sensing, A Plaintext-Related Image Encryption Algorithm Based on Compressive Sensing and a Novel Hyperchaotic System, Compressive Sampling for Energy Spectrum Estimation of Turbulent Flows, Sequential Active Learning of Low-Dimensional Model Representations for Reliability Analysis, An Algorithm Solving Compressive Sensing Problem Based on Maximal Monotone Operators, Compressed sensing reconstruction using expectation propagation, Data-Driven Reconstruction and Encoding of Sparse Stimuli across Convergent Sensory Layers from Downstream Neuronal Network Dynamics, Solving Basis Pursuit, Robust Data Assimilation Using $L_1$ and Huber Norms, Research on IQ imbalance error of orthogonal alternating sampling, Unconstrained \(\ell_1\)-\(\ell_2\) minimization for sparse recovery via mutual coherence, Sparse representation for blind spectrum sensing in cognitive radio: a compressed sensing approach, Model recovery for multi-input signal-output nonlinear systems based on the compressed sensing recovery theory, State estimation with limited sensors -- a deep learning based approach, Sparse Bayesian learning for network structure reconstruction based on evolutionary game data, Post-model-selection inference in linear regression models: an integrated review, Improved sparse Fourier approximation results: Faster implementations and stronger guarantees, Compressed sensing by inverse scale space and curvelet thresholding, Distribution agnostic Bayesian compressive sensing with incremental support estimation, Sparse signal recovery via generalized Gaussian function, Three-Dimensional Inverse Transport Solver Based on Compressive Sensing Technique, Synchrotron radiation-based \(l_1\)-norm regularization on micro-CT imaging in shale structure analysis, Gradient projection Newton pursuit for sparsity constrained optimization, Adaptive step-size matching pursuit algorithm for practical sparse reconstruction, On the number of iterations for convergence of CoSaMP and subspace pursuit algorithms, Adaptive multi-penalty regularization based on a generalized Lasso path, Newton method for \(\ell_0\)-regularized optimization, Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields, Smoothing inertial projection neural network for minimization \(L_{p-q}\) in sparse signal reconstruction, Generalized sparse recovery model and its neural dynamical optimization method for compressed sensing, Arbitrary block-sparse signal reconstruction based on incomplete single measurement vector, Performance analysis of the compressed distributed least squares algorithm, The finite steps of convergence of the fast thresholding algorithms with \(f\)-feedbacks in compressed sensing, Global and local structure preserving sparse subspace learning: an iterative approach to unsupervised feature selection, Newton-type optimal thresholding algorithms for sparse optimization problems, Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm, Iterative hard thresholding for compressed data separation, Iterative identification for multiple-input systems with time-delays based on greedy pursuit and auxiliary model, Model's sparse representation based on reduced mixed GMsFE basis methods, A simple homotopy proximal mapping algorithm for compressive sensing, Deterministic construction of compressed sensing matrices from constant dimension codes, Adaptive decomposition-based evolutionary approach for multiobjective sparse reconstruction, A Barzilai-Borwein gradient projection method for sparse signal and blurred image restoration, Geological facies recovery based on weighted \(\ell_1\)-regularization, Cluster sparsity field: an internal hyperspectral imagery prior for reconstruction, Recovering an unknown signal completely submerged in strong noise by a new stochastic resonance method, Posterior information-based image measurement matrix optimization, Bipolar measurement matrix using chaotic sequence, Sparse signal recovery via ECME thresholding pursuits, Block orthogonal greedy algorithm for stable recovery of block-sparse signal representations, Stability of 1-bit compressed sensing in sparse data reconstruction, Some greedy algorithms for sparse polynomial chaos expansions, Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing, Sparse polynomial chaos expansions via compressed sensing and D-optimal design, An efficient adaptive forward-backward selection method for sparse polynomial chaos expansion, Variance-based adaptive sequential sampling for polynomial chaos expansion, Compressing sensing based source localization for controlled acoustic signals using distributed microphone arrays, Spectral compressive sensing, Data-driven time-frequency analysis, Convergence of a data-driven time-frequency analysis method, Sparse approximate reconstruction decomposed by two optimization problems, Maximum correntropy adaptation approach for robust compressive sensing reconstruction, An algebraic perspective on integer sparse recovery, Functional concurrent linear regression model for spatial images, Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes, Traditional and recent approaches in background modeling for foreground detection: an overview, A novel T-S fuzzy systems identification with block structured sparse representation, Dynamic T-S Fuzzy Systems Identification Based on Sparse Regularization, On rank awareness, thresholding, and MUSIC for joint sparse recovery, Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation, A novel design of sparse prototype filter for nearly perfect reconstruction cosine-modulated filter banks, Sliding-MOMP based channel estimation scheme for ISDB-T systems, An efficient algorithm for learning dictionary under coherence constraint, Peeling decoding of LDPC codes with applications in compressed sensing, Compressive sensing in signal processing: algorithms and transform domain formulations, A novel 1D hybrid chaotic map-based image compression and encryption using compressed sensing and Fibonacci-Lucas transform, Incoherent dictionary learning method based on unit norm tight frame and manifold optimization for sparse representation, An effective algorithm for the spark of sparse binary measurement matrices, A unified primal dual active set algorithm for nonconvex sparse recovery, Analysis of compressed distributed adaptive filters, MRI simulation-based evaluation of an efficient under-sampling approach, Nonconvex sorted \(\ell_1\) minimization for sparse approximation, An efficient privacy-preserving compressive data gathering scheme in WSNs, Model recovery for Hammerstein systems using the auxiliary model based orthogonal matching pursuit method, A new smoothed L0 regularization approach for sparse signal recovery, Relation of Average Error in Prolate Spheroidal Wave Functions Algorithm for Bandlimited Functions Approximation to Radius of Information, A physics-constrained data-driven approach based on locally convex reconstruction for noisy database, Deterministic constructions of compressed sensing matrices based on codes, Image reconstruction based on improved block compressed sensing, Sparse Sensor Placement Optimization for Classification, Structured iterative hard thresholding with on- and off-grid applications, Lattices from tight frames and vertex transitive graphs, Partial gradient optimal thresholding algorithms for a class of sparse optimization problems, Image encryption using sparse coding and compressive sensing, Weighted thresholding homotopy method for sparsity constrained optimization, Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit, sampling based automatic modulation classifier, A sparse signal reconstruction method based on improved double chains quantum genetic algorithm, A reweighted symmetric smoothed function approximating \(L_0\)-norm regularized sparse reconstruction method, A Lagrange-Newton algorithm for sparse nonlinear programming, Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems, Region-based image-fusion framework for compressive imaging, Preconditioning for orthogonal matching pursuit with noisy and random measurements: the Gaussian case, A convex relaxation framework consisting of a primal-dual alternative algorithm for solving \(\ell_0\) sparsity-induced optimization problems with application to signal recovery based image restoration, Alternating direction method of multipliers for solving dictionary learning models, Sparse recovery of sound fields using measurements from moving microphones, Three stochastic measurement schemes for direction-of-arrival estimation using compressed sensing method, The sparsest solution to the system of absolute value equations, A compressed sampling receiver based on modulated wideband converter and a parameter estimation algorithm for fractional bandlimited LFM signals