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

Kernel $k$-means clustering can correctly identify and extract a far morevaried collection of cluster structures than the linear $k$-means clusteringalgorithm. However, kernel $k$-means clustering is computationally expensivewhen the non-linear feature map is high-dimensional and there are many inputpoints. Kernel approximation, e.g., the Nystr\"om method, has been applied inprevious works to approximately solve kernel learning problems when both of theabove conditions are present. This work analyzes the application of thisparadigm to kernel $k$-means clustering, and shows that applying the linear$k$-means clustering algorithm to $\frac{k}{\epsilon} (1 + o(1))$ featuresconstructed using a so-called rank-restricted Nystr\"om approximation resultsin cluster assignments that satisfy a $1 + \epsilon$ approximation ratio interms of the kernel $k$-means cost function, relative to the guarantee providedby the same algorithm without the use of the Nystr\"om method. As part of theanalysis, this work establishes a novel $1 + \epsilon$ relative-error tracenorm guarantee for low-rank approximation using the rank-restricted Nystr\"omapproximation. Empirical evaluations on the $8.1$ million instance MNIST8Mdataset demonstrate the scalability and usefulness of kernel $k$-meansclustering with Nystr\"om approximation. This work argues that spectralclustering using Nystr\"om approximation---a popular and computationallyefficient, but theoretically unsound approach to non-linear clustering---shouldbe replaced with the efficient and theoretically sound combination of kernel$k$-means clustering with Nystr\"om approximation. The superior performance ofthe latter approach is empirically verified.

Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds