Nonhomogeneous Euclidean first-passage percolation and distance learning

DOI10.3150/21-BEJ1341MaRDI QIDQ2073213zbMATH OpenOpenAlexWikidataFDO

Authors Pablo Groisman, Matthieu Jonckheere, Facundo Sapienza

Publication date 1 February 2022

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.09398, https://projecteuclid.org/journals/bernoulli/volume-28/issue-1/Nonhomogeneous-Euclidean-first-passage-percolation-and-distance-learning/10.3150/21-BEJ1341.full

zbMATH Keywords

distance learningEuclidean first-passage percolationnonhomogeneous point processes

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Searching and sorting (68P10) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: Consider an i.i.d. sample from an unknown density function supported on an unknown manifold embedded in a high dimensional Euclidean space. We tackle the problem of learning a distance between points, able to capture both the geometry of the manifold and the underlying density. We prove the convergence of this microscopic distance, as the sample size goes to infinity, to a macroscopic one that we call Fermat distance as it minimizes a path functional, resembling Fermat principle in optics. The proof boils down to the study of geodesics in Euclidean first-passage percolation for nonhomogeneous Poisson point processes.

Recommendations

• Convergence rates for estimators of geodesic distances and Fréchet expectations
• Modeling of distance functions on a manifold
• The topology of probability distributions on manifolds
• Euclidean models of first-passage percolation
• Ricci curvature and the manifold learning problem

Cites work

• Approximating geodesics via random points
• Arcs and Geodesics in Metric Spaces
• Determining Intrinsic Dimension and Entropy of High-Dimensional Shape Spaces
• Euclidean models of first-passage percolation
• Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold Learning
• Geodesics and spanning trees for Euclidean first-passage percolation.
• scientific article; zbMATH DE number 2080487 (Why is no real title available?)
• scientific article; zbMATH DE number 1912119 (Why is no real title available?)
• Limit theory for point processes in manifolds
• Shortest path through random points

Cited in

(3)

• Balancing geometry and density: path distances on high-dimensional data
• Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
• Supervised dimension reduction via local gradient elongation

This page was built for publication: Nonhomogeneous Euclidean first-passage percolation and distance learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073213)