A Probabilistic and RIPless Theory of Compressed Sensing
From MaRDI portal
Abstract: This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all models - e.g. Gaussian, frequency measurements - discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) - they make use of a much weaker notion - or a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s log n Fourier coefficients that are contaminated with noise.
Cited in
(82)- Infinite-dimensional compressed sensing and function interpolation
- Relaxed sparse eigenvalue conditions for sparse estimation via non-convex regularized regression
- Bias reduction in variational regularization
- Sparsity and incoherence in orthogonal matching pursuit
- Compressed sensing with structured sparsity and structured acquisition
- Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
- Robust group lasso: model and recoverability
- Compressed sensing and matrix completion with constant proportion of corruptions
- Phase retrieval from Fourier measurements with masks
- A non-convex regularization approach for compressive sensing
- Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?
- Low-rank matrix completion in a general non-orthogonal basis
- New regularization method and iteratively reweighted algorithm for sparse vector recovery
- Prediction bounds for higher order total variation regularized least squares
- Randomized signal processing with continuous frames
- Learning ``best kernels from data in Gaussian process regression. With application to aerodynamics
- Proof methods for robust low-rank matrix recovery
- On the Fourier transform of a quantitative trait: implications for compressive sensing
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Blind three dimensional deconvolution via convex optimization
- Geological facies recovery based on weighted \(\ell_1\)-regularization
- Variance-based adaptive sequential sampling for polynomial chaos expansion
- Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
- One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations
- On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
- Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
- A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions
- Basis adaptive sample efficient polynomial chaos (BASE-PC)
- RIPless compressed sensing from anisotropic measurements
- Locally sparse reconstruction using the \(\ell^{1,\infty}\)-norm
- Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
- Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
- Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
- The geometry of off-the-grid compressed sensing
- Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
- Low complexity regularization of linear inverse problems
- Breaking the coherence barrier: a new theory for compressed sensing
- On reconstructing functions from binary measurements
- Reconstruction methods in THz single-pixel imaging
- Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation
- Compressive sensing with redundant dictionaries and structured measurements
- Self-calibration and biconvex compressive sensing
- A survey of compressed sensing
- The quest for optimal sampling: computationally efficient, structure-exploiting measurements for compressed sensing
- Improved recovery guarantees for phase retrieval from coded diffraction patterns
- Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
- Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
- Remote sensing via _1-minimization
- Extracting Sparse High-Dimensional Dynamics from Limited Data
- Compressed Sensing Performance Bounds Under Poisson Noise
- Asymptotic Achievability of the CramÉr–Rao Bound for Noisy Compressive Sampling
- Theory of Sparse Coprime Sensing in Multiple Dimensions
- High-dimensional estimation with geometric constraints
- Hinge-minimax learner for the ensemble of hyperplanes
- Structured random measurements in signal processing
- Sparse polynomial chaos expansions: literature survey and benchmark
- Submatrices with nonuniformly selected random supports and insights into sparse approximation
- Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained _1 minimization
- Time Series Source Separation Using Dynamic Mode Decomposition
- Extracting Structured Dynamical Systems Using Sparse Optimization With Very Few Samples
- Generalized sampling and infinite-dimensional compressed sensing
- A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
- On the role of total variation in compressed sensing
- On the generation of sampling schemes for magnetic resonance imaging
- Nonuniform recovery of fusion frame structured sparse signals
- Sparse learning of partial differential equations with structured dictionary matrix
- A survey on compressive sensing: classical results and recent advancements
- Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
- Short Communication: Localized Adversarial Artifacts for Compressed Sensing MRI
- Universal Features for High-Dimensional Learning and Inference
- A Variable Density Sampling Scheme for Compressive Fourier Transform Interferometry
- Structured model selection via ℓ1−ℓ2 optimization
- Off-the-grid prediction and testing for linear combination of translated features
- Simultaneous off-the-grid learning of mixtures issued from a continuous dictionary
- Sample complexity bounds for the local convergence of least squares approximation
- Duality theory on generalized singular values and its applications
- Accelerated stochastic approximation with state-dependent noise
- Adapted variable density subsampling for compressed sensing
- Foveated compressed sensing
- DFT spectrum-sparsity-based quasi-periodic signal identification and application
- Hard thresholding pursuit algorithms: number of iterations
- Analysis of sparse MIMO radar
This page was built for publication: A Probabilistic and RIPless Theory of Compressed Sensing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272230)
