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)

• An algebra for periodic rhythms and scales
• Compressed sensing
• A hybrid splitting method for smoothing Tikhonov regularization problem
• Multilevel preconditioning and adaptive sparse solution of inverse problems
• Sparse approximation using \(\ell_1-\ell_2\) minimization and its application to stochastic collocation
• Stochastic collocation methods via \(\ell_1\) minimization using randomized quadratures
• Compressed sensing based on trust region method
• Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• Compressed sensing: how sharp is the restricted isometry property?
• A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery
• Adaptive compressive learning for prediction of protein-protein interactions from primary sequence
• A bipolar-bisection piecewise encoding scheme for multi-source reverse time migration
• Compressed sensing reconstruction using expectation propagation
• Leveraging reduced-order models for state estimation using deep learning
• Cirrhosis classification based on texture classification of random features
• $\ell _0$ Minimization for wavelet frame based image restoration
• 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
• High-dimensional inference: confidence intervals, \(p\)-values and R-software \texttt{hdi}
• Convergence of a data-driven time-frequency analysis method
• Sparse low rank approximation of potential energy surfaces with applications in estimation of anharmonic zero point energies and frequencies
• Compressed-sensing-based gradient reconstruction for ghost imaging
• A Variable Density Sampling Scheme for Compressive Fourier Transform Interferometry
• Recovering network topologies via Taylor expansion and compressive sensing
• Sparse identification of posynomial models
• Signal reconstruction by conjugate gradient algorithm based on smoothing \(l_1\)-norm
• Approximation with random bases: pro et contra
• Sparse recovery properties of discrete random matrices
• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• scientific article; zbMATH DE number 7750674 (Why is no real title available?)
• Remote sensing via _1-minimization
• Structured random measurements in signal processing
• Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
• Spectral dynamics and regularization of incompletely and irregularly measured data
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Codes for exact support recovery of sparse vectors from inaccurate linear measurements and their decoding
• On error correction with errors in both the channel and syndrome
• Sparse Legendre expansions via _1-minimization
• Strong convergence of a modified proximal algorithm for solving the lasso
• An implementable proximal point algorithmic framework for nuclear norm minimization
• A statistical mechanics approach to de-biasing and uncertainty estimation in Lasso for random measurements
• The proximity operator of the log-sum penalty
• Gradient projection Newton algorithm for sparse collaborative learning using synthetic and real datasets of applications
• Compressed sensing of color images
• Generalization bounds for sparse random feature expansions
• Sparsity and incoherence in compressive sampling
• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Stability of 1-bit compressed sensing in sparse data reconstruction
• Tight and full spark Chebyshev frames with real entries and worst-case coherence analysis
• Collaborative block compressed sensing reconstruction with dual-domain sparse representation
• Lattice-based patterned fabric inspection by using total variation with sparsity and low-rank representations
• Bias versus non-convexity in compressed sensing
• The numerics of phase retrieval
• 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
• Gradient projection Newton pursuit for sparsity constrained optimization
• Sparse control for continuous‐time systems
• An accelerated forward-backward splitting algorithm for solving inclusion problems with applications to regression and link prediction problems
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Restricted normal cones and sparsity optimization with affine constraints
• \(\mathrm{L_1RIP}\)-based robust compressed sensing
• Data science, big data and statistics
• Nonoverlapping convex polytopes with vertices in a Boolean cube and other problems in coding theory
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Discussion: ``A significance test for the lasso
• Fast sparse reconstruction: Greedy inverse scale space flows
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Nonconvex compressed sampling of natural images and applications to compressed MR imaging
• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Sparse sensing and DMD-based identification of flow regimes and bifurcations in complex flows
• Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
• Structured sparsity promoting functions
• Reconstruction and subgaussian processes
• On the role of total variation in compressed sensing
• Coorbit theory, multi-\(\alpha \)-modulation frames, and the concept of joint sparsity for medical multichannel data analysis
• Sparse approximate solution of partial differential equations
• On the linear independence of spikes and sines
• Dimensionality reduction with subgaussian matrices: a unified theory
• Relaxation algorithms for matrix completion, with applications to seismic travel-time data interpolation
• Signature codes for weighted noisy adder channel, multimedia fingerprinting and compressed sensing
• Solution of the problem on image reconstruction in computed tomography
• An efficient augmented Lagrangian method with applications to total variation minimization
• Learning semidefinite regularizers
• Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
• Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems
• Region-based image-fusion framework for compressive imaging
• Recursion for the smallest eigenvalue density of \(\beta \)-Wishart-Laguerre ensemble
• On sparse representation of analytic signal in Hardy space
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• Jointly evolving and compressing fuzzy system for feature reduction and classification
• Short-term memory capacity in networks via the restricted isometry property
• Chaotic analog-to-information conversion: principle and reconstructability with parameter identifiability
• Efficient sensing of von Kármán vortices using compressive sensing
• A note on the complexity of \(L _{p }\) minimization
• Joint image compression-encryption scheme using entropy coding and compressive sensing
• An improved fast iterative shrinkage thresholding algorithm for image deblurring

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)