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
- 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
- Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
- A short note on compressed sensing with partially known signal support
- Fast and RIP-optimal transforms
- Near oracle performance and block analysis of signal space greedy methods
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Compressed sensing for finite-valued signals
- Linear versus non-linear acquisition of step-functions
- Enhancing sparsity of Hermite polynomial expansions by iterative rotations
- Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
- The Dantzig selector: recovery of signal via ℓ 1 − αℓ 2 minimization
- Image reconstruction for diffuse optical tomography based on radiative transfer equation
- Fast proximity-gradient algorithms for structured convex optimization problems
- Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
- Sparse recovery via differential inclusions
- On the number of harmonic frames
- Two algorithms for compressed sensing of sparse tensors
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Random sampling of bandlimited functions
- \(L_p\)-norm regularization algorithms for optimization over permutation matrices
- Effect of sensing matrices on quality index parameters for block sparse bayesian learning-based EEG compressive sensing
- On support sizes of restricted isometry constants
- Mathematics of analog-to-digital conversion
- An efficient privacy-preserving compressive data gathering scheme in WSNs
- Direct data domain STAP using sparse representation of clutter spectrum
- Projected gradient iteration for nonlinear operator equation
- Idempotents and compressive sampling
- Fast overcomplete dictionary construction with probabilistic guarantees
- Combining line search and trust-region methods forℓ1-minimization
- Signal recovery under mutual incoherence property and oracle inequalities
- Beyond sparsity: the role of \(L_{1}\)-optimizer in pattern classification
- Image decoding optimization based on compressive 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)
