Codes and Expansions (CodEx) Seminar

Liane Xu (Princeton)
Manifold learning with symmetric divergences

Laplacian-based methods are popular for the dimensionality reduction of data lying in a high-dimensional Euclidean space. Several theoretical results for these algorithms depend on the fact that the Euclidean distance locally approximates the geodesic distance on the underlying submanifold which the data are assumed to lie on. However, for some applications, another divergence or metric may provide a more appropriate notion of dissimilarity than the Euclidean distance. We observe that a smooth, symmetric divergence D satisfying a non-degeneracy condition satisfies a similar approximation error with respect to the geodesic distance of an appropriately defined Riemannian metric. This is sufficient, for example, to deduce the pointwise convergence of graph Laplacians constructed with D. We discuss examples where D is given by the square of the L1 norm and the Sinkhorn divergence. This talk includes joint work with Amit Singer.