Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering

By Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn. 2018

151 citations recorded by the source corpus.

Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log(k /ε) / ε2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p. For k-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Ravi Kumar
2. Piotr Indyk
3. David P. Woodruff

In Computer Vision and Pattern Recognition

1. Ravi Kumar
2. Piotr Indyk
3. Alisa Chang
4. Badih Ghazi
5. Pasin Manurangsi
6. Ping Li
7. Luc Van Gool
8. Kaiming He

Citations in the corpus

• Scalable Fair Clustering (2019, methodology): “The running time can be reduced further by applying dimensionality reduction techniques, see, e.g., Cohen et al. (2015); Makarychev et al. (2018) and the references therein.”
• Locally Private k-Means in One Round (2021, background): “Specifically, the breakthrough work of Makarychev et al. (2019) allows one to randomly project to d = O (log k ) dimensions while maintaining the objective for any given partition.”