Sparse Fast Trigonometric Transforms

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