k-variance: a clustered notion of variance

DOI10.1137/20M1385895zbMATH Open1493.62257arXiv2012.06958OpenAlexW3112942112MaRDI QIDQ5089735FDOQ5089735

Authors: Justin Solomon, Kristjan Greenewald, H. N. Nagaraja 

Publication date: 15 July 2022

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

Abstract: We introduce $k$-variance, a generalization of variance built on the machinery of random bipartite matchings. $K$-variance measures the expected cost of matching two sets of $k$ samples from a distribution to each other, capturing local rather than global information about a measure as $k$ increases; it is easily approximated stochastically using sampling and linear programming. In addition to defining $k$-variance and proving its basic properties, we provide in-depth analysis of this quantity in several key cases, including one-dimensional measures, clustered measures, and measures concentrated on low-dimensional subsets of $mathbb{R}^n$. We conclude with experiments and open problems motivated by this new way to summarize distributional shape.

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

Recommendations

• scientific article; zbMATH DE number 1304696
• Variance and clustering
• Extended generalised variances, with applications
• A notion of stability for \(k\)-means clustering
• Variance and covariance of distributions on graphs

zbMATH Keywords

clusteringoptimal transportvarianceWasserstein

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Optimal transportation (49Q22) Order statistics; empirical distribution functions (62G30)

Cites Work

• Computational optimal transport. With applications to data sciences
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Asymptotics for transportation cost in high dimensions
• Probability theory of classical Euclidean optimization problems
• Almost sure convergence of the minimum bipartite matching functional in Euclidean space
• Combinatorial Optimization Over Two Random Point Sets
• Title not available (Why is that?)
• On algorithms for permuting large entries to the diagonal of a sparse matrix
• Title not available (Why is that?)
• On the theory of order statistics
• Relations, bounds and approximations for order statistics
• Order Statistics
• Concentration of measure and isoperimetric inequalities in product spaces
• Constructive quantization: approximation by empirical measures
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
• The mean difference and the mean deviation of some discontinuous distributions
• Convergence of asymptotic costs for random Euclidean matching problems
• Finer estimates on the \(2\)-dimensional matching problem
• Euclidean random matching in 2D for non-constant densities

Cited In (1)

• Variance and clustering

This page was built for publication: \(k\)-variance: a clustered notion of variance

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