Compressed sensing
2006/04/01 by David L. Donoho, D.L. Donoho · 23,265 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Combinatorics #Compressed sensing #Computer science #Image and Signal Denoising Methods #Mathematical Analysis and Transform Methods #Mathematics #Orthonormal basis #Physics #Pixel #Sparse and Compressive Sensing Techniques
paper · doi:10.1109/tit.2006.871582
published in IEEE Transactions on Information Theory 52(4), 1289-1306 (Institute of Electrical and Electronics Engineers)
openalex publication_date 2006/04/01 · openalex created_date 2022/05/12 · openalex updated_date 2026/08/05
Abstract
Suppose x is an unknown vector in Ropfm(a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n=O(m1/4log5/2(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an lscrpball for 02error O(N1/2-1p/). It is possible to design n=O(Nlog(m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of lscrpballs in high-dimensional Euclidean space in the case 0<ples1, and give a criterion identifying near- optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces
Cited by
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Deterministic Construction of Binary, Bipolar, and Ternary Compressed Sensing Matrices
- LDPC Codes for Compressed Sensing
- Deterministic Constructions of Compressed Sensing Matrices From Unitary Geometry
- Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
- Recovering Compressively Sampled Signals Using Partial Support Information
- Approximation Algorithms for Model-Based Compressive Sensing
- Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling
- A unifying framework from neural superposition to sparse interpretable codes
- Review on the new development of vibration-based damage identification for civil engineering structures: 2010–2019
- SAR Image Reconstruction via Incremental Imaging With Compressive Sensing
- Parameter Estimation With Bistatic MIMO Radar: A Coarray Tensor Decomposition Framework
- Super-resolution imaging with radio interferometry using sparse modeling
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods
- Improved total variation-based CT image reconstruction applied to clinical data
- Non-local total-variation (NLTV) minimization combined with reweighted L1-norm for compressed sensing CT reconstruction
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
- Low-field permanent magnets for industrial process and quality control
- Pros and cons of ultra-high-field MRI/MRS for human application
- Reconstruction of a low-rank matrix in the presence of Gaussian noise
- Machine Learning for Fluid Mechanics
- The Dantzig selector: Statistical estimation when p is much larger than n
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Modern Koopman Theory for Dynamical Systems
- Unsupervised learning enabled label-free single-pixel imaging for resilient information transmission through unknown dynamic scattering media
- Multiple‐ TE Based Blood–Brain‐Barrier Water Exchange Time Measurement Using a TE ‐Resolved 3D TSE Stack‐Of‐Spirals Readout
- Ramanujan sums in signal recovery and uncertainty principle inequalities
- Cross-Axis Weighted Harmonic Method: A Frequency-Domain Approach for Enhanced Resolution in Magnetic Particle Imaging
- A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
- Machine learning and the physical sciences
- Sparse filtering with the generalized lp / lq norm and its applications to the condition monitoring of rotating machinery
- How to generate accurate continuous thermal regimes from sparse but regular temperature measurements
- Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator
- Terahertz imaging technology: progress and applications
- Reducing electron beam damage through alternative STEM scanning strategies, Part I: Experimental findings
- Coprime array-based DOA estimation in unknown nonuniform noise environment
- Hashing-based remote sensing image tamper detection system
- A fast approach for overcomplete sparse decomposition based on smoothed L0 norm
- Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang–Fix
- Robust Sparse Linear Discriminant Analysis
- An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
- Compressive Sensing [Lecture Notes]
- Single-pixel imaging via compressive sampling
- Compressed Sensing MRI
- Phase Retrieval with Application to Optical Imaging: A contemporary overview
- A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing
- Sparsity-Driven Synthetic Aperture Radar Imaging: Reconstruction, autofocusing, moving targets, and compressed sensing
- Physics-Driven Deep Learning Methods for Fast Quantitative Magnetic Resonance Imaging: Performance improvements through integration with deep neural networks
- Recovery Conditions of Sparse Signals Using Orthogonal Least Squares-Type Algorithms
- A Bidirectional Cross-Scrambling Medical Image Encryption Scheme Incorporates Compressed Sensing and Its Application in IoMT
- Iterative hard thresholding for compressed sensing
- Robust sparse recovery with sparse Bernoulli matrices via expanders
- Algebraic compressed sensing
- 3D Geometry and Motion Estimations of Maneuvering Targets for Interferometric ISAR With Sparse Aperture
- Compressed sensing for body MRI
- MRI temporal acceleration techniques
- Recent advances in 3D time-resolved contrast-enhanced MR angiography
- Recovery of signals under the condition on RIC and ROC via prior support information
- Spectrum Sensing for Cognitive Radio : State-of-the-Art and Recent Advances
- New analysis of manifold embeddings and signal recovery from compressive measurements
- Fast Image Recovery Using Variable Splitting and Constrained Optimization
- SPARLS: The Sparse RLS Algorithm
- Exact solutions of infinite dimensional total-variation regularized\n problems
- A high-bias, low-variance introduction to Machine Learning for physicists
- Stable super-resolution limit and smallest singular value of restricted Fourier matrices
- Blind filters based on envelope spectrum sparsity indicators for bearing and gear vibration-based condition monitoring
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Sharp RIP bound for sparse signal and low-rank matrix recovery
- MUSIC for single-snapshot spectral estimation: Stability and super-resolution
- Recovery analysis for weighted ℓ1-minimization using the null space property
- Wavelet inpainting with the ℓ0 sparse regularization
- Deep(er) Learning
- Inverse Potential Problems for Divergence of Measures with Total Variation Regularization
- Roadmap on computational methods in optical imaging and holography [invited]
- Whole‐brain high‐resolution metabolite mapping with 3D compressed‐sensing SENSE low‐rank 1 H FID‐MRSI
- Accurate Estimation of Neural Population Dynamics without Spike Sorting
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Gadgetron: An open source framework for medical image reconstruction
- Sensor placement for sparse force reconstruction
- Compressed sensing MRI: a review of the clinical literature
- A deep learning-based reconstruction approach for accelerated magnetic resonance image of the knee with compressed sense: evaluation in healthy volunteers
- Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique
- A Novel Monte-Carlo Compressed Sensing and Dictionary Learning Method for the Efficient Path Planning of Remote Sensing Robots
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Restricted isometries for partial random circulant matrices
- Randomized LU decomposition
- Dynamics of information diffusion and its applications on complex networks
- Donoho-Logan Large Sieve Principles for Modulation and Polyanalytic Fock\n Spaces
- Lasso Meets Horseshoe : A Survey
- Robustness of Planar Fourier Capture Arrays to Colour Changes and Lost Pixels
- The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
- Digital Twin: Values, Challenges and Enablers From a Modeling Perspective
- Hierarchical clustering and optimal interval combination (HCIC): a knowledge-guided strategy for consistent and interpretable spectral variable interval selection
- A Saddle Point Algorithm for Robust Data-Driven Factor Model Problems
- The stability of generalized phase retrieval problem over compact groups
- DOA estimation based on CNN for underwater acoustic array
- Light-sheets and smart microscopy, an exciting future is dawning
- Deep learning for tomographic image reconstruction
- 2022 Review of Data-Driven Plasma Science
- Discovering governing equations from data: Sparse identification of nonlinear dynamical systems
- DART: A Practical Reconstruction Algorithm for Discrete Tomography
- Multichannel Compressive Sensing MRI Using Noiselet Encoding
- Towards a Mathematical Theory of Cortical Micro-circuits
- k‐t group sparse: A method for accelerating dynamic MRI
- Comentarios de un latinista español en torno a la "Gramática de la Lengua Española" de D. Emilio Alarcos Llorach
- The evolution of image reconstruction for CT—from filtered back projection to artificial intelligence
- Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression
- Learning a variational network for reconstruction of accelerated MRI data
- Golden‐angle radial sparse parallel MRI: Combination of compressed sensing, parallel imaging, and golden‐angle radial sampling for fast and flexible dynamic volumetric MRI
- Compressive Estimation of Doubly Selective Channels in Multicarrier Systems: Leakage Effects and Sparsity-Enhancing Processing
- Nonlinear regularization techniques for seismic tomography
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Multi-shot Echo Planar Imaging for accelerated Cartesian MR Fingerprinting: An alternative to conventional spiral MR Fingerprinting
- Compressed dynamic mode decomposition for background modeling
- Spread spectrum for imaging techniques in radio interferometry
- Phase diagram of matrix compressed sensing
- Time-Delay Estimation From Low-Rate Samples: A Union of Subspaces Approach
- Magnetic resonance fingerprinting
- Statistical-Physics-Based Reconstruction in Compressed Sensing
- Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices
- On the Computational Intractability of Exact and Approximate Dictionary Learning
- Analysis of sparse representations using bi-orthogonal dictionaries
- Iteratively reweighted algorithms for compressive sensing
- Sparse Probit Linear Mixed Model
- GPU-based high-performance computing for radiation therapy
- Stability of low-rank matrix recovery and its connections to Banach space geometry
- The nonequilibrium quantum many-body problem as a paradigm for extreme data science
- Development of a fast electromagnetic beam blanker for compressed sensing in scanning transmission electron microscopy
- Compressed Sensing in Astronomy
- Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing
- Compressing measurements in quantum dynamic parameter estimation
- A compressed sensing approach to 3D weak lensing
- Solving Inverse Problems With Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity
- Discrete Signal Reconstruction by Sum of Absolute Values
- Extracting a shape function for a signal with intra-wave frequency modulation
- Fundamental Performance Limits for Ideal Decoders in High-Dimensional Linear Inverse Problems
- Denoising point sets via L0 minimization
- Light fields in complex media: Mesoscopic scattering meets wave control
- Decoding from Pooled Data: Sharp Information-Theoretic Bounds
- MORESANE: MOdel REconstruction by Synthesis-ANalysis Estimators
- Magnetic Turbulence Spectra and Intermittency in the Heliosheath and in the Local Interstellar Medium
- Sparse approximation problem: how rapid simulated annealing succeeds and fails
- Target detection performance bounds in compressive imaging
- Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
- Progressive Compressed Sensing and Reconstruction of Multidimensional Signals Using Hybrid Transform/Prediction Sparsity Model
- A Novel Progressive Image Scanning and Reconstruction Scheme Based on Compressed Sensing and Linear Prediction
- Graded quantization: Democracy for multiple descriptions in compressed sensing
- Smoothness-constrained image recovery from block-based random projections
- Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
- Atomic Norm Minimization for Modal Analysis From Random and Compressed Samples
- Compressive Sensing of Sparse Tensors
- Robust Reconstruction of Complex Networks from Sparse Data
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Signal Retrieval With Measurement System Knowledge Using Variational Generative Model
- On the Distribution of the \(ℓ ^\underline \mathrm th\) Largest Eigenvalue of Spiked Complex Wishart Matrices
- Compressive sensing of signals generated in plastic scintillators in a novel J-PET instrument
- Efficient Estimation of Pauli Channels
- LADMM-Net: An unrolled deep network for spectral image fusion from compressive data
- Quantifying entanglement in a 68-billion-dimensional quantum state space
- Inferring sparsity: Compressed sensing using generalized restricted Boltzmann machines
- Radial velocity data analysis with compressed sensing techniques
- A New Compressive Video Sensing Framework for Mobile Broadcast
- State of the art and prospects of structured sensing matrices in compressed sensing
- A Novel Sampling Theorem on the Sphere
- A Review on Symbolic Regression in Power Systems: Methods, Applications, and Future Directions
- Blur resolved OCT: full-range interferometric synthetic aperture microscopy through dispersion encoding
- Robust recovery of signals with partially known support information using weighted BPDN
- Approximately Certifying the Restricted Isometry Property is Hard
- Robust sparse image reconstruction of radio interferometric observations with purify
- Deep Learning Meets Sparse Regularization: A signal processing perspective
- Global Sensitivity Analysis and Estimation of Model Error, Toward Uncertainty Quantification in Scramjet Computations
- Unknown Sparsity in Compressed Sensing: Denoising and Inference
- Compressed sensing quantum process tomography for superconducting quantum gates
- Sparse dynamical Boltzmann machine for reconstructing complex networks with binary dynamics
- Fast dictionary learning from incomplete data
- Reconstruction of Binary Functions and Shapes From Incomplete Frequency Information
- Statistical mechanical analysis of sparse linear regression as a variable selection problem
- Collection of micromirror-modulated light in the single-pixel broadband hyperspectral microscope
- Convolutional Sparse Coding Fast Approximation With Application to Seismic Reflectivity Estimation
- Massive MIMO Channel Estimation for Millimeter Wave Systems via Matrix Completion
- Type I and Type II Bayesian Methods for Sparse Signal Recovery Using Scale Mixtures
- Revealing physical interaction networks from statistics of collective dynamics
- Rate-distortion dimension of stochastic processes
- Frequency‐modulated SSFP with radial sampling and subspace reconstruction: A time‐efficient alternative to phase‐cycled bSSFP
- Accelerating Ultrafast Spectroscopy with Compressive Sensing
- ℓ1-Analysis minimization and generalized (co-)sparsity: When does recovery succeed?
- Compressive matched-field processing
- Sparse recovery of undersampled intensity patterns for coherent diffraction imaging at high X-ray energies
- Symmetric Toeplitz-Structured Compressed Sensing Matrices
- Compressive Hyperspectral Imaging via Approximate Message Passing
- Compressive Earth observatory: An insight from AIRS/AMSU retrievals
- A dedicated greedy pursuit algorithm for sparse spectral representation of music sound
- Soft Video Multicasting Using Adaptive Compressed Sensing
- A regression algorithm for accelerated lattice QCD that exploits sparse inference on the D-Wave quantum annealer
- Surveillance video processing using compressive sensing
- A general framework for the design and analysis of sparse FIR linear equalizers
- Design and analysis framework for sparse FIR channel shortening
- Sparse Signal Processing With Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
- Construction of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry Property
- On the Noise Robustness of Simultaneous Orthogonal Matching Pursuit
- A scalable design of experiments framework for optimal sensor placement
- High-Dimensional Estimation of Structured Signals From Non-Linear Observations With General Convex Loss Functions
- ℓ 1-Norm Minimization With Regula Falsi Type Root Finding Methods
- Detecting and tracking drift in quantum information processors
- Robust Bayesian Compressive Sensing for Signals in Structural Health Monitoring
- An accelerated splitting algorithm for radio-interferometric imaging: when natural and uniform weighting meet
- Joint Sparse Recovery With Semisupervised MUSIC
- SPARSE FARADAY ROTATION MEASURE SYNTHESIS
- A Novel Rate Control Algorithm for Onboard Predictive Coding of Multispectral and Hyperspectral Images
- Sparse polynomial chaos expansions via compressed sensing and D-optimal design
- Improving the Bound on the RIP Constant in Generalized Orthogonal Matching Pursuit
- Temporal resolution improvement using PICCS in MDCT cardiac imaging. [europepmc]
- Lensless wide-field fluorescent imaging on a chip using compressive decoding of sparse objects. [europepmc]
- Compressed sensing based cone-beam computed tomography reconstruction with a first-order method. [europepmc]
- Prior image constrained compressed sensing: implementation and performance evaluation. [europepmc]
- Sparsity based denoising of spectral domain optical coherence tomography images. [europepmc]
- Accelerated barrier optimization compressed sensing (ABOCS) reconstruction for cone-beam CT: phantom studies. [europepmc]
- Reverse engineering and identification in systems biology: strategies, perspectives and challenges. [europepmc]
- Reconstructing propagation networks with natural diversity and identifying hidden sources. [europepmc]
- Compressed sensing MRI: a review of the clinical literature. [europepmc]
- Microstructure Informed Tractography: Pitfalls and Open Challenges. [europepmc]
- A Russian Dolls ordering of the Hadamard basis for compressive single-pixel imaging. [europepmc]
- GENFIRE: A generalized Fourier iterative reconstruction algorithm for high-resolution 3D imaging. [europepmc]
- Deep learning for real-time single-pixel video. [europepmc]
- Single-Pixel Imaging and Its Application in Three-Dimensional Reconstruction: A Brief Review. [europepmc]
- Net-FLICS: fast quantitative wide-field fluorescence lifetime imaging with compressed sensing - a deep learning approach. [europepmc]
- Single-shot lensless imaging with fresnel zone aperture and incoherent illumination. [europepmc]
- Broadband perovskite quantum dot spectrometer beyond human visual resolution. [europepmc]
- Compressed sensing MRI: a review from signal processing perspective. [europepmc]
- Single pixel imaging at megahertz switching rates via cyclic Hadamard masks. [europepmc]
- An atlas of white matter anatomy, its variability, and reproducibility based on constrained spherical deconvolution of diffusion MRI. [europepmc]
- Advances in cost-effective integrated spectrometers. [europepmc]
- Monocular metasurface camera for passive single-shot 4D imaging. [europepmc]
- Light-sheets and smart microscopy, an exciting future is dawning. [europepmc]
- Scalable genetic screening for regulatory circuits using compressed Perturb-seq. [europepmc]
- Deep learning for accelerated and robust MRI reconstruction. [europepmc]
Related