A stable and accurate butterfly sparse Fourier transform (Q2903060)

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.