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
- PROMP: a sparse recovery approach to lattice-valued signals
- Exact minimum rank approximation via Schatten \(p\)-norm minimization
- Approximation of solutions with singularities of various types for linear ill-posed problems
- Remote sensing via \(\ell_1\)-minimization
- For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Robust estimation for an inverse problem arising in multiview geometry
- Nonconvex compressed sampling of natural images and applications to compressed MR imaging
- On the size of incoherent systems
- New analysis of manifold embeddings and signal recovery from compressive measurements
- Geometric separation by single-pass alternating thresholding
- A novel sparsity reconstruction method from Poisson data for 3D bioluminescence tomography
- Sparsity enforcing edge detection method for blurred and noisy Fourier data
- Iterative design of concentration factors for jump detection
- Three novel edge detection methods for incomplete and noisy spectral data
- Adaptive data analysis via sparse time-frequency representation
- Instance-optimality in probability with an \(\ell _1\)-minimization decoder
- Perturbations of measurement matrices and dictionaries in compressed sensing
- Average best \(m\)-term approximation
- Mixed linear system estimation and identification
- The stability of a procedure for the recovery of lost samples in band- limited signals
- Sparse approximations with interior point methods
- Sparse solutions of a class of constrained optimization problems
- A unified approach to uniform signal recovery from nonlinear observations
- Lagrangian-penalization algorithm for constrained optimization and variational inequalities
- Particle swarm optimization of compression measurement for signal detection
- Sparse signal recovery with exponential-family noise
- Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions
- Improved bounds for the RIP of subsampled circulant matrices
- Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
- Sparse reconstruction with multiple Walsh matrices
- Stable recovery of sparse signals via \(\ell_p\)-minimization
- A multiplicative Nakagami speckle reduction algorithm for ultrasound images
- First-order optimality condition of basis pursuit denoise problem
- Compressed classification learning with Markov chain samples
- Sparse recovery on Euclidean Jordan algebras
- Wave atoms and sparsity of oscillatory patterns
- Sparsity- and continuity-promoting seismic image recovery with curvelet frames
- Title not available (Why is that?)
- Nonmonotone Barzilai-Borwein gradient algorithm for \(\ell_1\)-regularized nonsmooth minimization in compressive sensing
- A modified Newton projection method for \(\ell _1\)-regularized least squares image deblurring
- Sparse time-frequency representation of nonlinear and nonstationary data
- Compressed sensing with coherent tight frames via \(l_q\)-minimization for \(0 < q \leq 1\)
- Orthogonal matching pursuit under the restricted isometry property
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)
