Manifold learning with bi-stochastic kernels

The evolution of manifold learning has seen the development of spectral methods like Diffusion Maps, which utilize kernels to capture geometric structures. Early approaches employed row-stochastic normalization, but these methods struggled with non-uniform sampling, leading to distortions in the inferred geometry. Recent advances introduced Sinkhorn normalization to produce bi-stochastic kernels, which better preserve geometric features. However, the precise relationship between these normalized kernels and the underlying heat kernel, as well as their infinitesimal generators, remained underexplored. This gap limited the theoretical understanding and practical robustness of diffusion-based algorithms, especially in complex data scenarios. The current work builds on this foundation, aiming to rigorously analyze the asymptotic behavior of bi-stochastic kernels and their connection to classical differential operators on manifolds.

The core problem is to determine how bi-stochastic normalization of kernels influences the diffusion process on a manifold, particularly in the presence of non-uniform sampling. Existing methods do not fully account for the sampling density and measure normalization, which can distort the geometric interpretation of the diffusion operator. The challenge lies in deriving the limiting infinitesimal generator of the normalized kernel, understanding its dependence on the sampling distribution and the specified measure, and establishing its relation to the heat kernel. Addressing this problem is crucial for developing stable, geometry-preserving algorithms capable of handling real-world data with inherent sampling biases and noise.

The paper introduces several key innovations: 1) It formalizes the construction of bi-stochastic kernels via iterative normalization, avoiding reliance on Sinkhorn iterations in favor of analytical derivations. 2) It rigorously derives the asymptotic form of the associated diffusion generator, revealing its dependence on the sampling density and the chosen measure. 3) It establishes a direct connection between the normalized kernels and the heat kernel, providing a geometric interpretation rooted in differential geometry. 4) It develops Nyström extension formulas for eigenfunctions and their gradients, enabling practical computation in high-dimensional settings. These innovations collectively deepen the theoretical understanding and practical applicability of diffusion processes in manifold learning.

• �� Define the kernel function: \(k_\epsilon(x, y) = h( |x - y|^2 / \epsilon )\), with \(h\) smooth and exponentially decaying.
• �� Normalize via iterative Sinkhorn algorithm: alternately normalize rows and columns to achieve bi-stochasticity with respect to the measure \(d\hat{\mu}(x) = d\mu(x)/w(x)\).
• �� Derive the asymptotic behavior: analyze the limit as \(\epsilon o 0\), employing spectral theory and differential geometry to connect the normalized kernel to the Laplace-Beltrami operator.
• �� Spectral decomposition: compute eigenvalues and eigenfunctions of the constructed operators, ensuring self-adjointness and compactness.
• �� Nyström extension: formulate explicit formulas for the gradients of eigenfunctions, facilitating their estimation in discrete data.
• �� Numerical validation: perform experiments on synthetic manifolds and real datasets to verify the theoretical predictions and compare with existing methods.

Experiments involve synthetic datasets like spheres and tori, and real datasets such as MNIST. The kernel parameters are chosen based on median distances, with \(\epsilon\) tuned to balance bias and variance. The methods compare bi-stochastic normalization against row normalization, measuring spectral convergence, eigenfunction accuracy, and gradient estimation errors. Error metrics include spectral gap preservation, \(L^2\) norm differences, and visualization of gradient fields. The experiments demonstrate that bi-stochastic kernels better approximate the heat kernel, especially under non-uniform sampling, with errors below 1%. Additional tests assess robustness to noise and sampling irregularities, confirming the theoretical advantages.

The analysis confirms that the bi-stochastic kernel's infinitesimal generator converges to the Laplace-Beltrami operator modified by the sampling density, approximating the heat kernel with high fidelity. Numerical results show spectral gaps and eigenfunctions converge rapidly as \(\epsilon o 0\). Gradient estimates via Nyström formulas closely match analytical derivatives, validating the theoretical derivations. In real data, the approach improves feature stability and geometric fidelity, outperforming traditional row-normalized kernels in non-uniform sampling scenarios. These findings demonstrate the method’s practical effectiveness and theoretical soundness.

The methodology applies to high-dimensional data analysis, including nonlinear dimensionality reduction, geometric feature extraction, and graph-based learning. It is particularly suited for datasets with sampling biases, noise, or complex geometries. The spectral and gradient estimation tools facilitate robust data representations, enabling improved clustering, visualization, and downstream learning tasks. Future integration with deep neural networks could further enhance scalability and adaptability, broadening the scope of manifold-based data analysis in industry and academia.

The approach assumes smooth, compact manifolds without boundary, limiting applicability to real-world data with noise, irregularities, or non-smooth structures. Computational costs for spectral decomposition and Sinkhorn iterations scale poorly with data size, posing challenges for large datasets. The theoretical guarantees rely on asymptotic limits, which may not hold exactly in finite samples. Extending the framework to non-compact or boundary-including manifolds, and to noisy or high-dimensional data, remains an open challenge.