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
• Compressive Sensing
• A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions
• Compressive sensing based machine learning strategy for characterizing the flow around a cylinder with limited pressure measurements
• A preconditioning approach for improved estimation of sparse polynomial chaos expansions
• \(\mathrm{L_1RIP}\)-based robust compressed sensing
• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Design of structured dynamic output-feedback controllers for interconnected systems
• Random sampling in reproducing kernel subspaces of \(L^p(\mathbb{R}^n)\)
• On the interval of fluctuation of the singular values of random matrices
• Sensitivity of low-rank matrix recovery
• Dynamical sampling
• Stability Results for Random Sampling of Sparse Trigonometric Polynomials
• Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction
• ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
• The sparsest solutions to \(Z\)-tensor complementarity problems
• A box constrained gradient projection algorithm for compressed sensing
• Compressed sensing and dynamic mode decomposition
• A Donoho-Stark criterion for stable signal recovery in discrete wavelet subspaces
• Phase retrieval for sparse signals
• Compressed sensing from a harmonic analysis point of view
• Compressed sensing with coherent and redundant dictionaries
• Deterministic convolutional compressed sensing matrices
• The non-convex sparse problem with nonnegative constraint for signal reconstruction
• Effective band-limited extrapolation relying on Slepian series and \(\ell^1\) regularization
• A strong restricted isometry property, with an application to phaseless compressed sensing
• Restricted isometries for partial random circulant matrices
• Learning circulant sensing kernels
• Sharp MSE bounds for proximal denoising
• Point source super-resolution via non-convex \(L_1\) based methods
• Simple bounds for recovering low-complexity models
• Computational Aspects of Constrained L 1-L 2 Minimization for Compressive Sensing
• Accelerated projected gradient method for linear inverse problems with sparsity constraints
• Bregman iteration algorithm for sparse nonnegative matrix factorizations via alternating \(l_1\)-norm minimization
• Random sampling of sparse trigonometric polynomials
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• Regularity properties of non-negative sparsity sets
• A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Bayesian signal detection with compressed measurements
• Reconstruction of smooth and discontinuous components of solutions to linear ill-posed problems
• Block sparse recovery via mixed \(l_2/l_1\) minimization
• Compressive wave computation
• Quasi-linear compressed sensing
• Iterative thresholding algorithms
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Dualizable shearlet frames and sparse approximation

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)