Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms

DOI10.1137/21M1427188zbMATH Open1492.94045arXiv2106.00554OpenAlexW3168146183MaRDI QIDQ5864089FDOQ5864089

Authors: Vegard Antun 

Publication date: 3 June 2022

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

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.

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

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

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)

Cites Work

• Matters computational. Ideas, algorithms, source code.
• Probing the Pareto frontier for basis pursuit solutions
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• A wavelet tour of signal processing. The sparse way.
• Ten Lectures on Wavelets
• Methods of conjugate gradients for solving linear systems
• Wavelets on the interval and fast wavelet transforms
• Title not available (Why is that?)
• 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 mathematical introduction to compressive sensing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sensitivity to Basis Mismatch in Compressed Sensing
• Oblique projections, biorthogonal Riesz bases and multiwavelets in Hilbert spaces
• A stability barrier for reconstructions from Fourier samples
• Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors
• GENERAL FRAMEWORK FOR CONSISTENT SAMPLING IN HILBERT SPACES
• Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method
• Title not available (Why is that?)
• Generalized sampling and infinite-dimensional compressed sensing
• A generalized sampling theorem for stable reconstructions in arbitrary bases
• A generalized sampling theory without band-limiting constraints
• 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
• Consistent Sampling and Signal Recovery
• A consistent and stable approach to generalized sampling
• Generalized sampling reconstruction from Fourier measurements using compactly supported shearlets
• Linear Stable Sampling Rate: Optimality of 2D Wavelet Reconstructions from Fourier Measurements
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• A practical guide to the recovery of wavelet coefficients from Fourier measurements
• Introduction to the mathematics of medical imaging.
• A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics
• PBDW state estimation: noisy observations; configuration-adaptive background spaces; physical interpretations
• Data Assimilation in Reduced Modeling
• Data assimilation and sampling in Banach spaces
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• On the stable sampling rate for binary measurements and wavelet reconstruction
• Linear reconstructions and the analysis of the stable sampling rate
• On the unification of schemes and software for wavelets on the interval
• The Gap between Theory and Practice in Function Approximation with Deep Neural Networks
• Optimal Compressive Imaging of Fourier Data
• Close Encounters of the Binary Kind: Signal Reconstruction Guarantees for Compressive Hadamard Sampling With Haar Wavelet Basis
• Compressive Imaging: Structure, Sampling, Learning

Cited In (1)

• Wavelet compressive sampling signal reconstruction using upside-down tree structure

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)