A Data-Driven Interpolation Method on Smooth Manifolds via Diffusion Processes and Voronoi Tessellations

We propose a data-driven interpolation method for approximating real-valued functions on smooth manifolds, based on the Laplace--Beltrami operator and Voronoi tessellations. Given pointwise evaluations, the method constructs a continuous extension by exploiting diffusion processes and the intrinsic geometry of the data. The approach builds on the Nadaraya--Watson kernel regression estimator, where the bandwidth is determined by Voronoi tessellations of the manifold. It is fully data-driven and requires neither a training phase nor any preprocessing prior to inference. The computational complexity of the inference step scales linearly with the number of sample points, leading to substantial gains in scalability compared to classical methods such as neural networks, radial basis function networks, and Gaussian process regression. We show that the resulting interpolant has vanishing gradient at the sample points and, with high probability as the number of samples increases, suppresses high-frequency components of the signal. Moreover, the method can be interpreted as minimizing a total variation--type energy, providing a closed-form analytical approximation to a compressed sensing problem with identity forward operator. We illustrate the performance of the method on sparse computational tomography reconstruction, where it achieves competitive reconstruction quality while significantly reducing computational time relative to standard total variation--based approaches.