Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

DOI10.1109/TIT.2006.885507MaRDI QIDQ3548002zbMATH OpenOpenAlexWikidataFDO

Authors Emmanuel J. Candès, Terence Tao

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0410542

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

Abstract: Suppose we are given a vector $f$ in $R^N$. How many linear measurements do we need to make about $f$ to be able to recover $f$ to within precision $epsilon$ in the Euclidean ($el{l}_2$) metric? Or more exactly, suppose we are interested in a class $calF$ of such objects--discrete digital signals, images, etc; how many linear measurements do we need to recover objects from this class to within accuracy $epsilon$? This paper shows that if the objects of interest are sparse or compressible in the sense that the reordered entries of a signal $fincalF$ decay like a power-law (or if the coefficient sequence of $f$ in a fixed basis decays like a power-law), then it is possible to reconstruct $f$ to within very high accuracy from a small number of random measurements.

Recommendations

• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Decoding by Linear Programming
• Sparsity and incoherence in compressive sampling

Cited in

(only showing first 100 items - show all)

• Concentration of \(S\)-largest mutilated vectors with \(\ell_p\)-quasinorm for \(0<p\leq 1\) and its applications
• A dual split Bregman method for fast \(\ell ^{1}\) minimization
• An overview on the applications of matrix theory in wireless communications and signal processing
• Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
• Near-optimality of linear recovery from indirect observations
• Perturbation Analysis of Orthogonal Least Squares
• Properties and iterative methods for the lasso and its variants
• Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
• On causal extrapolation of sequences with applications to forecasting
• Sparse approximate reconstruction decomposed by two optimization problems
• Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction
• Maximum correntropy adaptation approach for robust compressive sensing reconstruction
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Reconstruction of sparse signals in impulsive disturbance environments
• SRMD: sparse random mode decomposition
• RIPless compressed sensing from anisotropic measurements
• Wavelet denoising via sparse representation
• One-bit sensing, discrepancy and Stolarsky's principle
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparse recovery by non-convex optimization - instance optimality
• A significance test for the lasso
• Sparse recovery under weak moment assumptions
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Compressive sensing-based topology identification of multilayer networks
• Discrete-time scale-shift approach for wavelet construction and analysis
• Generalized sampling and infinite-dimensional compressed sensing
• On the volume of unit balls of finite-dimensional Lorentz spaces
• Approximation of frame based missing data recovery
• Algorithmic versatility of SPF-regularization methods
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Guarantees of total variation minimization for signal recovery
• Super-resolution of point sources via convex programming
• Fast iterative regularization by reusing data
• Signal recovery under cumulative coherence
• The stochastic geometry of unconstrained one-bit data compression
• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• Difference-of-convex learning: directional stationarity, optimality, and sparsity
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• Yang-Baxter equations in quantum information
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• A least-squares method for sparse low rank approximation of multivariate functions
• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• Random projections of smooth manifolds
• Bicomplex signals with sparsity constraints
• 2D compressed learning: support matrix machine with bilinear random projections
• An efficient algorithm based on sparse optimization for the aircraft departure scheduling problem
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Sparsity enforcing edge detection method for blurred and noisy Fourier data
• Sparse signal representation by adaptive non-uniform B-spline dictionaries on a compact interval
• Generalized Kalman smoothing: modeling and algorithms
• Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
• A null space analysis of the _1-synthesis method in dictionary-based compressed sensing
• Gradient estimation with simultaneous perturbation and compressive sensing
• On the generation of sampling schemes for magnetic resonance imaging
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• Stability of \(l_q\)-analysis based dual frame with Weibull matrices for \(0<q\leq 1\)
• A dual active set method for \(\ell1\)-regularized problem
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Cross validation in Lasso and its acceleration
• Gaussian approximations in high dimensional estimation
• Accelerating gradient projection methods for \(\ell _1\)-constrained signal recovery by steplength selection rules
• Compressive sensing with local geometric features
• Slope meets Lasso: improved oracle bounds and optimality
• Fast Phase Retrieval from Local Correlation Measurements
• Total variation wavelet inpainting
• Sparse recovery from inaccurate saturated measurements
• Just least squares: binary compressive sampling with low generative intrinsic dimension
• Polynomial data structure lower bounds in the group model
• Randomized large distortion dimension reduction
• Self-calibration and biconvex compressive sensing
• Spark-level sparsity and the \(\ell_1\) tail minimization
• An efficient Peaceman-Rachford splitting method for constrained TGV-shearlet-based MRI reconstruction
• Phase retrieval from Fourier measurements with masks
• Testing the nullspace property using semidefinite programming
• A general self-adaptive relaxed-PPA method for convex programming with linear constraints
• A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization
• Multiscale blind source separation
• Discussion: ``A significance test for the lasso
• The weighted majority algorithm
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Low complexity regularization of linear inverse problems
• Restoring the signal by modules of measurement
• The Moreau envelope based efficient first-order methods for sparse recovery
• Optimized projections for compressed sensing via rank-constrained nearest correlation matrix
• Ensemble Kalman inversion: a derivative-free technique for machine learning tasks
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Sparse approximation based on a random overcomplete basis
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Derandomizing restricted isometries via the Legendre symbol
• DC approximation approach for \(\ell_0\)-minimization in compressed sensing
• On the uniqueness of sparse time-frequency representation of multiscale data
• Sparse time-frequency decomposition for multiple signals with same frequencies
• Combined supervised information with PCA via discriminative component selection
• On construction of sparse probabilistic Boolean networks.
• Approximation error in regularized SVD-based Fourier continuations
• Fast and RIP-optimal transforms
• The smoothing objective penalty function method for two-cardinality sparse constrained optimization problems
• On the Fourier transform of a quantitative trait: implications for compressive sensing
• Consistency bounds and support recovery of d-stationary solutions of sparse sample average approximations
• Derandomized compressed sensing with nonuniform guarantees for _1 recovery

This page was built for publication: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548002)