k-variance: a clustered notion of variance

DOI10.1137/20M1385895MaRDI QIDQ5089735zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• Almost sure convergence of the minimum bipartite matching functional in Euclidean space
• Asymptotics for transportation cost in high dimensions
• Combinatorial Optimization Over Two Random Point Sets
• Computational optimal transport. With applications to data sciences
• Concentration of measure and isoperimetric inequalities in product spaces
• Constructive quantization: approximation by empirical measures
• Convergence of asymptotic costs for random Euclidean matching problems
• Euclidean random matching in 2D for non-constant densities
• Finer estimates on the 2-dimensional matching problem
• On algorithms for permuting large entries to the diagonal of a sparse matrix
• On the theory of order statistics
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Order Statistics
• Probability theory of classical Euclidean optimization problems
• Relations, bounds and approximations for order statistics
• 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

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)