Model-agnostic distribution recovery in high dimension via Fourier measurements.
X. Chen and A. De and Y. Huang and S. Nadimpalli and R. Servedio and T. Yang.
To appear in 38th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027.

Abstract:

We study the problem of reconstructing an unknown probability distribution to high accuracy, given noisy information about its low-degree Fourier coefficients. Prior results for this basic problem have typically imposed strong modeling assumptions on the distribution, often requiring that it is a linear combination of spatially separated point sources.

In this work, we analyze a very general version of the high-dimensional recovery problem, by considering completely general distributions over the $d$-dimensional torus $[0,1)^d$; we do not assume any spatial separation between point sources, or even that the distribution is a finite linear combination of point sources. The question naturally arises: what can be said about distribution recovery in such a general setting?

  • As a warm-up, we first give results for reconstructing distributions with respect to the Wasserstein distance. We establish essentially matching upper and lower bounds on the cutoff frequency $T$ and the magnitude $\kappa$ of the noise for which accurate reconstruction is possible. Roughly speaking, our results here show that for $d$-dimensional distributions, estimates of $\approx \exp(d)$ many Fourier coefficients are necessary and sufficient for accurate reconstruction under the Wasserstein distance.

  • As our main result, we define a new notion of "heavy hitter" reconstruction for distributions, which essentially amounts to achieving high-accuracy reconstruction of all "sufficiently dense" regions of the distribution. We give essentially matching upper and lower bounds on the cutoff frequency $T$ and the magnitude $\kappa$ of the noise for which accurate reconstruction is possible under this notion. Our results show that (in sharp contrast with Wasserstein reconstruction) accurate estimates of only $\approx \exp(\sqrt{d})$ many Fourier coefficients are necessary and sufficient for heavy hitter reconstruction.

    • Link to full version

    Back to main papers page