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
• Adaptive compressive learning for prediction of protein-protein interactions from primary sequence
• Convergence of a data-driven time-frequency analysis method
• Compressive total variation for image reconstruction and restoration
• Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
• Compression and Conditional Emulation of Climate Model Output
• A regularizing multilevel approach for nonlinear inverse problems
• Linear total variation approximate regularized nuclear norm optimization for matrix completion
• The modified accelerated Bregman method for regularized basis pursuit problem
• Signal recovery from incomplete measurements in the presence of outliers
• Localized Fourier analysis for graph signal processing
• On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1]\)
• A general family of trimmed estimators for robust high-dimensional data analysis
• Sparsest representations and approximations of an underdetermined linear system
• Learning and sparse control of multiagent systems
• Polynomial-exponential decomposition from moments
• On the approximate discrete KLT of fractional Brownian motion and applications
• Signal recovery under cumulative coherence
• Debiasing the Lasso: optimal sample size for Gaussian designs
• A spread-return mean-reverting model for credit spread dynamics
• Sparse recovery from inaccurate saturated measurements
• Foundations of gauge and perspective duality
• Mathematics of electron tomography
• Surface inpainting with sparsity constraints
• Sparse proximal support vector machine with a specialized interior-point method
• Bayesian computation: a summary of the current state, and samples backwards and forwards
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• Noise-shaping quantization methods for frame-based and compressive sampling systems
• Frames for compressed sensing using coherence
• Observable dictionary learning for high-dimensional statistical inference
• Separating signal from noise
• An \(l_0\)-norm based color image deblurring model under mixed random-valued impulse and Gaussian noise
• Sparse approximate solution of fitting surface to scattered points by MLASSO model
• Compressed sensing for real measurements of quaternion signals
• The extensions of convergence rates of Kaczmarz-type methods
• \(\ell_1\) minimization with noisy data
• On the uniqueness of the sparse signals reconstruction based on the missing samples variation analysis
• Expander \(\ell_0\)-decoding
• Sparse solutions to underdetermined Kronecker product systems
• A conjugate subgradient algorithm with adaptive preconditioning for the least absolute shrinkage and selection operator minimization

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)