Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering. (arXiv:2201.08226v1 [stat.ML])

Semidefinite programming (SDP) is a powerful tool for tackling a wide range
of computationally hard problems such as clustering. Despite the high accuracy,
semidefinite programs are often too slow in practice with poor scalability on
large (or even moderate) datasets. In this paper, we introduce a linear time
complexity algorithm for approximating an SDP relaxed $K$-means clustering. The
proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset
and then propagates the solution to all data points by a …

arxiv clustering ml