Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms

DOI10.1137/21M1427188MaRDI QIDQ5864089zbMATH OpenOpenAlexFDO

Authors Vegard Antun

Publication date 3 June 2022

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

waveletssampling theoryWalsh functionsfast transformsWalsh-Hadamard samples

Mathematics Subject Classification ID

Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for wavelets (65T60) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product) (46C05) Sampling theory in information and communication theory (94A20) Application of orthogonal and other special functions (94A11)

Abstract: Recovering a signal (function) from finitely many binary or Fourier samples is one of the core problems in modern medical imaging, and by now there exist a plethora of methods for recovering a signal from such samples. Examples of methods, which can utilise wavelet reconstruction, include generalised sampling, infinite-dimensional compressive sensing, the parameterised-background data-weak (PBDW) method etc. However, for any of these methods to be applied in practice, accurate and fast modelling of an $NimesM$ section of the infinite-dimensional change-of-basis matrix between the sampling basis (Fourier or Walsh-Hadamard samples) and the wavelet reconstruction basis is paramount. In this work, we derive an algorithm, which bypasses the $NM$ storage requirement and the $mathcalO(NM)$ computational cost of matrix-vector multiplication with this matrix when using Walsh-Hadamard samples and wavelet reconstruction. The proposed algorithm computes the matrix-vector multiplication in $mathcalO(NlogN)$ operations and has a storage requirement of $mathcalO(2^q)$, where $N=2^{dq}M$, (usually $qin1,2$) and $d=1,2$ is the dimension. As matrix-vector multiplications is the computational bottleneck for iterative algorithms used by the mentioned reconstruction methods, the proposed algorithm speeds up the reconstruction of wavelet coefficients from Walsh-Hadamard samples considerably.

Recommendations

• On reconstructing functions from binary measurements
• Derivation of fast algorithms via binary filtering of signals
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Time-frequency analysis in the discrete phase plane
• The algorithm research of fast multiwavelet transform based on FFT
• Explicit universal sampling sets in finite vector spaces
• An improved fast algorithm based on wavelet transform
• On the computation of wavelet coefficients
• scientific article; zbMATH DE number 802859
• A practical guide to the recovery of wavelet coefficients from Fourier measurements

Cites work

• scientific article; zbMATH DE number 2131802 (Why is no real title available?)
• scientific article; zbMATH DE number 49667 (Why is no real title available?)
• scientific article; zbMATH DE number 3510923 (Why is no real title available?)
• scientific article; zbMATH DE number 1215245 (Why is no real title available?)
• A consistent and stable approach to generalized sampling
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A generalized empirical interpolation method: application of reduced basis techniques to data assimilation
• A generalized sampling theorem for stable reconstructions in arbitrary bases
• A generalized sampling theory without band-limiting constraints
• A mathematical introduction to compressive sensing
• A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics
• A practical guide to the recovery of wavelet coefficients from Fourier measurements
• A stability barrier for reconstructions from Fourier samples
• A wavelet tour of signal processing. The sparse way.
• Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem
• Breaking the coherence barrier: a new theory for compressed sensing
• Close Encounters of the Binary Kind: Signal Reconstruction Guarantees for Compressive Hadamard Sampling With Haar Wavelet Basis
• Compressive imaging: structure, sampling, learning. With contributions by Vegard Antun
• Consistent Sampling and Signal Recovery
• Data Assimilation in Reduced Modeling
• Data assimilation and sampling in Banach spaces
• GENERAL FRAMEWORK FOR CONSISTENT SAMPLING IN HILBERT SPACES
• Generalized sampling and infinite-dimensional compressed sensing
• Generalized sampling reconstruction from Fourier measurements using compactly supported shearlets
• Introduction to the mathematics of medical imaging.
• Linear Stable Sampling Rate: Optimality of 2D Wavelet Reconstructions from Fourier Measurements
• Linear reconstructions and the analysis of the stable sampling rate
• Matters computational. Ideas, algorithms, source code.
• Methods of conjugate gradients for solving linear systems
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Oblique projections, biorthogonal Riesz bases and multiwavelets in Hilbert spaces
• 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 stable sampling rate for binary measurements and wavelet reconstruction
• On the unification of schemes and software for wavelets on the interval
• Optimal compressive imaging of Fourier data
• PBDW state estimation: noisy observations; configuration-adaptive background spaces; physical interpretations
• Probing the Pareto frontier for basis pursuit solutions
• Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method
• Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors
• Sensitivity to Basis Mismatch in Compressed Sensing
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Ten Lectures on Wavelets
• The gap between theory and practice in function approximation with deep neural networks
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• Wavelets on the interval and fast wavelet transforms

Cited in

(3)

• On the stable sampling rate for binary measurements and wavelet reconstruction
• Wavelet compressive sampling signal reconstruction using upside-down tree structure
• On reconstructing functions from binary measurements

Describes a project that uses

Uses Software

• FXT
• hfloat
• SPGL1
• WaveLab
• MRI Simulation and Reconstruction
• infCS

This page was built for publication: Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms

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