Improved approximation guarantees for sublinear-time Fourier algorithms (Q1762319)

This paper develops fast methods for finding near-optimal nonlinear approximations to the Fourier transform of a given continuous and periodic function \(f:\;[0,2\pi]^D\to\mathbb C\). Suppose that \(f\) is a band limited so that its Fourier transform, \(\hat f:\;\mathbb Z^D\to \mathbb C\), is zero for all \(\omega\notin [-N/2,N/2]^D\), where \(N^D\) is large. An optimal \(k\)-term trigonometric approximation to \(f\) is given by \[ f_k^{\text{opt}}({\mathbf x})=\sum_{j=1}^k\hat f (\omega_j)e^{i\omega_j{\mathbf x}}, \] where \(\omega_1,\dots,\omega_{N^D}\in (-N/2,N/2]^D\bigcap\mathbb Z^D\) are ordered by the magnitudes of their coefficients so that \[ |\hat f(\omega_1)|\geq|\hat f(\omega_2)|\geq\dots\geq |\hat f(\omega_{N^D})|. \] The optimal \(k\)-term approximation error is then \(\|f-f_k^{\text{opt}}\|_2=\|\hat f-\hat f_k^{\text{opt}}\|_2\). Suppose \(k\in\mathbb N\) is given. The goal of this paper is to develop fast Fourier approximation schemes that are guaranteed to always return a near-optimal trigonometric polynomial, \(y_k:\;[0,2\pi]^D\to\mathbb C\), having \(\|f-y_k\|_2\approx\|\hat f-\hat f_k^{\text{opt}}\|_2\).