Fast Fourier Transform at Nonequispaced Nodes and Applications


Fenn, Markus


[img]
Preview
PDF
Fenn.pdf - Published

Download (2MB)

URL: http://ub-madoc.bib.uni-mannheim.de/1157
URN: urn:nbn:de:bsz:180-madoc-11577
Document Type: Doctoral dissertation
Year of publication: 2005
Publishing house: Universität Mannheim
Evaluator: Steidl, Gabriele
Date of oral examination: 8 December 2005
Publication language: English
Institution: School of Business Informatics and Mathematics > Angewandte Mathematik u. Informatik (Steidl -2011)
Subject: 004 Computer science, internet
Classification: MSC: 65T50 42A10 42B05 65F50 ,
Subject headings (SWD): Schnelle Fourier-Transformation
Individual keywords (German): unstrukturierte Knotenmengen , schnelle trigonometrische Transformationen , schnelle Matrix-Vektor Multiplikation , Ridgelets
Keywords (English): nonequispaced nodes , fast trigonometric transforms , fast matrix-vector multiplication , ridgelets
Abstract: The direct computation of the discrete Fourier transform at arbitrary nodes requires O(NM) arithmetical operations, too much for practical purposes. For equally spaced nodes the computation can be done by the well known fast Fourier transform (FFT) in only O(N log N) arithmetical operations. Recently, the fast Fourier transform for nonequispaced nodes (NFFT) was developed for the fast approximative computation of the above sums in only O(N log N + M log 1/e), where e denotes the required accuracy. The principal topics of this thesis are generalizations and applications of the NFFT. This includes the following subjects: - Algorithms for the fast approximative computation of the discrete cosine and sine transform at nonequispaced nodes are developed by applying fast trigonometric transforms instead of FFTs. - An algorithm for the fast Fourier transform on hyperbolic cross points with nonequispaced spatial nodes in 2 and 3 dimensions based on the NFFT and an appropriate partitioning of the hyperbolic cross is proposed. - A unified linear algebraic approach to recent methods for the fast computation of matrix-vector-products with special dense matrices, namely the fast multipole method, fast mosaic-skeleton approximation and H-matrix arithmetic, is given. Moreover, the NFFT-based summation algorithm by Potts and Steidl is further developed and simplified by using algebraic polynomials instead of trigonometric polynomials and the error estimates are improved. - A new algorithm for the characterization of engineering surface topographies with line singularities is proposed. It is based on hard thresholding complex ridgelet coefficients combined with total variation minimization. The discrete ridgelet transform is designed by first using a discrete Radon transform based on the NFFT and then applying a dual-tree complex wavelet transform. - A new robust local scattered data approximation method is introduced. It is an advancement of the moving least squares approximation (MLS) and generalizes an approach of van den Boomgard and van de Weijer to scattered data. In particular, the new method is space and data adaptive.
Translation of the title: Schnelle Fouriertransformation auf unstrukturierten Knotenmengen und Anwendungen (German)
Translation of the abstract: Die direkte Berechnung der diskreten Fourier-Transformation an beliebigen Knoten erfordert O(NM) arithmetische Operationen. Für äquidistante Knoten kann die Berechnung mittels schneller Fouriertransformation (FFT) in nur O(N log N) arithmetischen Operationen durchgeführt werden. Auf unstrukturierten Knotenmengen hat sich inzwischen ein Algorithmus (NFFT) zur effizienten näherungsweisen Berechnung der diskreten Fourier-Transformation in nur O( N log N + M log 1/e ) etabliert, wobei e die gewünschte Genauigkeit bezeichnet. Das Hauptaugenmerk dieser Dissertation liegt auf Verallgemeinerungen und Anwendungen der NFFT. Im Einzelnen beinhaltet dies die folgenden Ergebnisse: - Es werden schnelle Algorithmen für die näherungsweise Berechnung der diskreten Kosinus- und Sinustransformation auf unstrukturierten Knotenmengen entwickelt, die statt der FFT schnelle trigonometrische Transformationen verwenden. - Ein Algorithmus für die schnelle Fouriertransformation auf hyperbolischen Kreuzen in 2 und 3 Dimensionen mit unstrukturierten Knotenmengen im Zeitbereich wird aufbauend auf der NFFT und einer geeigneten Unterteilung der hyperbolischen Kreuze konstruiert. - Ein einheitlicher algebraischer Zugang zu aktuellen Methoden für die schnelle Berechnung von Matrix-Vektor-Produkten mit speziellen vollbesetzten Matrizen, und zwar die "fast multipole method" (FMM), die "fast mosaic-skeleton"-Approximation und die H-Matrix-Arithmetik, wird gegeben. Desweiteren wird der NFFT-basierte Summationsalgorithmus von Potts und Steidl durch die Verwendung algebraischer an Stelle von trigonometrischen Polynomen vereinfacht, und die Fehlerabschätzungen werden verbessert. - Ein neuer Algorithmus zur Beschreibung der Beschaffenheit technischer Oberflächen mit Liniensingularitäten wird vorgestellt. Er basiert auf einer Kopplung von "hard thresholding" von Ridgeletkoeffizienten mit Verfahren zur Minimierung der totalen Variation. Die diskrete Ridgelettransformation erhält man durch Verwendung einer auf der NFFT basierenden diskreten Radontransformation und anschließender Anwendung einer speziellen komplexen Wavelettransformation, der "dual-tree complex wavelet transform". - Eine neue robuste lokale Approximationsmethode für gestreute Daten wird eingeführt. Sie stellt eine Weiterentwicklung der sogenannten "moving least squares" Approximation (MLS) dar und verallgemeinert einen Ansatz von van den Boomgaard und van de Weijer auf nichtäquidistante Knoten. Insbesondere ist der neue Zugang raum- und datenadaptiv. (German)
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Fenn, Markus (2005) Fast Fourier Transform at Nonequispaced Nodes and Applications. Open Access [Doctoral dissertation]
[img]
Preview


+ Search Authors in

BASE: Fenn, Markus

Google Scholar: Fenn, Markus

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item