Fourier computation of empirical diffusion metrics

Abstract

We give a finite Fourier algorithm for computing empirical diffusion-metric entries together with their joint uncertainty estimates. The metric is defined through an inverse weighted Laplacian and estimated by empirical heat-kernel Sinkhorn normalization. For a fixed smooth, strictly positive density on a fixed-dimensional flat torus and fixed smooth test functions, the algorithm preserves the exact estimator's population-centered Gaussian limit, joint covariance consistency and ordinary nonparametric bootstrap. For every fixed eta > 0, its deterministic work is O(n^(1+eta)) in the exact-real model, using sufficiently high fixed-order bias extrapolation. The proof controls the closing spectral gap as bandwidth decreases, the actual normalization iterations, and the errors in both the inverse metric and its influence covariance under the original empirical weights. Positive Fourier features and reduced linear solves provide the algorithm. The work bound includes feature-Gram construction and factorization; explicit finite schedules illustrate the resulting resource counts.