Oblivious near-optimal sampling for multidimensional signals with Fourier constraints

We study the problem of reconstructing a continuous multidimensional signal from a small number of samples under Fourier constraints assuming that the Fourier power spectrum of the signal has some desirable properties, e.g. being compactly supported, being sparse. We further assume that the Fourier constraint can be expressed as a prior distribution on the Fourier power spectrum, which subsumes the aforementioned examples. The study of sampling and reconstructing in this vein has attracted much attention with a long history.In this paper, we are interested in finding oblivious sampling strategies, that is, sampling without knowing what specific constraint is put on the Fourier power spectrum. We show that it is possible to obliviously sample a Fourier-constrained multidimensional signal with a near-optimal (up to a logarithmic factor) number of samples that guarantee successful reconstruction, partially answering an open question in Avron et al. (2019) which considered the $1$-dimensional case. Our approach highlights a phenomenon that is unique for dimension $d\ge 2$ that the sampling strategy should depend on the geometry of the region on which the signal is to be reconstructed, unlike the case $d=1$ where all regions are of the form $[a,b]$ which are all geometrically equivalent. Our proof, using tools from convex geometry, also illuminates an idea obscured in $d=1$, that to reconstruct a signal in a given region, it can be helpful to take some samples outside that region.