Large-Scale High-Dimensional Clustering with Fast Sketching

Antoine Chatalic, Rémi Gribonval, Nicolas Keriven

Abstract

In this paper, we address the problem of high-dimensional k-means clustering in a large-scale setting, i.e. for datasets that comprise a large number of items. Sketching techniques have already been used to deal with this “large-scale” issue, by compressing the whole dataset into a single vector of random nonlinear generalized moments from which the k centroids are then retrieved efficiently. However, this approach usually scales quadratically with the dimension; to cope with high-dimensional datasets, we show how to use fast structured random matrices to compute the sketching operator efficiently. This yields significant speed-ups and memory savings for high-dimensional data, while the clustering results are shown to be much more stable, both on artificial and real datasets.
BibTeX
@inproceedings{chatalic2018large,
  author = {Antoine Chatalic and Rémi Gribonval and Nicolas Keriven},
  title = {{Large-Scale High-Dimensional Clustering with Fast Sketching}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  doi = {10.1109/icassp.2018.8461328},
}

Loading related content...

Figure