Recovering Wavelet Coefficients from Binary Samples Using Fast Transforms

Abstract

Recovering a signal (function) from finitely many binary or Fourier samples is one of the core problems in modern imaging, and by now there exist a plethora of methods for recovering a signal from such samples. Examples of methods which can utilize wavelet reconstruction include generalized sampling, infinite-dimensional compressive sensing, the parameterized-background data-weak (PBDW) method, etc. However, for any of these methods to be applied in practice, accurate and fast modeling of an N×M 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. Building on the work of Gataric and Poon [SIAM J. Sci. Comput., 38 (2016), pp. A1075--A1099], we derive an algorithm which bypasses the NM storage requirement and the O(NM) computational cost of matrix-vector multiplication with this matrix and its adjoint when using Walsh--Hadamard samples and wavelet reconstruction. The proposed algorithm computes the matrix-vector multiplication in O(NlogN) operations and has a storage requirement of O(2q), where N=2dqM (usually q∈{1,2}) and d=1,2 is the dimension. As matrix-vector multiplications are 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.