Stable signal recovery from incomplete and inaccurate measurements
2006/03/01 by Emmanuel J. Candès, Justin K. Romberg, Justin Romberg +1 · 263 citations
Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Mathematical Analysis and Transform Methods #Image and Signal Denoising Methods
paper · doi:10.1002/cpa.20124
Abstract
Abstract Suppose we wish to recover a vector x 0 ∈ ℝ 𝓂 (e.g., a digital signal or image) from incomplete and contaminated observations y = A x 0 + e ; A is an 𝓃 × 𝓂 matrix with far fewer rows than columns (𝓃 ≪ 𝓂) and e is an error term. Is it possible to recover x 0 accurately based on the data y ? To recover x 0 , we consider the solution x # to the 𝓁 1 ‐regularization problem where ϵ is the size of the error term e . We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x 0 is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A 's provided that the number of nonzeros of x 0 is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x 0 ; then stable recovery occurs for almost any set of 𝓃 coefficients provided that the number of nonzeros is of the order of 𝓃/(log 𝓂) 6 . In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.
Cited by
- Recovering Compressively Sampled Signals Using Partial Support Information
- First-Principles Lattice Dynamics Method for Strongly Anharmonic Crystals
- Quantum sensing
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- The Dantzig selector: Statistical estimation when p is much larger than n
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- ST-DDA: Dynamic Channel Estimation in the Doppler-Delay-Angle Domain via Sparse Subspace Tracking for TDD Systems
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Sparse Approximation by Semidefinite Programming
- NeuralChaos: Optimal Adapted Approximation of Square Integrable Predictable Processes
- Stable and robust ℓp-constrained compressive sensing recovery via robust width property
- Preconditioned training of normalizing flows for variational inference in inverse problems
- Compressive Sampling Using EM Algorithm
- Robust Recovery of Signals From a Structured Union of Subspaces
- Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
- Sparse System Identification in Pairs of FIR and TM Bases
- Joint Beam Training and Positioning For Intelligent Reflecting Surfaces Assisted Millimeter Wave Communications
- Regularization in High-Dimensional Regression and Classification via\n Random Matrix Theory
- Deep Sparse Coding Using Optimized Linear Expansion of Thresholds
- A general framework of rotational sparse approximation in uncertainty quantification
- An inverse problem for the wave equation with one measurement and the pseudorandom noise
- Segment-Sliding Reconstruction of Pulsed Radar Echoes with Sub-Nyquist Sampling
- Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
- On the ℓ^∞-norms of the Singular Vectors of Arbitrary Powers of a Difference Matrix with Applications to Sigma-Delta Quantization
- CT Image Reconstruction in a Low Dimensional Manifold
- Hidden cliques and the certification of the restricted isometry property
- Compressed Sensing with Deep Image Prior and Learned Regularization
- Nonlinear frames and sparse reconstructions in Banach spaces
- Stochastic collocation methods via minimization of Transformed L1 penalty
- Insight into Primal Augmented Lagrangian Multilplier Method
- Extension of Sparse Randomized Kaczmarz Algorithm for Multiple\n Measurement Vectors
- Weak Stability of ℓ1-minimization Methods in Sparse Data Reconstruction
- Phase-space entropy at acquisition reflects downstream learnability
- Deep Learning-Guided Image Reconstruction from Incomplete Data
- Do Generalized-Gamma Scale Mixtures of Normals Fit Large Image Datasets?
- Ramanujan sums in signal recovery and uncertainty principle inequalities
- From STLS to Projection-based Dictionary Selection in Sparse Regression for System Identification
- Towards Machine Intelligence
- On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Rates and architectures for learning geometrically non-trivial operators
- Fast L1-L2 minimization via a proximal operator
- Large-aperture computational single-sensor microwave imager using 1-bit programmable coding metasurface at single frequency
- Adaptive sampling using variational autoencoder and reinforcement learning
- Multichannel group sparsity methods for compressive channel estimation in doubly selective multicarrier MIMO systems (extended version)
- Signal Recovery from Incomplete and Inaccurate Measurements via Regularized Orthogonal Matching Pursuit
- Bayesian Massive MIMO Channel Estimation with Parameter Estimation Using Low-Resolution ADCs
- Compressed Sensing using Generative Models
- Solving Tall Dense Linear Programs in Nearly Linear Time
- Compressed sensing in the quaternion algebra
- Compressive Spectrum Sensing for Cognitive Radio Networks
- Sparse regression with highly correlated predictors
- Universal Rate-Efficient Scalar Quantization
- cryoSENSE: Compressive Sensing Enables High-throughput Microscopy with Sparse and Generative Priors on the Protein Cryo-EM Image Manifold
- Spectrum of normal operators that generate certain scalable iterative systems
- Dynamical systems and forward-backward algorithms associated with the\n sum of a convex subdifferential and a monotone cocoercive operator
- An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and\n Related Problems
- Random Search Algorithms for the Sparse Null Vector Problem
- Sparse stabilization of mean-field agent dynamics through a three-operator splitting method
- All-or-nothing statistical and computational phase transitions in sparse\n spiked matrix estimation
- Sparse Recovery by Non-convex Optimization -- Instance Optimality
- A problem dependent analysis of SOCP algorithms in noisy compressed sensing
- Exclusive Group Lasso for Structured Variable Selection
- Bayesian Compressed Regression
- Optimization landscape of ℓ0-Bregman relaxations
- Constrained Shadow Tomography for Molecular Simulation on Quantum Devices
- How to generate accurate continuous thermal regimes from sparse but regular temperature measurements
- Plug-and-Play Algorithms for Large-scale Snapshot Compressive Imaging
- Reconstruction of Ordinary Differential Equations From Time Series Data
- Adaptive Restart for Accelerated Gradient Schemes
- Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
- Bayesian compressed sensing with new sparsity-inducing prior
- An efficient proximal algorithm for squared L1 over L2 regularized sparse recovery
- Atomic norm denoising with applications to line spectral estimation
- Some smooth divergences for ℓ1-approximations
- Refined additive uncertainty principle
- L1-norm Regularized Indefinite Kernel Logistic Regression
- Sparse Isotropic Regularization for Spherical Harmonic Representations of Random Fields on the Sphere
- Weighed l1 on the simplex: Compressive sensing meets locality
- A performance analysis framework for SOCP algorithms in noisy compressed sensing
- Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
- Suprema of Chaos Processes and the Restricted Isometry Property
- InstaHide: Instance-hiding Schemes for Private Distributed Learning
- 1-Bit Compressive Sensing for Efficient Federated Learning Over the Air
- Minimization of Transformed L1 Penalty: Closed Form Representation and Iterative Thresholding Algorithms
- Support Recovery of Sparse Signals
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
- On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
- Structure dependent sampling in compressed sensing: theoretical\n guarantees for tight frames
- An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
- Single-pixel imaging via compressive sampling
- Atomic Norm Denoising With Applications to Line Spectral Estimation
- Leveraging Diversity and Sparsity in Blind Deconvolution
- Iterative hard thresholding for compressed sensing
- Robust sparse recovery with sparse Bernoulli matrices via expanders
- Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints
- L1-norm minimization for quaternion signals
- A Method for Finding Structured Sparse Solutions to Non-negative Least Squares Problems with Applications
- Eigenmatrix for unstructured sparse recovery
- Constant-Expansion Suffices for Compressed Sensing with Generative Priors
- Algebraic compressed sensing
- Compressed sensing for body MRI
- Adaptive compressed sensing - a new class of self-organizing coding models for neuroscience
- Optimal RIP bounds for sparse signals recovery via ℓ minimization
- Recovery of signals under the condition on RIC and ROC via prior support information
- Stability results for random sampling of sparse trigonometric polynomials
- Optimized Compressed Sensing via Incoherent Frames Designed by Convex Optimization
- A Theoretical Analysis of Sparse Recovery Stability of Dantzig Selector and LASSO
- Achieving the Scaling Law of SNR-Monitoring in Dynamic Wireless Networks
- Exact Reconstruction using Beurling Minimal Extrapolation
- Improving Network Slimming with Nonconvex Regularization
- New analysis of manifold embeddings and signal recovery from compressive measurements
- Fast Image Recovery Using Variable Splitting and Constrained Optimization
- A Dual Symmetric Gauss-Seidel Alternating Direction Method of Multipliers for Hyperspectral Sparse Unmixing
- Convergence of a Relaxed Variable Splitting Coarse Gradient Descent\n Method for Learning Sparse Weight Binarized Activation Neural Networks
- Computational methods for large-scale inverse problems: a survey on hybrid projection methods
- Limited Tomography Reconstruction via Tight Frame and Sinogram Extrapolation
- Balanced conic rectified flow
- Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
- Image Block Loss Restoration Using Sparsity Pattern as Side Information
- Instance optimality in phase retrieval
- Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
- One-bit compressive sensing with norm estimation
- Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
- Joint Signal Recovery and Uncertainty Quantification via the Residual Prior Transform
- Multi-Label Prediction via Compressed Sensing
- A Convexly Constrained LiGME Model and Its Proximal Splitting Algorithm
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Majority Vote Compressed Sensing
- Super-resolution by means of Beurling minimal extrapolation
- Guarantees for Greedy Maximization of Non-submodular Functions with Applications
- Spectral subspace extraction via incoherent quantum phase estimation
- Performance Analysis of Spectral Clustering on Compressed, Incomplete and Inaccurate Measurements
- Exploiting Model Sparsity in Adaptive MPC: A Compressed Sensing Viewpoint
- Recovery of Integer Images from Limited DFT Measurements with Lattice Methods
- Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information
- Simplifying Optimal Transport through Schatten-p Regularization
- Do Subsampled Newton Methods Work for High-Dimensional Data?
- Sparse Phase Retrieval: Convex Algorithms and Limitations
- Matrix-free Interior Point Method for Compressed Sensing Problems
- Density Evolution Analysis of Node-Based Verification-Based Algorithms\n in Compressive Sensing
- Analysis of Democratic Voting Principles used in Distributed Greedy Algorithms
- Universality in Learning from Linear Measurements
- Multivariate sparse interpolation using randomized Kronecker\n substitutions
- Estimation in exponential family Regression based on linked data contaminated by mismatch error
- Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
- Rare-Allele Detection Using Compressed Se(que)nsing
- Task Vectors, Learned Not Extracted: Performance Gains and Mechanistic Insight
- Multi-Processor Approximate Message Passing Using Lossy Compression
- Non-convex Fraction Function Penalty: Sparse Signals Recovered from Quasi-linear Systems
- Sparsest solutions of underdetermined linear systems via <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>ℓ</mml:mi><mml:mi>q</mml:mi></mml:msub></mml:math>-minimization for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.gif" overflow="scroll"><mml:mn>0</mml:mn><mml:mo><</mml:mo><mml:mi>q</mml:mi><mml:mo>⩽</mml:mo><mml:mn>1</mml:mn></mml:math>
- Sharp RIP bound for sparse signal and low-rank matrix recovery
- Recovery analysis for weighted ℓ1-minimization using the null space property
- Projection & Probability-Driven Black-Box Attack
- Efficient iterative thresholding algorithms with functional feedbacks and convergence analysis
- Compressive Sensing with Local Geometric Features
- A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm
- Super-Resolution of Brain MRI Images using Overcomplete Dictionaries and Nonlocal Similarity
- Deep(er) Learning
- Inverse Potential Problems for Divergence of Measures with Total\n Variation Regularization
- Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
- Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
- Super-resolution techniques to simulate electronic spectra of large molecular systems
- Exact recoverability from dense corrupted observations via L1 minimization
- The Fourier ratio: A unifying measure of complexity for recovery, localization, and learning
- Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes
- Sparsity in time-frequency representations
- A simple proof that random matrices are democratic
- PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
- Sparse Legendre expansions via ℓ1 minimization
- Mixed Operators in Compressed Sensing
- Fast L1-Minimization Algorithms For Robust Face Recognition
- Multidimensional Chebyshev spaces, hierarchy of infinite-dimensional spaces and Kolmogorov-Gelfand widths
- Clustered Sparsity and Separation of Cartoon and Texture
- A Scale Invariant Approach for Sparse Signal Recovery
- Hyperspectral Unmixing Overview: Geometrical, Statistical, and Sparse\n Regression-Based Approaches
- On Maximization of Weakly Modular Functions: Guarantees of Multi-stage\n Algorithms, Tractability, and Hardness
- Compressive Sensing of Color Images Using Nonlocal Higher Order Dictionary
- Iterative Hard Thresholding for Compressed Sensing
- Low rank matrix recovery from Clifford orbits
- A Weighted Difference of Anisotropic and Isotropic Total Variation for Relaxed Mumford-Shah Color and Multiphase Image Segmentation
- Sparsity estimation in compressive sensing with application to MR images
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Sparsity Lower Bounds for Dimensionality Reducing Maps
- High-Quality Tomographic Image Reconstruction Integrating Neural Networks and Mathematical Optimization
- Convolutional Dictionary Learning in Hierarchical Networks
- Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance
- Lower Bounds for Compressed Sensing with Generative Models
- Learning functions through Diffusion Maps
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
- Improved bounds for the RIP of Subsampled Circulant matrices
- On the Certification of the Restricted Isometry Property
- Stable Principal Component Pursuit
- Early Classification of Time Series is Meaningful
- MemeSequencer: Sparse Matching for Embedding Image Macros
- Functional Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
- Capacity Scaling of Massive MIMO in Strong Spatial Correlation Regimes
- Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
- New Analysis of Manifold Embeddings and Signal Recovery from Compressive\n Measurements
- Learning Functions of Few Arbitrary Linear Parameters in High Dimensions
- Recovery Guarantees for Compressible Signals with Adversarial Noise
- A Critical Review of LASSO and Its Derivatives for Variable Selection Under Dependence Among Covariates
- Detection-Directed Sparse Estimation using Bayesian Hypothesis Test and Belief Propagation
- Structure-Blind Signal Recovery
- Highly robust error correction by convex programming
- Compressive Sensing over the Grassmann Manifold: a Unified Geometric Framework
- Cooperative Sparsity Pattern Recovery in Distributed Networks Via\n Distributed-OMP
- Polarization Reconfigurable Transmit-Receive Beam Alignment with Interpretable Transformer
- Nonuniqueness of Solutions of a Class of ℓ0-minimization Problems
- Compressive sensing: a paradigm shift in signal processing
- A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
- Compressive Sensing Based Opportunistic Protocol for Throughput Improvement in Wireless Networks
- Iterative ℓ1 minimization for non-convex compressed sensing
- The Cramer-Rao Bound for Sparse Estimation
- Compressed Sensing: How sharp is the Restricted Isometry Property
- Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit
- Bacterial Community Reconstruction Using A Single Sequencing Reaction
- A Unified Framework for Sparse Relaxed Regularized Regression: SR3
- High-dimensional robust regression and outliers detection with SLOPE
- Sparse Reconstruction via The Reed-Muller Sieve
- Lensless Compressive Imaging
- Inferring Rankings Using Constrained Sensing
- Insense: Incoherent Sensor Selection for Sparse Signals
- Multi-view in Lensless Compressive Imaging
- Networked Estimation using Sparsifying Basis Prediction
- Is "Compressed Sensing" compressive? Can it beat the Nyquist Sampling Approach?
- Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique
- Sparse Stabilization and Control of Alignment Models
- Empirical average-case relation between undersampling and sparsity in x-ray CT
- Quantum Spectral Reasoning: A Non-Neural Architecture for Interpretable Machine Learning
- An Overview of Algorithms for Contactless Cardiac Feature Extraction from Radar Signals: Advances and Challenges
- Expressivity of expand-and-sparsify representations
- Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
- Compressive sensing Petrov-Galerkin approximation of high-dimensional\n parametric operator equations
- Optimal compressed sensing for mixing stochastic processes
- Subspace selection for projection maximization with matroid constraints
- Sparse Index Tracking Based On L1/2 Model And Algorithm
- Compressive and Noncompressive Power Spectral Density Estimation from Periodic Nonuniform Samples
- On Detection-Directed Estimation Approach for Noisy Compressive Sensing
- Enhanced imaging of microcalcifications in digital breast tomosynthesis through improved image-reconstruction algorithms. [europepmc]
- Lensless wide-field fluorescent imaging on a chip using compressive decoding of sparse objects. [europepmc]
- Feasibility of high temporal resolution breast DCE-MRI using compressed sensing theory. [europepmc]
- Metal artifact reduction in x-ray computed tomography (CT) by constrained optimization. [europepmc]
- A constrained, total-variation minimization algorithm for low-intensity x-ray CT. [europepmc]
- Characterization of statistical prior image constrained compressed sensing (PICCS): II. Application to dose reduction. [europepmc]
- Reverse engineering and identification in systems biology: strategies, perspectives and challenges. [europepmc]
- Reconstructing propagation networks with natural diversity and identifying hidden sources. [europepmc]
- Efficient and generalized processing of multidimensional NUS NMR data: the NESTA algorithm and comparison of regularization terms. [europepmc]
- Pitfalls in compressed sensing reconstruction and how to avoid them. [europepmc]
- Large Metasurface Aperture for Millimeter Wave Computational Imaging at the Human-Scale. [europepmc]
- Learning partial differential equations via data discovery and sparse optimization. [europepmc]
- Discovering sparse transcription factor codes for cell states and state transitions during development. [europepmc]
- A very large-scale microelectrode array for cellular-resolution electrophysiology. [europepmc]
- Deep-learning-based ghost imaging. [europepmc]
- Fast and accurate edge orientation processing during object manipulation. [europepmc]
- Robust data-driven discovery of governing physical laws with error bars. [europepmc]
- Front-end Weber-Fechner gain control enhances the fidelity of combinatorial odor coding. [europepmc]
- Learning to synthesize: robust phase retrieval at low photon counts. [europepmc]
- Broadband perovskite quantum dot spectrometer beyond human visual resolution. [europepmc]
- Endo-microscopy beyond the Abbe and Nyquist limits. [europepmc]
- Compressed sensing MRI: a review from signal processing perspective. [europepmc]
- Minutes-timescale 3D isotropic imaging of entire organs at subcellular resolution by content-aware compressed-sensing light-sheet microscopy. [europepmc]
- Compressed Sensing Real-Time Cine Reduces CMR Arrhythmia-Related Artifacts. [europepmc]
- Light-sheets and smart microscopy, an exciting future is dawning. [europepmc]
Related