Zur Kurzanzeige

Sparse Fast Trigonometric Transforms

dc.contributor.advisorPlonka-Hoch, Gerlind Prof. Dr.
dc.contributor.authorBittens, Sina Vanessa
dc.date.accessioned2019-07-22T08:59:15Z
dc.date.available2019-07-22T08:59:15Z
dc.date.issued2019-07-22
dc.identifier.urihttp://hdl.handle.net/21.11130/00-1735-0000-0003-C16D-9
dc.identifier.urihttp://dx.doi.org/10.53846/goediss-7572
dc.language.isoengde
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject.ddc510de
dc.titleSparse Fast Trigonometric Transformsde
dc.typedoctoralThesisde
dc.contributor.refereePlonka-Hoch, Gerlind Prof. Dr.
dc.date.examination2019-06-13
dc.description.abstractengTrigonometric 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.de
dc.contributor.coRefereeKrahmer, Felix Prof. Dr.
dc.contributor.thirdRefereePotts, Daniel Prof. Dr.
dc.subject.engSparse Fourier transformde
dc.subject.engstructured sparsityde
dc.subject.engapproximation algorithmsde
dc.subject.engdiscrete Fourier transformde
dc.subject.engdeterministic sparse FFTde
dc.subject.engsublinear sparse FFTde
dc.subject.engdiscrete cosine transformde
dc.subject.engdeterministic sparse fast DCTde
dc.subject.engsublinear sparse DCTde
dc.identifier.urnurn:nbn:de:gbv:7-21.11130/00-1735-0000-0003-C16D-9-5
dc.affiliation.instituteFakultät für Mathematik und Informatikde
dc.subject.gokfullMathematics (PPN61756535X)de
dc.identifier.ppn1672306701


Dateien

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige