Zur Kurzanzeige

Deterministic Sparse FFT Algorithms

dc.contributor.advisorPlonka-Hoch, Gerlind Prof. Dr.
dc.contributor.authorWannenwetsch, Katrin Ulrike
dc.date.accessioned2016-09-30T08:21:24Z
dc.date.available2016-09-30T08:21:24Z
dc.date.issued2016-09-30
dc.identifier.urihttp://hdl.handle.net/11858/00-1735-0000-002B-7C10-0
dc.identifier.urihttp://dx.doi.org/10.53846/goediss-5874
dc.language.isoengde
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject.ddc510de
dc.titleDeterministic Sparse FFT Algorithmsde
dc.typedoctoralThesisde
dc.contributor.refereePlonka-Hoch, Gerlind Prof. Dr.
dc.date.examination2016-08-09
dc.description.abstractengThe discrete Fourier transform (DFT) is a well-known transform with many applications in various fields. By fast Fourier transform (FFT) algorithms, the DFT of a vector can be efficiently computed. Using these algorithms, one can reconstruct a complex vector x of length N from its discrete Fourier transform applying O(N log N) arithmetical operations. In order to improve the complexity of FFT algorithms, one needs additional a priori assumptions on the vector x. In this thesis, the focus is on vectors with small support or sparse vectors for which several new deterministic algorithms are proposed that have a lower complexity than regular FFT algorithms. We develop sublinear time algorithms for the reconstruction of complex vectors or matrices with small support from Fourier data as well as an algorithm for the reconstruction of real nonnegative vectors. The algorithms are analyzed and evaluated in numerical experiments. Furthermore, we generalize the algorithm for real nonnegative vectors with small support and propose an approach to the reconstruction of sparse vectors with real nonnegative entries.de
dc.contributor.coRefereePotts, Daniel Prof. Dr.
dc.subject.engDiscrete Fourier Transformde
dc.subject.engFast Fourier Transformde
dc.subject.engsparse Fourier reconstructionde
dc.subject.engsparse FFTde
dc.subject.engvector reconstructionde
dc.subject.engsmall supportde
dc.identifier.urnurn:nbn:de:gbv:7-11858/00-1735-0000-002B-7C10-0-2
dc.affiliation.instituteFakultät für Mathematik und Informatikde
dc.subject.gokfullMathematics (PPN61756535X)de
dc.identifier.ppn869470280


Dateien

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige