English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Semidefinite programming (SDP) is a powerful tool for tackling a wide rangeof computationally hard problems such as clustering. Despite the high accuracy,semidefinite programs are often too slow in practice with poor scalability onlarge (or even moderate) datasets. In this paper, we introduce a linear timecomplexity algorithm for approximating an SDP relaxed $K$-means clustering. Theproposed sketch-and-lift (SL) approach solves an SDP on a subsampled datasetand then propagates the solution to all data points by a nearest-centroidrounding procedure. It is shown that the SL approach enjoys a similar exactrecovery threshold as the $K$-means SDP on the full dataset, which is known tobe information-theoretically tight under the Gaussian mixture model. The SLmethod can be made adaptive with enhanced theoretic properties when the clustersizes are unbalanced. Our simulation experiments demonstrate that thestatistical accuracy of the proposed method outperforms state-of-the-art fastclustering algorithms without sacrificing too much computational efficiency,and is comparable to the original $K$-means SDP with substantially reducedruntime.

Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering