A stable and accurate butterfly sparse Fourier transform
type: Item
instance of: scholarly article
zbMATH Open document ID: 1255.65252
DOI: 10.1137/110839825
author: Stefan Kunis
author: Ines Melzer
published in: SIAM Journal on Numerical Analysis
publication date: 2012-08-23T00:00:00Z
Mathematics Subject Classification ID: 65T40
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 42A15
zbMATH DE Number: 6070640
zbMATH Keywords: trigonometric approximation
zbMATH Keywords: nonharmonic Fourier series
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: trigonometric interpolation
zbMATH Keywords: butterfly approximation scheme
zbMATH Keywords: error analysis
describes a project that uses: NFFT
describes a project that uses: NFFT3
MaRDI profile type: Publication
OpenAlex ID: W1986681927
title: A stable and accurate butterfly sparse Fourier transform
review text: The following problem is discussed:NEWLINENEWLINE Given a space dimension \(d\in \mathbb N\), a nonharmonic bandwidth \(N=2^L\), \(L\in \mathbb N\), a set of frequencies \(\tilde T=\{\xi_k\in [0,N]^d:\;k=1,\dots,M_2\}\), a set of Fourier coefficients \(\hat U_k\in C\), \(k=1,\dots,M_2\), and a set of evaluation nodes \(\tilde x=\{{\mathbf x}_j\in [0,N]^d:\;j=1,2,\dots,M_1\}\), we want to compute the sums NEWLINE\[NEWLINE U_j:=U({\mathbf x}_j)=\sum_{k=1}^{M_2}\hat U_ke^{2\pi i{\mathbf \xi}_k{\mathbf x}_j/N},~j=1,\dots,M_1. NEWLINE\]NEWLINE To solve this problem, the authors use the trigonometric interpolation operator NEWLINE\[NEWLINE ({\mathcal L}_pg)({\mathbf x})=\sum_{s=0}^{p-1}\hat g_se^{2\pi i{\mathbf \xi}_s{\mathbf x}/N} NEWLINE\]NEWLINE and the butterfly approximation scheme. The authors present a rigorous error analysis which shows how the local expansion degree depends on the target accuracy and the nonharmonic bandwidth.
reviewed by: S. F. Lukomskii
description: scientific article; zbMATH DE number 6070640