Stable signal recovery from incomplete and inaccurate measurements
From MaRDI portal
(Redirected from Publication:5486267)
Statistical aspects of information-theoretic topics (62B10) Numerical optimization and variational techniques (65K10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Rate-distortion theory in information and communication theory (94A34)
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.
Recommendations
Cited in
(only showing first 100 items - show all)- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
- Random projections of smooth manifolds
- Compressive sensing for subsurface imaging using ground penetrating radar
- Sparse solutions to underdetermined Kronecker product systems
- A simple proof of the restricted isometry property for random matrices
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
- Mixed linear system estimation and identification
- Geometric median and robust estimation in Banach spaces
- The stability of a procedure for the recovery of lost samples in band- limited signals
- Discovering governing equations from data by sparse identification of nonlinear dynamical systems
- A regularizing multilevel approach for nonlinear inverse problems
- A general family of trimmed estimators for robust high-dimensional data analysis
- 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
- Computation of sparse and dense equilibrium strategies of evolutionary games
- Sparse recovery from inaccurate saturated measurements
- Surface inpainting with sparsity constraints
- Observable dictionary learning for high-dimensional statistical inference
- Sparse approximate solution of fitting surface to scattered points by MLASSO model
- Compressed sensing for real measurements of quaternion signals
- On the uniqueness of the sparse signals reconstruction based on the missing samples variation analysis
- Expander \(\ell_0\)-decoding
- PROMP: a sparse recovery approach to lattice-valued signals
- A conjugate subgradient algorithm with adaptive preconditioning for the least absolute shrinkage and selection operator minimization
- Sparsity enabled cluster reduced-order models for control
- The matrix splitting based proximal fixed-point algorithms for quadratically constrained \(\ell_{1}\) minimization and Dantzig selector
- Online fault diagnosis for nonlinear power systems
- Approximating sampled sinusoids and multiband signals using multiband modulated DPSS dictionaries
- Smoothed _1-regularization-based line search for sparse signal recovery
- Fast state-space methods for inferring dendritic synaptic connectivity
- Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences
- Learning data discretization via convex optimization
- Geometric separation in \(\mathbb{R}^3\)
- A new nonconvex approach to low-rank matrix completion with application to image inpainting
- Compressed sensing with structured sparsity and structured acquisition
- Recovery of signals under the condition on RIC and ROC via prior support information
- A computational study of the role of spatial receptive field structure in processing natural and non-natural scenes
- Sparse signal reconstruction based on multiparameter approximation function with smoothed _0 norm
- Roles of clustering coefficient for the network reconstruction
- Linear total variation approximate regularized nuclear norm optimization for matrix completion
- Signal recovery under mutual incoherence property and oracle inequalities
- Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
- On monotone and primal-dual active set schemes for \(\ell^p\)-type problems, \(p \in (0,1]\)
- Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
- Data-based prediction and causality inference of nonlinear dynamics
- Fast L1-L2 minimization via a proximal operator
- Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing
- Dictionary evaluation and optimization for sparse coding based speech processing
- Adaptive compressive learning for prediction of protein-protein interactions from primary sequence
- On the sparseness of 1-norm support vector machines
- Robust group lasso: model and recoverability
- Sparse feedback design in discrete-time linear systems
- Customized dictionary learning for subdatasets with fine granularity
- Peeling decoding of LDPC codes with applications in compressed sensing
- A novel detection scheme with multiple observations for sparse signal based on likelihood ratio test with sparse estimation
- Norm-minimized scattering data from intensity spectra
- Augmented sparse reconstruction of protein signaling networks
- Self-adaptive image reconstruction inspired by insect compound eye mechanism
- CONFIGR: a vision-based model for long-range figure completion
- Robust estimation for an inverse problem arising in multiview geometry
- An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems
- Compressed sensing and matrix completion with constant proportion of corruptions
- Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements
- Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
- Thresholding-based iterative selection procedures for model selection and shrinkage
- The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
- New nonsmooth equations-based algorithms for _1-norm minimization and applications
- Reconstruction of nonuniformly sampled time-limited signals using prolate spheroidal wave functions
- A short note on compressed sensing with partially known signal support
- A preconditioning approach for improved estimation of sparse polynomial chaos expansions
- A simple and flexible model order reduction method for FFT-based homogenization problems using a sparse sampling technique
- A data-driven framework for sparsity-enhanced surrogates with arbitrary mutually dependent randomness
- Debiasing the Lasso: optimal sample size for Gaussian designs
- Reconstructed error and linear representation coefficients restricted by \(\ell_1\)-minimization for face recognition under different illumination and occlusion
- Sparse signal inversion with impulsive noise by dual spectral projected gradient method
- Sparse approximation of fitting surface by elastic net
- Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
- A performance guarantee for orthogonal matching pursuit using mutual coherence
- Sparse approximate reconstruction decomposed by two optimization problems
- Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction
- Sparse principal component analysis via fractional function regularity
- A new linearized split Bregman iterative algorithm for image reconstruction in sparse-view X-ray computed tomography
- An algebraic perspective on integer sparse recovery
- Deterministic constructions of compressed sensing matrices based on optimal codebooks and codes
- Noisy Euclidean distance matrix completion with a single missing node
- Properties and iterative methods for the \(Q\)-lasso
- Compressed data separation via dual frames based split-analysis with Weibull matrices
- On recovery guarantees for one-bit compressed sensing on manifolds
- On the interplay between acceleration and identification for the proximal gradient algorithm
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- On the \(\ell^\infty\)-norms of the singular vectors of arbitrary powers of a difference matrix with applications to sigma-delta quantization
- Dual-density-based reweighted \(\ell_1\)-algorithms for a class of \(\ell_0\)-minimization problems
- Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
- Memoryless scalar quantization for random frames
- Sparse approximate solutions to max-plus equations
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)
