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)

• Fast convex pruning of deep neural networks
• A statistical approach to the problem of restoring damaged and contaminated images
• Sparse signals recovered by non-convex penalty in quasi-linear systems
• Atmospheric radar imaging improvements using compressed sensing and MIMO
• Generalized Mercer kernels and reproducing kernel Banach spaces
• Iteratively weighted thresholding homotopy method for the sparse solution of underdetermined linear equations
• Sparse recovery via nonconvex regularized \(M\)-estimators over \(\ell_q\)-balls
• A note on the minimization of a Tikhonov functional with \(\ell^1\)-penalty
• Sparse regression: scalable algorithms and empirical performance
• Data science, big data and statistics
• Sparse approximate solution of partial differential equations
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• A computational study of the role of spatial receptive field structure in processing natural and non-natural scenes
• Low complexity regularization of linear inverse problems
• On the interplay between acceleration and identification for the proximal gradient algorithm
• Estimation of block sparsity in compressive sensing
• Frames induced by the action of continuous powers of an operator
• Surface Reconstruction via L 1-Minimization
• Mathematical methods in biomedical imaging
• A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
• On sparse approximations of solutions to linear systems with orthogonal matrices
• Robust multi-image processing with optimal sparse regularization
• Compressive statistical learning with random feature moments
• A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
• RBF-network based sparse signal recovery algorithm for compressed sensing reconstruction
• GPU accelerated greedy algorithms for compressed sensing
• A note on linear function approximation using random projections
• Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization
• Adaptive projected gradient thresholding methods for constrained \(l_0\) problems
• Geometric separation of singularities using combined multiscale dictionaries
• Stability of the elastic net estimator
• Subset selection in sparse matrices
• Nonlinear approximation spaces for inverse problems
• Noisy 1-bit compressive sensing: models and algorithms
• From compression to compressed sensing
• Primal-dual first-order methods for a class of cone programming
• Complete set of translation invariant measurements with Lipschitz bounds
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• The \(\ell_{2,q}\) regularized group sparse optimization: lower bound theory, recovery bound and algorithms
• Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
• Minimization of \(L_1\) over \(L_2\) for sparse signal recovery with convergence guarantee
• Explicit universal sampling sets in finite vector spaces
• Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm
• A theoretical investigation of Brockett's ensemble optimal control problems
• Effective zero-norm minimization algorithms for noisy compressed sensing
• Robust dequantized compressive sensing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric separation in \(\mathbb{R}^3\)
• Recovering an unknown signal completely submerged in strong noise by a new stochastic resonance method
• Complexity of approximation of functions of few variables in high dimensions
• Regularization of inverse problems via time discrete geodesics in image spaces
• An algebraic perspective on integer sparse recovery
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Proof methods for robust low-rank matrix recovery
• Greedy signal space methods for incoherence and beyond
• 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

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)