{"ID":2843149,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07846","arxiv_id":"2511.07846","title":"Model-agnostic super-resolution in high dimensions","abstract":"The problem of super-resolution, roughly speaking, is to reconstruct an unknown signal to high accuracy, given (potentially noisy) information about its low-degree Fourier coefficients. Prior results on super-resolution have imposed strong modeling assumptions on the signal, typically requiring that it is a linear combination of spatially separated point sources. In this work we analyze a very general version of the super-resolution problem by considering completely general non-negative signals (equivalently, 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 super-resolution in such a general setting? - As a warm-up, we first give a set of results for reconstructing distributions under the Wasserstein distance. We establish essentially matching upper and lower bounds on the cutoff frequency $T$ and the magnitude $κ$ of the noise for which accurate reconstruction is possible: we show that for $d$-dimensional distributions, estimates of $\\approx \\exp(d)$ many Fourier coefficients are both necessary and sufficient for accurate Wasserstein reconstruction. - 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 $κ$ 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 both necessary and sufficient for heavy hitter reconstruction.","short_abstract":"The problem of super-resolution, roughly speaking, is to reconstruct an unknown signal to high accuracy, given (potentially noisy) information about its low-degree Fourier coefficients. Prior results on super-resolution have imposed strong modeling assumptions on the signal, typically requiring that it is a linear comb...","url_abs":"https://arxiv.org/abs/2511.07846","url_pdf":"https://arxiv.org/pdf/2511.07846v2","authors":"[\"Xi Chen\",\"Anindya De\",\"Yizhi Huang\",\"Shivam Nadimpalli\",\"Rocco A. Servedio\",\"Tianqi Yang\"]","published":"2025-11-11T05:28:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"math.ST\"]","methods":"[]","has_code":false}