Event Title
The Voronoi Means Conjecture
Location
Crow 204
Start Date
7-19-2016 3:30 PM
End Date
19-7-2016 3:50 PM
Description
We recently developed a relax-and-round algorithm for $k$-means clustering. When applied to balanced spherical Gaussian mixtures of unit entrywise variance, this algorithm clusters most points according to Gaussian component provided the minimum distance between component centers is at least some polynomial in $k$. This talk introduces a new conjecture called the Voronoi Means Conjecture, which implies that this distance for successful clustering must exhibit $k$-dependence as an artifact of $k$-means. The conjecture is a statement about highly symmetric collections of vectors, and I will announce a prize for its resolution. (This is joint work with Soledad Villar and Rachel Ward at the University of Texas at Austin.)
The Voronoi Means Conjecture
Crow 204
We recently developed a relax-and-round algorithm for $k$-means clustering. When applied to balanced spherical Gaussian mixtures of unit entrywise variance, this algorithm clusters most points according to Gaussian component provided the minimum distance between component centers is at least some polynomial in $k$. This talk introduces a new conjecture called the Voronoi Means Conjecture, which implies that this distance for successful clustering must exhibit $k$-dependence as an artifact of $k$-means. The conjecture is a statement about highly symmetric collections of vectors, and I will announce a prize for its resolution. (This is joint work with Soledad Villar and Rachel Ward at the University of Texas at Austin.)