Nearly optimal bounds on the Fourier sampling numbers of Besov spaces

Let Tᵈ denote the d-dimensional torus. We consider the problem of optimally recovering a target function f^*:Tᵈ→ C from samples of its Fourier coefficients. We make classical smoothness assumptions on f^*, specifically that f^* lies in a Besov space Bˢ_∞(Lq) with $s > 0$ and 1≤ q≤ ∞, and measure recovery error in the Lₚ-norm with 1≤ p≤ ∞. 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₀ < p≤ 2 with p₀ ≈ 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.