Sparse Fast Trigonometric Transforms

by Sina Vanessa Bittens
Doctoral thesis
Date of Examination:2019-06-13
Date of issue:2019-07-22
Advisor:Prof. Dr. Gerlind Plonka-Hoch
Referee:Prof. Dr. Gerlind Plonka-Hoch
Referee:Prof. Dr. Felix Krahmer
Referee:Prof. Dr. Daniel Potts
Persistent Address: http://dx.doi.org/10.53846/goediss-7572

 

 

Files in this item

Name:Dissertation_Sina_Bittens_web.pdf
Size:2.00Mb
Format:PDF

The following license files are associated with this item:

Abstract

English

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
 
Statistik