Preserving injectivity under subgaussian mappings and its application to compressed sensing

DOI10.1016/J.ACHA.2020.05.006MaRDI QIDQ778017zbMATH OpenOpenAlexWikidataFDO

Authors Xuemei Chen, Richard G. Lynch, Peter G. Casazza

Publication date 30 June 2020

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingframesparsesubgaussiandictionarynull space property

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Inequalities; stochastic orderings (60E15) Randomized algorithms (68W20)

Abstract: The field of compressed sensing has become a major tool in high-dimensional analysis, with the realization that vectors can be recovered from relatively very few linear measurements as long as the vectors lie in a low-dimensional structure, typically the vectors that are zero in most coordinates with respect to a basis. However, there are many applications where we instead want to recover vectors that are sparse with respect to a dictionary rather than a basis. That is, we assume the vectors are linear combinations of at most $s$ columns of a $dimesn$ matrix $mathbfD$, where $s$ is very small relative to $n$ and the columns of $mathbfD$ form a (typically overcomplete) spanning set. In this direction, we show that as a matrix $mathbfD$ stays bounded away from zero in norm on a set $S$ and a provided map $$ comprised of i.i.d. subgaussian rows has number of measurements at least proportional to the square of $w(mathbfDS)$, the Gaussian width of the related set $mathbfDS$, then with high probability the composition $$ also stays bounded away from zero. As a specific application, we obtain that the null space property of order $s$ is preserved under such subgaussian maps with high probability. Consequently, we obtain stable recovery guarantees for dictionary-sparse signals via the $el{l}_1$-synthesis method with only $O(slog(n/s))$ random measurements and a minimal condition on $mathbfD$, which complements the compressed sensing literature.

Recommendations

• Dictionary-sparse recovery from heavy-tailed measurements
• Nonuniform sparse recovery with subgaussian matrices
• Analysis _1-recovery with frames and Gaussian measurements
• Compressive sensing with redundant dictionaries and structured measurements
• A null space analysis of the _1-synthesis method in dictionary-based compressed sensing

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• A brief introduction to Hilbert space frame theory and its applications
• A mathematical introduction to compressive sensing
• A null space analysis of the _1-synthesis method in dictionary-based compressed sensing
• Analysis _1-recovery with frames and Gaussian measurements
• Analysis of inpainting via clustered sparsity and microlocal analysis
• Atomic decomposition by basis pursuit
• Bounding the smallest singular value of a random matrix without concentration
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Compressed Sensing and Redundant Dictionaries
• Compressed sensing with coherent and redundant dictionaries
• Compressive sensing with redundant dictionaries and structured measurements
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Decoding by Linear Programming
• Dictionary-sparse recovery via thresholding-based algorithms
• Estimation in high dimensions: a geometric perspective
• Explicit constructions of RIP matrices and related problems
• Finite frames. Theory and applications.
• Flavors of compressive sensing
• Full spark frames
• Hard thresholding pursuit: an algorithm for compressive sensing
• High-dimensional estimation with geometric constraints
• Improved bounds for sparse recovery from subsampled random convolutions
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On sparse reconstruction from Fourier and Gaussian measurements
• On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Orthogonal matching pursuit under the restricted isometry property
• Perturbations of measurement matrices and dictionaries in compressed sensing
• Robust width: a characterization of uniformly stable and robust compressed sensing
• Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Sparse recovery under weak moment assumptions
• Sparse representations in unions of bases
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• Stable signal recovery from incomplete and inaccurate measurements
• The convex geometry of linear inverse problems
• The gap between the null space property and the restricted isometry property
• Upper and lower bounds for stochastic processes. Modern methods and classical problems

Cited in

(5)

• Sub-Gaussian matrices on sets: optimal tail dependence and applications
• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Dictionary-sparse recovery from heavy-tailed measurements
• A null space analysis of the _1-synthesis method in dictionary-based compressed sensing
• Sampling rates for \(\ell^1\)-synthesis

Describes a project that uses

Uses Software

• CoSaMP
• PDCO

This page was built for publication: Preserving injectivity under subgaussian mappings and its application to compressed sensing

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