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)

• Majorizing measures and proportional subsets of bounded orthonormal systems
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Compressive sensing for multi-static scattering analysis
• Extensions of compressed sensing
• 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
• Nonlinear least squares in \(\mathbb R^{N}\)
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• A unified approach to model selection and sparse recovery using regularized least squares
• The weighted majority algorithm
• Signal recovery under cumulative coherence
• Sparse recovery from inaccurate saturated measurements
• Improved bounds for sparse recovery from subsampled random convolutions
• Sparse approximate solution of fitting surface to scattered points by MLASSO model
• Landmark recognition with sparse representation classification and extreme learning machine
• Prediction of protein-protein interaction by metasample-based sparse representation
• Expander \(\ell_0\)-decoding
• Generalized Kalman smoothing: modeling and algorithms
• The matrix splitting based proximal fixed-point algorithms for quadratically constrained \(\ell_{1}\) minimization and Dantzig selector
• Analysis of the equivalence relationship between \(l_{0}\)-minimization and \(l_{p}\)-minimization
• A hierarchical framework for recovery in compressive sensing
• Local variable selection of nonlinear nonparametric systems by first order expansion
• Deterministic construction of compressed sensing matrices based on semilattices
• Sparse probit linear mixed model
• Robustness properties of dimensionality reduction with Gaussian random matrices
• Random matrices and erasure robust frames
• Accelerating near-field 3D imaging approach for joint high-resolution imaging and phase error correction
• Sparsity and incoherence in orthogonal matching pursuit
• Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
• Compressed sensing with structured sparsity and structured acquisition
• Sparse signal reconstruction based on multiparameter approximation function with smoothed _0 norm
• TV+TV regularization with nonconvex sparseness-inducing penalty for image restoration
• Roles of clustering coefficient for the network reconstruction
• Median filter based compressed sensing model with application to MR image reconstruction
• Signature codes for weighted noisy adder channel, multimedia fingerprinting and compressed sensing
• Signal recovery under mutual incoherence property and oracle inequalities
• Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
• An overview on the applications of matrix theory in wireless communications and signal processing
• Near-optimality of linear recovery from indirect observations
• Learning semidefinite regularizers
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• Spark-level sparsity and the _1 tail minimization
• Multiscale blind source separation
• Approximation error in regularized SVD-based Fourier continuations
• Adaptive compressive learning for prediction of protein-protein interactions from primary sequence
• High-dimensional inference: confidence intervals, \(p\)-values and R-software \texttt{hdi}
• Robust group lasso: model and recoverability
• Combined similarity to reference image with joint sparsifying transform for longitudinal compressive sensing MRI
• Efficient extreme learning machine via very sparse random projection
• Augmented sparse reconstruction of protein signaling networks
• From low- to high-dimensional moments without magic
• Self-adaptive image reconstruction inspired by insect compound eye mechanism
• Strengthening hash families and compressive sensing
• How well can we estimate a sparse vector?
• An efficient algorithm for \(\ell_{0}\) minimization in wavelet frame based image restoration
• Proximity algorithms for the L1/TV image denoising model
• Primal and dual alternating direction algorithms for \(\ell _{1}\)-\(\ell _{1}\)-norm minimization problems in compressive sensing
• Detecting a vector based on linear measurements
• A recursive procedure for density estimation on the binary hypercube
• Compressed sensing of color images
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing
• An enhanced diagnosis method for weak fault features of bearing acoustic emission signal based on compressed sensing
• Parallel magnetic resonance imaging acceleration with a hybrid sensing approach
• Phase retrieval from Fourier measurements with masks
• Compressed sparse tensor based quadrature for vibrational quantum mechanics integrals
• A simple and flexible model order reduction method for FFT-based homogenization problems using a sparse sampling technique
• Slope meets Lasso: improved oracle bounds and optimality
• Reconstructed error and linear representation coefficients restricted by \(\ell_1\)-minimization for face recognition under different illumination and occlusion
• Sparse approximation of fitting surface by elastic net
• Rapid compressed sensing reconstruction: a semi-tensor product approach
• Recursion for the smallest eigenvalue density of \(\beta \)-Wishart-Laguerre ensemble
• 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
• Sparse system identification for stochastic systems with general observation sequences
• Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction
• Maximum correntropy adaptation approach for robust compressive sensing reconstruction
• A simple and feasible method for a class of large-scale \(l^1\)-problems
• 2D compressed learning: support matrix machine with bilinear random projections
• An efficient algorithm based on sparse optimization for the aircraft departure scheduling problem
• A general self-adaptive relaxed-PPA method for convex programming with linear constraints
• Large deviations, dynamics and phase transitions in large stochastic and disordered neural networks
• Consistency bounds and support recovery of d-stationary solutions of sparse sample average approximations
• Low-rank matrix completion in a general non-orthogonal basis
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• Finite impulse response models: a non-asymptotic analysis of the least squares estimator
• Separable collusion-secure multimedia codes
• Memoryless scalar quantization for random frames
• RWRM: residual Wasserstein regularization model for image restoration
• Efficiency of orthogonal super greedy algorithm under the restricted isometry property
• On data compression and recovery for sequences using constraints on the spectrum range
• Two-stage geometric information guided image reconstruction
• A simple recovery framework for signals with time-varying sparse support
• Analysis of Termatiko sets in measurement matrices
• Sparse parameter identification of stochastic dynamical systems
• Fast and memory-optimal dimension reduction using Kac's walk
• The proximity operator of the log-sum penalty

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)