Publication
SIMODS
Paper

๐‘˜ -Variance: A Clustered Notion of Variance

View publication

Abstract

We introduce ๐‘˜-variance, a generalization of variance built on the machinery of random bipartite matchings. ๐‘˜-variance measures the expected cost of matching two sets of ๐‘˜ samples from a distribution to each other, capturing local rather than global information about a measure as ๐‘˜ increases; it is easily approximated stochastically using sampling and linear programming. In addition to defining ๐‘˜-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 โ„๐‘›. We conclude with experiments and open problems motivated by this new way to summarize distributional shape.

Date

01 Dec 2022

Publication

SIMODS

Authors

Topics

Share