Sparse Fast Trigonometric Transforms
von Sina Vanessa Bittens
Datum der mündl. Prüfung:2019-06-13
Erschienen:2019-07-22
Betreuer:Prof. Dr. Gerlind Plonka-Hoch
Gutachter:Prof. Dr. Gerlind Plonka-Hoch
Gutachter:Prof. Dr. Felix Krahmer
Gutachter:Prof. Dr. Daniel Potts
Dateien
Name:Dissertation_Sina_Bittens_web.pdf
Size:2.00Mb
Format:PDF
Zusammenfassung
Englisch
Trigonometric transforms like the Fourier transform or the discrete cosine transform (DCT) are of immense importance in signal and image processing, physics, engineering, and data processing. The research of past decades has provided us with runtime optimal algorithms for these transforms. Significant runtime improvements are only possible if there is additional a priori information about the sparsity of the signal. In the first part of this thesis we develop sublinear algorithms for the fast Fourier transform for frequency sparse periodic functions. We investigate three classes of sparsity: short frequency support, polynomially structured sparsity and block sparsity. For all three classes we present new deterministic, sublinear algorithms that recover the Fourier coefficients of periodic functions from samples. We prove theoretical runtime and sampling bounds for all algorithms and also investigate their performance in numerical experiments. In the second part of this thesis we focus on the reconstruction of vectors with short support from their DCT of type II. We present two different new, deterministic and sublinear algorithms for this problem. The first method is based on inverse discrete Fourier transforms and uses complex arithmetic, whereas the second one utilizes properties of the DCT and only employs real arithmetic. We show theoretical runtime and sampling bounds for both algorithms and compare them numerically in experiments. Furthermore, we generalize the techniques for recovering vectors with short support from their DCT of type II using only real arithmetic to the two-dimensional setting of recovering matrices with block support, also providing theoretical runtime and sampling complexities for the obtained new two-dimensional algorithm.
Keywords: Sparse Fourier transform; structured sparsity; approximation algorithms; discrete Fourier transform; deterministic sparse FFT; sublinear sparse FFT; discrete cosine transform; deterministic sparse fast DCT; sublinear sparse DCT