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

DOI10.1109/TIT.2006.885507zbMATH Open1309.94033arXivmath/0410542OpenAlexW2129638195WikidataQ56813489 ScholiaQ56813489MaRDI QIDQ3548002FDOQ3548002

Authors: Emmanuel J. Candès, Terence Tao 

Publication date: 21 December 2008

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

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.

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

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

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Recovering network topologies via Taylor expansion and compressive sensing
• Title not available (Why is that?)
• High-dimensional inference: confidence intervals, \(p\)-values and R-software \texttt{hdi}
• Sparsity and incoherence in compressive sampling
• A statistical mechanics approach to de-biasing and uncertainty estimation in Lasso for random measurements
• Sparse Legendre expansions via \(\ell_1\)-minimization
• On error correction with errors in both the channel and syndrome
• Strong convergence of a modified proximal algorithm for solving the lasso
• An implementable proximal point algorithmic framework for nuclear norm minimization
• Restricted normal cones and sparsity optimization with affine constraints
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• An efficient augmented Lagrangian method with applications to total variation minimization
• Dimensionality reduction with subgaussian matrices: a unified theory
• Solution of the problem on image reconstruction in computed tomography
• A note on the complexity of \(L _{p }\) minimization
• Compressive sensing-based topology identification of multilayer networks
• Properties and iterative methods for the lasso and its variants
• A significance test for the lasso
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparse recovery by non-convex optimization - instance optimality
• Guarantees of total variation minimization for signal recovery
• Super-resolution of point sources via convex programming
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Sparse recovery under weak moment assumptions
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Random projections of smooth manifolds
• Compressive sensing with local geometric features
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• Fast Phase Retrieval from Local Correlation Measurements
• Discussion: ``A significance test for the lasso
• Accelerating gradient projection methods for \(\ell _1\)-constrained signal recovery by steplength selection rules
• Gaussian approximations in high dimensional estimation
• Total variation wavelet inpainting
• Testing the nullspace property using semidefinite programming
• The weighted majority algorithm
• Derandomizing restricted isometries via the Legendre symbol
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Exact matrix completion via convex optimization
• Compressed sensing and best \(k\)-term approximation
• The residual method for regularizing ill-posed problems
• Exact reconstruction using Beurling minimal extrapolation
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• A model of regularization parameter determination in low-dose X-ray CT reconstruction based on dictionary learning
• An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration
• Proximity algorithms for the L1/TV image denoising model
• Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
• Explicit constructions of RIP matrices and related problems
• Steiner equiangular tight frames
• Variations on a theorem of Candès, Romberg and Tao
• A superlinearly convergent \(R\)-regularized Newton scheme for variational models with concave sparsity-promoting priors
• Decoding by Linear Programming
• Extensions of compressed sensing
• Robust sparse phase retrieval made easy
• Rejoinder: ``A significance test for the lasso
• A unified approach to model selection and sparse recovery using regularized least squares
• Data-driven time-frequency analysis
• Stability and instance optimality for Gaussian measurements in compressed sensing
• Linearized Bregman iterations for compressed sensing
• Robustness properties of dimensionality reduction with Gaussian random matrices
• Regularized vector field learning with sparse approximation for mismatch removal
• Best subset selection via a modern optimization lens
• A survey of compressed sensing
• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT
• R3P-Loc: a compact multi-label predictor using ridge regression and random projection for protein subcellular localization
• How well can we estimate a sparse vector?
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Noncommutative Bennett and Rosenthal inequalities
• One-bit compressed sensing by linear programming
• An alternating minimization method for matrix completion problems
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• The Littlewood-Offord problem and invertibility of random matrices
• Discussion: ``A significance test for the lasso
• Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials
• On sparse reconstruction from Fourier and Gaussian measurements
• Asymptotic analysis of the role of spatial sampling for covariance parameter estimation of Gaussian processes
• A novel measurement matrix based on regression model for block compressed sensing
• Anomaly detection in large-scale data stream networks
• Stable signal recovery from incomplete and inaccurate measurements
• Signal Reconstruction From Noisy Random Projections
• Suprema of chaos processes and the restricted isometry property
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• IMRO: A proximal quasi-Newton method for solving \(\ell_1\)-regularized least squares problems
• Compressed sensing
• $\ell _0$ Minimization for wavelet frame based image restoration
• Coorbit theory, multi-\(\alpha \)-modulation frames, and the concept of joint sparsity for medical multichannel data analysis
• Sparse approximate solution of partial differential equations
• Wavelet denoising via sparse representation
• On the volume of unit balls of finite-dimensional Lorentz spaces
• The stochastic geometry of unconstrained one-bit data compression
• Signal recovery under cumulative coherence
• Sparse signal representation by adaptive non-uniform B-spline dictionaries on a compact interval
• Sparse recovery from inaccurate saturated measurements
• On the uniqueness of sparse time-frequency representation of multiscale data
• Sparse time-frequency decomposition for multiple signals with same frequencies
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• Extraction of intrawave signals using the sparse time-frequency representation method

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)