Model-agnostic super-resolution in high dimensions

Xi Chen Anindya De Yizhi Huang Columbia University University of Pennsylvania Columbia University [email protected] [email protected] [email protected] Shivam Nadimpalli Rocco A. Servedio Tianqi Yang MIT Columbia University Columbia University [email protected] [email protected] tian · 2025

Read Model-agnostic super-resolution in high dimensions by Xi Chen Anindya De Yizhi Huang Columbia University University of Pennsylvania Columbia University [email protected] [email protected] [email protected] Shivam Nadimpalli Rocco A. Servedio Tianqi Yang MIT Columbia University Columbia University [email protected] [email protected] tian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07846.txt.

Introduction

Xi Chen, Anindya De, and Yizhi Huang recover whole distributions from blurry Fourier clues. Given noisy low-degree Fourier coefficients of an unknown distribution on a high-dimensional torus, can the distribution itself be rebuilt accurately? Earlier answers assumed tidy structure, like separated point sources.

Completely general distributions get an analysis here, with no separation or finite-source assumptions. The recovery question is basic to signal processing, learning theory, and inverse problems. Guarantees without structural crutches mean the method applies where nature has not promised tidiness. Fourier measurements are cheap to collect in many sensors, so broad recovery results multiply their value.

Catalog record

CREATORXi Chen Anindya De Yizhi Huang Columbia University University of Pennsylvania Columbia University [email protected] [email protected] [email protected] Shivam Nadimpalli Rocco A. Servedio Tianqi Yang MIT Columbia University Columbia University [email protected] [email protected] tian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07846

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Model-agnostic super-resolution in high dimensions Xi Chen Anindya De Yizhi Huang Columbia University University of Pennsylvania Columbia University [email protected] [email protected] [email protected] Shivam Nadimpalli Rocco A. Servedio Tianqi Yang MIT Columbia University Columbia University [email protected] [email protected] [email protected] 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 signals over the d d -dimensional torus [ 0 , 1 ) d [0,1)^{d} ; we do not assume any spatial separation between point sources, or even that the signal is a finite linear combination of point sources. The question naturally arises: what can be said about super-resolution in such a general setting? We give two sets of results for two different natural notions of signal reconstruction: 1. Reconstruction in Wasserstein distance: Our first set of results is for reconstructing signals with respect to the Wasserstein distance. We give essentially matching upper and lower bounds on the cutoff frequency T T and the magnitude κ \kappa of the noise for which accurate reconstruction in Wasserstein distance is possible. Roughly speaking, our results here show that for d d -dimensional signals, estimates of ≈ exp ⁡ ( d ) \approx\exp(d) many Fourier coefficients are necessary and sufficient for accurate reconstruction under the Wasserstein distance. 2. “Heavy hitter” reconstruction: We go on to define a new notion of “heavy hitter” reconstruction for non-negative signals (which, after normalization, correspond to probability distributions); this notion essentially amounts to achieving high-accuracy reconstruction of all “sufficiently dense” regions of the distribution. For this notion too, we give essentially matching upper and lower bounds on the cutoff frequency T T and the magnitude κ \kappa of the noise for which accurate reconstruction is possible. Our results show that—in sharp contrast with Wasserstein reconstruction—accurate estimates of only ≈ exp ⁡ ( d ) \approx\exp(\sqrt{d}) many Fourier coefficients are necessary and sufficient for heavy hitter reconstruction. 1 Introduction This paper considers the fundamental signal processing problem of super-resolution —recovering fine-scale structure from coarse, noisy measurements—from the perspective of theoretical computer science. A convenient starting point to motivate the problem is the diffraction limit from optical physics: when illuminated by light waves of wavelength \lambda , an optical system cannot resolve features separated by distances much smaller than \lambda . This idea, dating back to the 1870s [ 1 , 36 , 42 ] , has recently been formalized and studied through the lens of theoretical computer science by Chen and Moitra [ 5 ] , who established statistical and computational limits on diffraction-limited imaging. Since frequency and wavelength are inversely related, this line of work can be summarized as the following high-level idea: Resolving increasingly fine details from noisy measurements requires access to correspondingly higher frequencies: shorter wavelengths enable finer resolution. However, in many settings, systems can only be observed at low frequencies, raising the fundamental question of super-resolution : Can we recover a signal even from bandlimited measurements? Put differently, if our measurements are limited to frequencies below a certain cutoff, to what extent can we still reconstruct the underlying signal? The modern mathematical study of super-resolution originates in the seminal work of Donoho [ 10 ] . Although our focus will be on high-dimensional signals, it is instructive to begin with the one-dimensional setting introduced by Candès and Fernandez–Granda [ 3 ] . Here, the domain is the one-dimensional torus \mathbb{T} , which we identify with the interval [0,1) . A signal is modeled as f(x)\mathrel{\mathop{\mathchar 58\relax}}=\sum_{j=1}^{k}u_{j}\delta_{t_{j}}(x)\,, (1) where \delta_{t_{j}}(x) , where \delta_{t_{j}}(\cdot) is a Dirac delta centered at the point t_{j}\in\mathbb{T} and u_{j}\in\mathbb{R} is the corresponding amplitude. In other words, the signal f is a superposition of k point sources where the j^{\text{th}} point source has location t_{j} and amplitude u_{j} . We will sometimes refer to a Dirac delta \delta_{t} as a spike located at t . Next, recall that the Fourier spectrum over the torus \mathbb{T} is indexed by the integers \mathbb{Z} . In particular, for a signal f , the Fourier coefficient at frequency \ell\in\mathbb{Z} is given by \widehat{f}(\ell)=\int_{x\in\mathbb{T}}f(x)\cdot\exp\big(2\pi i\ell x\big)\,dx\,. By definition of the Dirac delta \delta_{t} , for any test function g we have \int_{x}g(x)\delta_{t}(x)=g(t) . In particular, applying this to a signal of the form ( 1 ), we obtain \widehat{f}(\ell)=\sum_{j=1}^{k}u_{j}\exp(2\pi i\ell t_{j})\,. The main question posed by Candès and Fernandez–Granda in [ 4 ] was whether bandlimited measurements suffice to recover an unknown signal f , under the promise that f is a superposition of k point sources (i.e., f is as in Equation 1 ). They proposed a convex optimization framework for this inverse problem and showed, among other things, that if \widehat{f}(\ell) is known exactly for all \ell\leq k (in other words, the signal is observed up to bandlimit k ), then their convex program perfectly reconstructs f . It is worth noting that the ability to recover a k -sparse signal f from the exact Fourier coefficients \{\widehat{f}(\ell)\}_{|\ell|\leq k} is not new: Prony’s method, dating back to 1795 [ 7 ] , achieves the same guarantee. The novelty of [ 4 ] lies in showing that such recovery can be accomplished through a convex optimization program. That said, the assumption of having perfect access to the exact Fourier data is quite restrictive; in practice, the measurements \widehat{f}(\ell) are inevitably perturbed by noise. This raises the natural question of whether recovery is possible given noisy measurements. Noisy measurements. Suppose the algorithm no longer has access to the true Fourier coefficients but instead receives \{\widetilde{f}(\ell)\}_{|\ell|\leq T} satisfying |\widetilde{f}(\ell)-\widehat{f}(\ell)|\leq\kappa\,. In other words, the observed coefficients are perturbed by additive noise of magnitude at most \kappa . This modification substantially changes the nature of the problem. Indeed, it is easy to see that given \{\widetilde{f}(\ell)\}_{|\ell|\leq T} , one cannot distinguish between f_{1}(x)=\delta_{0}(x)\qquad\text{versus}\qquad f(x)=\frac{1}{2}\cdot\delta_{0}(x)+\frac{1}{2}\cdot\delta_{\Delta}(x) (2) for \Delta\ll\min\{\kappa,T^{-1}\} . In other words, even deciding whether f consists of one spike or two becomes impossible without imposing an additional separation condition between the spikes. Thus, to recover a signal f from noisy estimates of \widehat{f}(\ell) , it appears necessary to impose a separation assumption on the support points of f (spoiler alert: this is precisely the assumption we reexamine in this paper). To formalize what “separation” means on the torus, we first recall the natural distance metric between two points a,b\in\mathbb{T} : the toroidal distance \mathrm{d}_{\mathrm{tor}}(a,b) , which is the shortest distance between a and b when identifying the interval [0,1) with the unit circle (so that 0 and 1 coincide; see Section 2.2 for the formal definition.) With this definition in hand, Candès and Fernandez–Granda [ 3 ] studied the setting where any two supports points t_{i},t_{j} of f satisfy \mathrm{d}_{\mathrm{tor}}(t_{i},t_{j})\geq\Delta . They proved that f can be approximately recovered even in the presence of noise, provided that the support points t_{1},\dots,t_{k} lie on a grid and the bandlimit T is at least 2/\Delta . (We note that the error metric in [ 3 ] is based on

Read the complete text