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)

• 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 𝓁₁‐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
• Concave programming for finding sparse solutions to problems with convex constraints
• A variable fixing version of the two-block nonlinear constrained Gauss-Seidel algorithm for \(\ell_1\)-regularized least-squares
• A consistent and stable approach to generalized sampling
• \(l_p\)-recovery of the most significant subspace among multiple subspaces with outliers
• Log-concavity and strong log-concavity: a review
• Signal Sampling and Recovery Under Dependent Errors
• Reconstruction of nonuniformly sampled time-limited signals using prolate spheroidal wave functions
• Separate reconstruction of solution components with singularities of various types for linear operator equations of the first kind
• Extreme point inequalities and geometry of the rank sparsity ball
• Capturing ridge functions in high dimensions from point queries
• The null space property for sparse recovery from multiple measurement vectors
• On the sparseness of 1-norm support vector machines
• A half thresholding projection algorithm for sparse solutions of LCPs
• Compressed sensing of low-rank plus sparse matrices
• Sparse linear regression from perturbed data
• Sparse regularization for semi-supervised classification
• Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements
• 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

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)