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)

• Self-calibration and biconvex compressive sensing
• Idempotents and compressive sampling
• Slope meets Lasso: improved oracle bounds and optimality
• Collaborative block compressed sensing reconstruction with dual-domain sparse representation
• Effect of sensing matrices on quality index parameters for block sparse bayesian learning-based EEG compressive sensing
• Intrinsic modeling of stochastic dynamical systems using empirical geometry
• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Compressive sensing with redundant dictionaries and structured measurements
• Approximation of frame based missing data recovery
• Reconstruction and subgaussian processes
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Large deviations, dynamics and phase transitions in large stochastic and disordered neural networks
• Analog random coding
• A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• A simple Gaussian measurement bound for exact recovery of block-sparse signals
• Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm
• A fast recovery method of 2D geometric compressed sensing signal
• Compressive sampling and rapid reconstruction of broadband frequency hopping signals with interference
• DFT spectrum-sparsity-based quasi-periodic signal identification and application
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Analysis of sparse MIMO radar
• Signal recovery under mutual incoherence property and oracle inequalities
• Discrete uncertainty principles and sparse signal processing
• Improved bounds for sparse recovery from subsampled random convolutions
• Spectral dynamics and regularization of incompletely and irregularly measured data
• The numerics of phase retrieval
• Cross validation in Lasso and its acceleration
• Estimation of block sparsity in compressive sensing
• Reconstruction of systems with impulses and delays from time series data
• Randomized interpolative decomposition of separated representations
• Construction of a full row-rank matrix system for multiple scanning directions in discrete tomography
• An efficient privacy-preserving compressive data gathering scheme in WSNs
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• A new sparse recovery method for the inverse acoustic scattering problem
• A simple and feasible method for a class of large-scale \(l^1\)-problems
• Data science, big data and statistics
• Wavelet denoising via sparse representation
• On support sizes of restricted isometry constants
• Rapid compressed sensing reconstruction: a semi-tensor product approach
• Approximation with random bases: pro et contra
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Low complexity regularization of linear inverse problems
• On sparse representation of analytic signal in Hardy space
• Beyond sparsity: the role of \(L_{1}\)-optimizer in pattern classification
• Sparse representation of signals in Hardy space
• Sparse identification of posynomial models
• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions
• High-dimensional inference in misspecified linear models
• On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing
• A Barzilai-Borwein type method for minimizing composite functions
• Generalized sampling and infinite-dimensional compressed sensing
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Generalized Kalman smoothing: modeling and algorithms
• Fast and RIP-optimal transforms
• Compressed history matching: Exploiting transform-domain sparsity for regularization of nonlinear dynamic data integration problems
• Yang-Baxter equations in quantum information
• 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
• Optimization methods for synthetic aperture radar imaging
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Deterministic construction of sparse binary matrices via incremental integer optimization
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Sparsity enforcing edge detection method for blurred and noisy Fourier data
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• Nonlinear least squares in \(\mathbb R^{N}\)
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Greedy-like algorithms for the cosparse analysis model
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• The null space property for sparse recovery from multiple measurement vectors
• A least-squares method for sparse low rank approximation of multivariate functions
• Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
• Rank-based model selection for multiple ions quantum tomography
• Majorizing measures and proportional subsets of bounded orthonormal systems
• Fast \(\ell _{1}\) minimization by iterative thresholding for multidimensional NMR spectroscopy
• Near oracle performance and block analysis of signal space greedy methods
• Sparse system identification for stochastic systems with general observation sequences
• Sparse regularization for semi-supervised classification
• A convergent overlapping domain decomposition method for total variation minimization
• Dense fast random projections and Lean Walsh transforms
• Signature codes for weighted noisy adder channel, multimedia fingerprinting and compressed sensing
• On the generation of sampling schemes for magnetic resonance imaging
• A modified greedy analysis pursuit algorithm for the cosparse analysis model
• Decomposable norm minimization with proximal-gradient homotopy algorithm
• scientific article; zbMATH DE number 7583424 (Why is no real title available?)
• Yang-Baxter equations and quantum entanglements
• Finding a low-rank basis in a matrix subspace
• Sparse decomposition by iterating Lipschitzian-type mappings
• Sparse signal recovery using a new class of random matrices
• Uniform recovery of fusion frame structured sparse signals
• Compressed sensing of color images
• Learning semidefinite regularizers
• Log-concavity and strong log-concavity: a review
• Signature codes for noisy multiple access adder channel
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees

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)