Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling

DOI10.1016/J.ACHA.2021.04.001MaRDI QIDQ1979911zbMATH OpenOpenAlexFDO

Authors Ben Adcock, Vegard Antun, Anders C. Hansen

Publication date 3 September 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

uniform recoverylocal coherenceinfinite-dimensional compressed sensingsparsity in levelsWalsh samplingwavelet recovery

Mathematics Subject Classification ID

Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Sampling theory in information and communication theory (94A20)

Abstract: Infinite-dimensional compressed sensing deals with the recovery of analog signals (functions) from linear measurements, often in the form of integral transforms such as the Fourier transform. This framework is well-suited to many real-world inverse problems, which are typically modelled in infinite-dimensional spaces, and where the application of finite-dimensional approaches can lead to noticeable artefacts. Another typical feature of such problems is that the signals are not only sparse in some dictionary, but possess a so-called local sparsity in levels structure. Consequently, the sampling scheme should be designed so as to exploit this additional structure. In this paper, we introduce a series of uniform recovery guarantees for infinite-dimensional compressed sensing based on sparsity in levels and so-called multilevel random subsampling. By using a weighted $el{l}^1$-regularizer we derive measurement conditions that are sharp up to log factors, in the sense they agree with those of certain oracle estimators. These guarantees also apply in finite dimensions, and improve existing results for unweighted $el{l}^1$-regularization. To illustrate our results, we consider the problem of binary sampling with the Walsh transform using orthogonal wavelets. Binary sampling is an important mechanism for certain imaging modalities. Through carefully estimating the local coherence between the Walsh and wavelet bases, we derive the first known recovery guarantees for this problem.

Recommendations

• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Generalized sampling and infinite-dimensional compressed sensing
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• On oracle-type local recovery guarantees in compressed sensing

Cites work

• scientific article; zbMATH DE number 49667 (Why is no real title available?)
• scientific article; zbMATH DE number 3510923 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• Breaking the coherence barrier: a new theory for compressed sensing
• Compressed sensing
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Decoding by Linear Programming
• Generalized sampling and infinite-dimensional compressed sensing
• Linear reconstructions and the analysis of the stable sampling rate
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• New Bounds for Restricted Isometry Constants
• On oracle-type local recovery guarantees in compressed sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• On the Theorem of Uniform Recovery of Random Sampling Matrices
• On the stable sampling rate for binary measurements and wavelet reconstruction
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Robustness to Unknown Error in Sparse Regularization
• Sensitivity to Basis Mismatch in Compressed Sensing
• Shifting Inequality and Recovery of Sparse Signals
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Ten Lectures on Wavelets
• Wavelets and filter banks
• Wavelets on the interval and fast wavelet transforms

Cited in

(13)

• scientific article; zbMATH DE number 7626740 (Why is no real title available?)
• Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Infinite-dimensional compressed sensing and function interpolation
• Generalized sampling and infinite-dimensional compressed sensing
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• Compressed sensing with frames and sparsity in levels class
• Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels

Describes a project that uses

Uses Software

• MRI Simulation and Reconstruction

This page was built for publication: Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling

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