Preserving injectivity under subgaussian mappings and its application to compressed sensing

DOI10.1016/J.ACHA.2020.05.006zbMATH Open1448.94053arXiv1710.09972OpenAlexW3030280132WikidataQ122887637 ScholiaQ122887637MaRDI QIDQ778017FDOQ778017

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

Publication date: 30 June 2020

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

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.

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Title not available (Why is that?)
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Decoding by Linear Programming
• Stable signal recovery from incomplete and inaccurate measurements
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A mathematical introduction to compressive sensing
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Finite frames. Theory and applications.
• Upper and Lower Bounds for Stochastic Processes
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• The gap between the null space property and the restricted isometry property
• On sparse reconstruction from Fourier and Gaussian measurements
• Sparse representations in unions of bases
• Sparse recovery under weak moment assumptions
• A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• The convex geometry of linear inverse problems
• 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
• Compressed Sensing and Redundant Dictionaries
• Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries
• Full spark frames
• Explicit constructions of RIP matrices and related problems
• Compressed sensing with coherent and redundant dictionaries
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• A brief introduction to Hilbert space frame theory and its applications
• Hard Thresholding Pursuit: An Algorithm for Compressive Sensing
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Instance-optimality in probability with an \(\ell _1\)-minimization decoder
• Perturbations of measurement matrices and dictionaries in compressed sensing
• Orthogonal matching pursuit under the restricted isometry property
• Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing
• Improved bounds for sparse recovery from subsampled random convolutions
• Estimation in High Dimensions: A Geometric Perspective
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• High-dimensional estimation with geometric constraints: Table 1.
• Flavors of Compressive Sensing
• On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions
• Dictionary-sparse recovery via thresholding-based algorithms

Cited In (3)

• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Dictionary-sparse recovery from heavy-tailed measurements
• Sampling rates for \(\ell^1\)-synthesis

Uses Software

• PDCO
• CoSaMP

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)