Compressed sensing
2006/04/01 by David L. Donoho, D.L. Donoho · 111 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Image and Signal Denoising Methods #Mathematical Analysis and Transform Methods
paper · doi:10.1109/tit.2006.871582
Abstract
Suppose x is an unknown vector in Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> (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(m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/4</sup> log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5/2</sup> (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 lscr <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> ball for 0<ples1. The N most important coefficients in that expansion allow reconstruction with lscr <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> error O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2-1</sup> p/). 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 lscr <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> balls 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 ℓ 0 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
- Lasso Meets Horseshoe: A Survey
- 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\n 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 <sup>1</sup> H FID‐MRSI
- Donoho-Logan large sieve principles for modulation and polyanalytic Fock spaces
- 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
- 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