Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

DOI10.1109/TIT.2006.885507MaRDI QIDQ3548002zbMATH OpenOpenAlexWikidataFDO

Authors Emmanuel J. Candès, Terence Tao

Publication date 21 December 2008

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

Full work available at URL https://arxiv.org/abs/math/0410542

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

Abstract: Suppose we are given a vector $f$ in $R^N$. How many linear measurements do we need to make about $f$ to be able to recover $f$ to within precision $epsilon$ in the Euclidean ($el{l}_2$) metric? Or more exactly, suppose we are interested in a class $calF$ of such objects--discrete digital signals, images, etc; how many linear measurements do we need to recover objects from this class to within accuracy $epsilon$? This paper shows that if the objects of interest are sparse or compressible in the sense that the reordered entries of a signal $fincalF$ decay like a power-law (or if the coefficient sequence of $f$ in a fixed basis decays like a power-law), then it is possible to reconstruct $f$ to within very high accuracy from a small number of random measurements.

Recommendations

• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Decoding by Linear Programming
• Sparsity and incoherence in compressive sampling

Cited in

(only showing first 100 items - show all)

• Geometric approach to error-correcting codes and reconstruction of signals
• Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
• On the conditioning of random subdictionaries
• A dual split Bregman method for fast \(\ell ^{1}\) minimization
• Ensemble extreme learning machine and sparse representation classification
• Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection
• Simple bounds for recovering low-complexity models
• Cirrhosis classification based on texture classification of random features
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Deterministic construction of compressed sensing matrices from codes
• An improved fast iterative shrinkage thresholding algorithm for image deblurring
• Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction
• An adaptive inverse scale space method for compressed sensing
• A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
• RIPless compressed sensing from anisotropic measurements
• Compressed sensing from a harmonic analysis point of view
• Approximation error in regularized SVD-based Fourier continuations
• Exact optimization for the \(\ell ^{1}\)-compressive sensing problem using a modified Dantzig-Wolfe method
• Nonconvex compressed sampling of natural images and applications to compressed MR imaging
• A coordinate gradient descent method for \(\ell_{1}\)-regularized convex minimization
• Low rank matrix recovery from rank one measurements
• Restricted isometries for partial random circulant matrices
• Remote sensing via \(\ell_1\)-minimization
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• The restricted isometry property for time-frequency structured random matrices
• Accelerated Bregman method for linearly constrained \(\ell _1-\ell _2\) minimization
• A novel cognitive ISAR imaging method with random stepped frequency chirp signal
• Influence factors of sparse microwave imaging radar system performance: approaches to waveform design and platform motion analysis
• Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain
• Improved FOCUSS method for reconstruction of cluster structured sparse signals in radar imaging
• 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
• On uncertainty principles in the finite dimensional setting
• Compressed sensing with coherent and redundant dictionaries
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• Recovery of high-dimensional sparse signals via \(\ell_1\)-minimization
• Adaptive data analysis via sparse time-frequency representation
• A box constrained gradient projection algorithm for compressed sensing
• Two are better than one: fundamental parameters of frame coherence
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
• Random sampling of sparse trigonometric polynomials
• Codes for exact support recovery of sparse vectors from inaccurate linear measurements and their decoding
• Recovery of low-rank matrices based on the rank null space properties
• Structured random measurements in signal processing
• Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
• Compressive wave computation
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Compressed sensing image restoration based on data-driven multi-scale tight frame
• Conjugate gradient acceleration of iteratively re-weighted least squares methods
• Landmark recognition with sparse representation classification and extreme learning machine
• Compressed sensing and dynamic mode decomposition
• Empirical processes with a bounded \(\psi_1\) diameter
• Off-grid DOA estimation via real-valued sparse Bayesian method in compressed sensing
• Entropic regularization of the \(\ell _{0}\) function
• Sparsity in time-frequency representations
• Accelerated projected gradient method for linear inverse problems with sparsity constraints
• Optimal non-linear models for sparsity and sampling
• An algorithm solving compressive sensing problem based on maximal monotone operators
• Deterministic convolutional compressed sensing matrices
• Restricted \(p\)-isometry property and its application for nonconvex compressive sensing
• On the linear independence of spikes and sines
• Compressed sensing: how sharp is the restricted isometry property?
• A dynamically bi-orthogonal method for time-dependent stochastic partial differential equations. II: Adaptivity and generalizations
• Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization
• Combinatorial Algorithms for Compressed Sensing
• \(\mathrm{L_1RIP}\)-based robust compressed sensing
• Compressive sensing by random convolution
• Interpolation via weighted \(\ell_{1}\) minimization
• Quasi-linear compressed sensing
• Multiscale stochastic preconditioners in non-intrusive spectral projection
• Two-dimensional digital filters with sparse coefficients
• The coefficient regularized regression with random projection
• A novel compressed sensing scheme for photoacoustic tomography
• Detecting a vector based on linear measurements
• A recursive procedure for density estimation on the binary hypercube
• Model selection with distributed SCAD penalty
• Iterative re-weighted least squares algorithm for \(l_p\)-minimization with tight frame and \(0 < p \leq 1\)
• Self-adaptive image reconstruction inspired by insect compound eye mechanism
• On the Doubly Sparse Compressed Sensing Problem
• Adaptive compressive learning for prediction of protein-protein interactions from primary sequence
• Reconstruction of sparse signals in impulsive disturbance environments
• Sparse recovery properties of discrete random matrices
• Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
• Frames as codes
• Reconstructed error and linear representation coefficients restricted by \(\ell_1\)-minimization for face recognition under different illumination and occlusion
• Sparse approximation of fitting surface by elastic net
• Convergence of a data-driven time-frequency analysis method
• Joint image compression-encryption scheme using entropy coding and compressive sensing
• Spark-level sparsity and the \(\ell_1\) tail minimization
• Compressed sparse tensor based quadrature for vibrational quantum mechanics integrals
• A simple and flexible model order reduction method for FFT-based homogenization problems using a sparse sampling technique
• DC approximation approach for \(\ell_0\)-minimization in compressed sensing
• Modern regularization methods for inverse problems
• Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing
• An enhanced diagnosis method for weak fault features of bearing acoustic emission signal based on compressed sensing
• Parallel magnetic resonance imaging acceleration with a hybrid sensing approach
• Multilevel preconditioning and adaptive sparse solution of inverse problems
• Sparse sensing and DMD-based identification of flow regimes and bifurcations in complex flows

This page was built for publication: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548002)