Search papers, labs, and topics across Lattice.
This paper investigates the convergence properties of graph Laplacians when applied to data on Riemannian manifolds, establishing a key estimate for the geodesic distance that relates a smooth symmetric divergence to the squared geodesic distance. The authors show that under certain conditions, the divergence can be approximated by the geodesic distance squared, leading to pointwise convergence of the graph Laplacians. This finding is significant as it provides a framework for analyzing manifold learning algorithms and their performance in high-dimensional data settings.
Graph Laplacians converge under a new framework that connects symmetric divergences to geodesic distances, revealing deeper insights into manifold learning.
When analyzing a manifold learning algorithm for data lying on a smooth, compact, connected Riemannian submanifold $(\mathcal{M}, g)$ of $\mathbb{R}^d$, a key estimate for the geodesic distance $d_g$ is that there exists $K > 0$ such that $0 \leq d_g(p, q)^2 - \|p-q\|^2 \leq K d_g(p, q)^4$ for all $p, q \in \mathcal{M}$. We observe that more generally, when $\mathcal{M}$ is equipped with a smooth symmetric divergence $D$ satisfying a non-degeneracy condition and $g$ is given by $g_p := \frac{1}{2}\mathrm{Hess}_p(D(p, \cdot))$ for all $p \in \mathcal{M}$, there exists $K > 0$ such that $\left| D(p, q) - d_g(p, q)^2 \right| \leq K d_g(p, q)^4$ for all $p, q \in \mathcal{M}$. We demonstrate that this is sufficient for the pointwise convergence of graph Laplacians constructed with $D$ and discuss examples where $D$ is given by the Sinkhorn divergence on a family of probability measures parametrized by a manifold.
