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.
Jonathan W. Siegel (Tue,) studied this question.