Balancing geometry and density: path distances on high-dimensional data

DOI10.1137/20M1386657zbMATH Open1493.62391arXiv2012.09385OpenAlexW4226462355MaRDI QIDQ5037564FDOQ5037564

Authors: Anna V. Little, Daniel McKenzie, James M. Murphy 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: New geometric and computational analyses of power-weighted shortest-path distances (PWSPDs) are presented. By illuminating the way these metrics balance density and geometry in the underlying data, we clarify their key parameters and discuss how they may be chosen in practice. Comparisons are made with related data-driven metrics, which illustrate the broader role of density in kernel-based unsupervised and semi-supervised machine learning. Computationally, we relate PWSPDs on complete weighted graphs to their analogues on weighted nearest neighbor graphs, providing high probability guarantees on their equivalence that are near-optimal. Connections with percolation theory are developed to establish estimates on the bias and variance of PWSPDs in the finite sample setting. The theoretical results are bolstered by illustrative experiments, demonstrating the versatility of PWSPDs for a wide range of data settings. Throughout the paper, our results require only that the underlying data is sampled from a low-dimensional manifold, and depend crucially on the intrinsic dimension of this manifold, rather than its ambient dimension.

Full work available at URL: https://arxiv.org/abs/2012.09385

Recommendations

• Diffusion state distances: multitemporal analysis, fast algorithms, and applications to biological networks
• Empirical geodesic graphs and CAT\((k)\) metrics for data analysis
• Intrinsic dimension of geometric data sets
• Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (extended abstract)
• Bounds on the mean power-weighted nearest neighbour distance

zbMATH Keywords

clusteringmachine learninghigh-dimensional statisticskernel methodsmanifold learningpath distances

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational aspects of data analysis and big data (68T09)

Cites Work

• Visualizing data using t-SNE
• Finding the homology of submanifolds with high confidence from random samples
• Diffusion maps
• Curvature Measures
• The reach, metric distortion, geodesic convexity and the variation of tangent spaces
• Title not available (Why is that?)
• A distribution-free theory of nonparametric regression
• A Nonparametric Estimate of a Multivariate Density Function
• Generalized density clustering
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Geodesics and spanning trees for Euclidean first-passage percolation.
• Connecting dots: from local covariance to empirical intrinsic geometry and locally linear embedding
• The geometry of kernelized spectral clustering
• Local kernels and the geometric structure of data
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• Variable bandwidth diffusion kernels
• On energy, discrepancy and group invariant measures on measurable subsets of Euclidean space
• Shortest path through random points
• Title not available (Why is that?)
• Density-sensitive semisupervised inference
• A note on some rates of convergence in first-passage percolation
• The strong uniform consistency of nearest neighbor density estimates
• Euclidean models of first-passage percolation
• Robust path-based spectral clustering
• 50 Years of First-Passage Percolation
• Entropy reduction in Euclidean first-passage percolation
• Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions
• Fractional diffusion maps
• Estimating the reach of a manifold
• Manifold learning with arbitrary norms
• Local regularization of noisy point clouds: improved global geometric estimates and data analysis
• Nonhomogeneous Euclidean first-passage percolation and distance learning
• Title not available (Why is that?)
• Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph

Cited In (5)

• People mover's distance: class level geometry using fast pairwise data adaptive transportation costs
• Comments on: ``Distance geometry and data science
• Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• Geometric scattering on measure spaces

Uses Software

• t-SNE

This page was built for publication: Balancing geometry and density: path distances on high-dimensional data

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