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)

• 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
• Influence factors of sparse microwave imaging radar system performance: approaches to waveform design and platform motion analysis
• Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain
• Reweighted minimization model for MR image reconstruction with split Bregman method
• The essential ability of sparse reconstruction of different compressive sensing strategies
• Sparse microwave imaging: principles and applications
• Sparse SAR imaging based on \(L_{1/2}\) regularization
• Recovery of high-dimensional sparse signals via \(\ell_1\)-minimization
• Democracy in action: quantization, saturation, and compressive sensing
• Computation of sparse and dense equilibrium strategies of evolutionary games
• Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection
• Compressed sensing-based reconstruction for computed tomography with translational trajectory
• The restricted isometry property for time-frequency structured random matrices
• Analysis of compressed distributed adaptive filters
• Sparsity and non-Euclidean embeddings
• On exact recovery of sparse vectors from linear measurements
• Multiple suboptimal solutions for prediction rules in gene expression data
• Coupling the gradient method with a general exterior penalization scheme for convex minimization
• Restricted \(p\)-isometry property and its application for nonconvex compressive sensing
• A weighted difference of anisotropic and isotropic total variation model for image processing
• Multicontrast MRI reconstruction with structure-guided total variation
• Minimization of \(\ell_{1-2}\) for compressed sensing
• Compressive sensing for subsurface imaging using ground penetrating radar
• Sparsity in penalized empirical risk minimization
• The nonnegative zero-norm minimization under generalized \(Z\)-matrix measurement
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Deterministic constructions of compressed sensing matrices based on codes
• Sparsity in time-frequency representations
• A new computational method for the sparsest solutions to systems of linear equations
• 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

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)