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