A STABLE AND ACCURATE BUTTERFLY SPARSE FOURIER TRANSFORM

Autor(en): Kunis, Stefan 
Melzer, Ines
Stichwörter: ALGORITHM; fast Fourier transform; Mathematics; Mathematics, Applied; nonharmonic Fourier series; trigonometric approximation
Erscheinungsdatum: 2012
Herausgeber: SIAM PUBLICATIONS
Journal: SIAM JOURNAL ON NUMERICAL ANALYSIS
Volumen: 50
Ausgabe: 3
Startseite: 1777
Seitenende: 1800
Zusammenfassung: 
Recently, the butterfly approximation scheme was proposed for computing Fourier transforms with sparse and smooth sampling in the frequency and spatial domains. We present a rigorous error analysis which shows how the local expansion degree depends on the target accuracy and the nonharmonic bandwidth. Moreover, we show that the original scheme becomes numerically unstable if a large local expansion degree is used. This problem is removed by representing all approximations in a Lagrange-type basis instead of the previously used monomial basis. All theoretical results are illustrated by numerical experiments.
ISSN: 00361429
DOI: 10.1137/110839825

Show full item record

Page view(s)

3
Last Week
0
Last month
1
checked on Feb 28, 2024

Google ScholarTM

Check

Altmetric