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)

• 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 ℓ ₁ − αℓ ₂ 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
• Refined analysis of sparse MIMO radar
• Sparse representation of signals in Hardy space
• Kernel sparse representation for time series classification
• Noise folding in completely perturbed compressed sensing
• Decomposable norm minimization with proximal-gradient homotopy algorithm
• Sparse decomposition by iterating Lipschitzian-type mappings
• Sparse signal recovery using a new class of random matrices
• Data based identification and prediction of nonlinear and complex dynamical systems
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• 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

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)