Nearly optimal bounds on the Fourier sampling numbers of Besov spaces

Abstract

Let ${\mathbb{T}}^d$ denote the $d$-dimensional torus. We consider the problem of optimally recovering a target function $f^{\ast }:{\mathbb{T}}^d\to \mathbb{C}$ from samples of its Fourier coefficients. We make classical smoothness assumptions on $f^{\ast }$, specifically that $f^{\ast }$ lies in a Besov space $B_{\infty }^s(L_q)$ with $s>0$ and $1\le q\le \infty$, and measure recovery error in the $L_p$-norm with $1\le p\le \infty$. Abstractly, the optimal recovery error is characterized by a `restricted' version of the Gelfand widths, which we call the Fourier sampling numbers. Up to logarithmic factors, we determine the correct asymptotics of the Fourier sampling numbers in the regime $s/d>1-1/p$. We also give a description of nearly optimal Fourier measurements and recovery algorithms in each of these cases. In the other direction, we prove a novel lower bound showing that there is an asymptotic gap between the Fourier sampling numbers and the Gelfand widths when $q=1$ and $p_0<p\le 2$ with $p_0\approx 1.535$. Finally, we discuss the practical implications of our results, which imply a sharper recovery of edges, and provide numerical results demonstrating this phenomenon.