Stable signal recovery from incomplete and inaccurate measurements

DOI10.1002/CPA.20124zbMATH Open1098.94009arXivmath/0503066OpenAlexW2164452299WikidataQ56688957 ScholiaQ56688957MaRDI QIDQ5486267FDOQ5486267

Authors: Emmanuel J. Candès, Justin Romberg, Terence Tao 

Publication date: 6 September 2006

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Abstract: Suppose we wish to recover an n-dimensional real-valued vector x_0 (e.g. a digital signal or image) from incomplete and contaminated observations y = A x_0 + e; A is a n by m matrix with far fewer rows than columns (n << m) and e is an error term. Is it possible to recover x_0 accurately based on the data y? To recover x_0, we consider the solution x* to the l1-regularization problem min |x|_1 subject to |Ax-y|_2 <= epsilon, where epsilon is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit-normed columns) and if the vector x_0 is sufficiently sparse, then the solution is within the noise level |x* - x_0|_2 le C epsilon. As a first example, suppose that A is a Gaussian random matrix, then stable recovery occurs for almost all such A's provided that the number of nonzeros of x_0 is of about the same order as the number of observations. Second, suppose one observes few Fourier samples of x_0, then stable recovery occurs for almost any set of p coefficients provided that the number of nonzeros is of the order of n/[log m]^6. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights on the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals.

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

Recommendations

• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Stable Recovery of Sparse Signals Via Regularized Minimization
• Decoding by Linear Programming
• On sparse reconstruction from Fourier and Gaussian measurements
• Sparsity and incoherence in compressive sampling

zbMATH Keywords

approximately sparse signals

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Numerical optimization and variational techniques (65K10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Rate-distortion theory in information and communication theory (94A34)

Cites Work

• Title not available (Why is that?)

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

• Empirical average-case relation between undersampling and sparsity in X-ray CT
• Periodic spline-based frames for image restoration
• Iterative hard thresholding for compressed sensing
• A simple proof of the restricted isometry property for random matrices
• Reconstruction of sparse connectivity in neural networks from spike train covariances
• Sparsity and incoherence in compressive sampling
• Some sharp performance bounds for least squares regression with \(L_1\) regularization
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Strong convergence of a modified proximal algorithm for solving the lasso
• A LONE code for the sparse control of quantum systems
• Recovery of sparsest signals via \(\ell^q \)-minimization
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Learning functions of few arbitrary linear parameters in high dimensions
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Approximation of functions of few variables in high dimensions
• Properties and iterative methods for the lasso and its variants
• \(L_1\)-penalization in functional linear regression with subgaussian design
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparse recovery by non-convex optimization - instance optimality
• 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).
• \(\alpha\)-Molecules
• A geometrical stability condition for compressed sensing
• Convolutional neural networks analyzed via convolutional sparse coding
• Adaptive restart for accelerated gradient schemes
• Stable direction recovery in single-index models with a diverging number of predictors
• A remark on compressed sensing
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
• Random projections of smooth manifolds
• Combinatorial sublinear-time Fourier algorithms
• Analysis of discrete \(L^2\) projection on polynomial spaces with random evaluations
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• The restricted isometry property and its implications for compressed sensing
• Statistical consistency of coefficient-based conditional quantile regression
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Necessary and sufficient conditions for linear convergence of \(\ell^1\)-regularization
• Compressed sensing and best \(k\)-term approximation
• The residual method for regularizing ill-posed problems
• Exact reconstruction using Beurling minimal extrapolation
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Stable signal recovery from phaseless measurements
• Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Explicit constructions of RIP matrices and related problems
• Thresholding-based iterative selection procedures for model selection and shrinkage
• Matrix-free interior point method for compressed sensing problems
• Properties and iterative methods for the \(Q\)-lasso
• Variations on a theorem of Candès, Romberg and Tao
• Sparse recovery with partial support knowledge
• A numerical exploration of compressed sampling recovery
• A nonconvex model with minimax concave penalty for image restoration
• Decoding by Linear Programming
• Just relax: convex programming methods for identifying sparse signals in noise
• Stable recovery of sparse overcomplete representations in the presence of noise
• Microlocal analysis of the geometric separation problem
• Isotropic sparse regularization for spherical harmonic representations of random fields on the sphere
• Compressed sensing and matrix completion with constant proportion of corruptions
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Stable image reconstruction using total variation minimization
• Robust sparse phase retrieval made easy
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• Stability and instance optimality for Gaussian measurements in compressed sensing
• L1Packv2: A Mathematica package for minimizing an \(\ell _{1}\)-penalized functional
• Weaker regularity conditions and sparse recovery in high-dimensional regression
• An asymptotic existence result on compressed sensing matrices
• A survey of compressed sensing
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Sparse recovery under matrix uncertainty
• One-bit compressed sensing by linear programming
• Iteratively reweighted least squares minimization for sparse recovery
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Geometric median and robust estimation in Banach spaces
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials
• Spike detection from inaccurate samplings
• On sparse reconstruction from Fourier and Gaussian measurements
• Discovering governing equations from data by sparse identification of nonlinear dynamical systems
• Inducing sparsity via the horseshoe prior in imaging problems
• Guaranteed clustering and biclustering via semidefinite programming
• Signal Reconstruction From Noisy Random Projections
• Suprema of chaos processes and the restricted isometry property
• Compressed sensing
• Sparse stabilization and control of alignment models
• Recovery of localised structure from signals with non-sparse components
• Nonlinear frames and sparse reconstructions in Banach spaces
• Spectral dynamics and regularization of incompletely and irregularly measured data
• Observability for initial value problems with sparse initial data
• Two-dimensional random projection
• Sparse matrices in frame theory
• Computing non-negative tensor factorizations
• Inexact operator splitting method for monotone inclusion problems
• Approximation of frame based missing data recovery
• Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
• On the generation of sampling schemes for magnetic resonance imaging
• Robust sparse recovery via a novel convex model
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness

This page was built for publication: Stable signal recovery from incomplete and inaccurate measurements

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