Stable signal recovery from incomplete and inaccurate measurements
From MaRDI portal
Publication:5486267
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
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
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
- Compressive Sensing
- A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
- Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
- A preconditioning approach for improved estimation of sparse polynomial chaos expansions
- \(\mathrm{L_1RIP}\)-based robust compressed sensing
- Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
- Design of structured dynamic output-feedback controllers for interconnected systems
- Random sampling in reproducing kernel subspaces of \(L^p(\mathbb{R}^n)\)
- On the interval of fluctuation of the singular values of random matrices
- Sensitivity of low-rank matrix recovery
- Dynamical sampling
- Stability Results for Random Sampling of Sparse Trigonometric Polynomials
- Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction
- ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
- The sparsest solutions to \(Z\)-tensor complementarity problems
- A box constrained gradient projection algorithm for compressed sensing
- Compressed sensing and dynamic mode decomposition
- A Donoho-Stark criterion for stable signal recovery in discrete wavelet subspaces
- Phase retrieval for sparse signals
- Compressed sensing from a harmonic analysis point of view
- Compressed sensing with coherent and redundant dictionaries
- Deterministic convolutional compressed sensing matrices
- The non-convex sparse problem with nonnegative constraint for signal reconstruction
- Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization
- A strong restricted isometry property, with an application to phaseless compressed sensing
- Restricted isometries for partial random circulant matrices
- Learning circulant sensing kernels
- Sharp MSE bounds for proximal denoising
- Point source super-resolution via non-convex \(L_1\) based methods
- Simple bounds for recovering low-complexity models
- Computational Aspects of Constrained L 1-L 2 Minimization for Compressive Sensing
- Accelerated projected gradient method for linear inverse problems with sparsity constraints
- Bregman iteration algorithm for sparse nonnegative matrix factorizations via alternating \(l_1\)-norm minimization
- Random sampling of sparse trigonometric polynomials
- 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
- Regularity properties of non-negative sparsity sets
- A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
- Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
- Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
- Bayesian signal detection with compressed measurements
- Reconstruction of smooth and discontinuous components of solutions to linear ill-posed problems
- Block sparse recovery via mixed \(l_2/l_1\) minimization
- Compressive wave computation
- Quasi-linear compressed sensing
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)
