A STABLE AND ACCURATE BUTTERFLY SPARSE FOURIER TRANSFORM

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 bandwidt...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 2012-01, Vol.50 (3), p.1777-1800
Main Authors: KUNIS, STEFAN, MELZER, INES
Format: Article
Language:English
Subjects:
Accuracy
Applied mathematics
Approximation
Bandwidths
Dyadics
Error analysis
Fast Fourier transformations
Fourier transformations
Fourier transforms
Interpolation
Matrices
Polynomials
Signal bandwidth
Tensors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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:0036-1429
1095-7170
DOI:10.1137/110839825