EcoSta 2022: Start Registration
View Submission - EcoSta2022
A0663
Title: Clustering and dimension reduction via Fermat distances Authors:  Anna Little - Univeristy of Utah (United States) [presenting]
Abstract: Fermat distances are an optimal path metric which balances density-based and geometric information present in data. Graph Laplacians constructed with Fermat distance provide a useful tool for obtaining sparse graph cuts, dealing with elongated data structures, and automatically detecting the number of clusters. As the sample size converges to infinity, the spectrum of the discrete Fermat Graph Laplacian converges to the spectrum of a continuum Kolmogorov operator which generates a diffusion on the associated manifold. Unlike the Euclidean case where the diffusion occurs at a constant speed, the resulting diffusion is accelerated in regions of high density, allowing for the rapid exploration of elongated data structures. The purpose is to discuss some of the desirable properties of Fermat Graph Laplacians and highlight how the continuum limit provides a theoretical framework for understanding these properties. In addition, these metrics can be efficiently computed by restricting them to a sparse graph.