PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shusen Wang, Alex Gittens, Michael W. Mahoney

arXiv:1706.02803v4cs.LGstat.ML

TL;DR

Linear k-means misses some non-linear cluster structures, and full kernel k-means is computationally expensive. The paper combines rank-restricted Nyström approximation with linear k-means and establishes approximation guarantees. Its experiments report that the approach consistently outperforms Nyström spectral clustering and scales to an 8.1-million-vector dataset.

  • Problem

    Linear k-means does not recover some non-spherical clusters, while full kernel k-means can be expensive because it requires full kernel-matrix computations and feature decomposition.

    Source: §1 · pp. 2–3

  • Method

    The method rank-restricts Nyström features and applies linear k-means, using projection-cost preservation to analyze its approximation guarantee.

    Source: §1.1 · p. 4, §1.2 · p. 5

  • Results

    Approximate kernel k-means consistently outperforms approximate spectral clustering, and the distributed implementation clusters 8.1 million vectors.

    Source: §7 · pp. 26–27

  • Takeaways & Limitations

    The authors suggest rank-restricted Nyström kernel k-means for clustering moderately large-scale data, in combination with distributed computing frameworks.

    Source: §7 · p. 27

    The authors cannot establish the 1 + epsilon guarantee without rank restriction, but do not know whether the restriction is necessary.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

Kernel $k$-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear $k$-means clustering algorithm. However, kernel $k$-means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel approximation, e.g., the Nystr\"om method, has been applied in previous works to approximately solve kernel learning problems when both of the above conditions are present. This work analyzes the application of this paradigm to kernel $k$-means clustering, and shows that applying the linear $k$-means clustering algorithm to $\frac{k}{\epsilon} (1 + o(1))$ features constructed using a so-called rank-restricted Nystr\"om approximation results in cluster assignments that satisfy a $1 + \epsilon$ approximation ratio in terms of the kernel $k$-means cost function, relative to the guarantee provided by the same algorithm without the use of the Nystr\"om method. As part of the analysis, this work establishes a novel $1 + \epsilon$ relative-error trace norm guarantee for low-rank approximation using the rank-restricted Nystr\"om approximation. Empirical evaluations on the $8.1$ million instance MNIST8M dataset demonstrate the scalability and usefulness of kernel $k$-means clustering with Nystr\"om approximation. This work argues that spectral clustering using Nystr\"om approximation---a popular and computationally efficient, but theoretically unsound approach to non-linear clustering---should be replaced with the efficient and theoretically sound combination of kernel $k$-means clustering with Nystr\"om approximation. The superior performance of the latter approach is empirically verified.

1. Introduction

Linear k-means can miss non-spherical clusters, while full kernel k-means is computationally expensive. The paper presents a rank-restricted Nyström approach with approximation guarantees and compares it with existing Nyström methods.

1. Introduction

  • Ring-shaped clusters with coincident centers are not recovered by linear k-means, while full kernel k-means costs O(n^3 + n^2d + Tn^2k).The kernel trick lets the objective use feature-space inner products without explicitly computing potentially high-dimensional features.Source: §1 · pp. 2–3
  • For s = k/epsilon and the stated c, Nyström features followed by the same linear k-means algorithm give a 1 + O(epsilon) relative guarantee with probability at least 0.9.The method extracts c features, reduces them to s dimensions, then applies linear k-means.Source: §1 · p. 4

1.1 Contributions

  • The authors cannot establish the guarantee without rank restriction, whose necessity is unknown; the restriction also reduces the cost of the linear k-means step.The paper also establishes a novel relative-error trace norm bound for rank-restricted Nyström approximation.Source: §1.1 · pp. 4–5

1.2 Relation to Prior Work

  • Unlike Musco and Musco (2017), the guarantees cover sketching methods meeting two stated properties and use rank-restricted Nyström features.The paper positions this approach as a theoretically supported, empirically competitive alternative to Nyström spectral clustering.Source: §1.2 · pp. 5–6, §1.1 · p. 5

1.3 Paper Organization

  • The paper proceeds from notation and sketching background to theoretical results, comparisons and evaluations, a distributed implementation, and a conclusion.Proofs are provided in the appendices.Source: §1.3 · p. 6

2. Notation

This section establishes the paper's notation for matrices, vectors, sets, decompositions, norms, and sketching methods.

2. Notation

  • The notation section defines identity and zero objects, the index set [n], and a k-partition as disjoint sets whose union is [n].It also defines set cardinality.Source: §2 · pp. 6–7
  • The section defines compact SVD and, for symmetric positive semidefinite matrices, its correspondence to an eigenvalue decomposition; truncated SVD gives an optimal rank-s approximation in unitarily invariant norms.It also introduces leverage scores and coherence for singular-vector subspaces.Source: §2 · p. 7
  • A sketch replaces a matrix with a smaller matrix, using column selection or random projection; the section also describes sampling and projection methods with differing costs.CountSketch applies in O(nnz(A)) time, while SRHT applies to a dense matrix in O(mn log c) time.Source: §2 · pp. 7–8

3. Our Main Results: Improved SPSD Matrix Approximation and Kernel k-means Approximation

The section establishes guarantees for rank-restricted Nyström approximation and applies them to kernel k-means, alongside results for KPCA and the power method.

3.1 The Nyström Method

  • Theorem 1 gives a novel relative-error trace-norm guarantee for rank-restricted Nyström approximation (CW†CT)s, a form prior analyses had not covered.Source: §3.1 · pp. 9–10

3.2 Main Result for Approximate Kernel k-means

  • Theorem 2 compares clustering from Nyström features with the output of a γ-approximate linear k-means solver under a prescribed sketch-size condition.Source: §3.2 · p. 11
  • On MNIST8M, Figure 2 shows that larger c improves mean NMI and stability, while performance is non-monotonic in s and can worsen when s is too large.Source: §3.2 · p. 11, Figure 2 · p. 12

3.3 Approximate Kernel k-Means with KPCA and Power Method

  • For KPCA, k/epsilon features suffice for a (1 + epsilon) objective approximation; prior approaches used s = k without approximation-ratio guarantees.Source: §3.3 · pp. 12, 14
  • A few power-iteration rounds can provide sufficiently accurate eigenspace estimates, but the method requires forming the full K and may not fit in memory.Source: §3.3 · p. 13

4. Comparison to Spectral Clustering with Nystr¨om Approximation

Nyström-approximated kernel k-means is presented as an equally efficient, more theoretically principled alternative to Nyström spectral clustering. In experiments, it is more accurate across sketch sizes and elapsed times.

4.1 Background

  • At equivalent computational cost, Nyström kernel k-means is described as more theoretically sound and effective in practice than Nyström spectral clustering.Source: §4.1 · p. 14

4.2 Spectral Clustering with Nyström Approximation

  • Nyström spectral clustering lacks a known bounded approximation ratio, and its approximate affinity matrix can yield negative degrees or a Laplacian that is not SPSD.Negative entries can make the degree normalization non-real; even when it is real, the resulting Laplacian's eigenvectors may not provide useful clustering coordinates.Source: §4.2 · p. 15
  • Small perturbations in the approximate degree matrix can make the approximate Laplacian far from the true one and strongly affect its eigenvectors.Source: §4.2 · p. 15
  • Approximating the normalized affinity matrix instead requires forming the full K at quadratic cost, and the resulting SPSD matrix is not necessarily a graph Laplacian.Its off-diagonal entries need not be non-positive, and its smallest eigenvalue may be nonzero.Source: §4.2 · p. 15

4.3 Empirical Comparison with Approximate Spectral Clustering using Nyström Approximation

  • Across three datasets, KK is more accurate than SC as a function of sketch size and elapsed time.Both methods use uniform-sampling Nyström approximation; Figure 3 compares their runtimes and accuracies.Source: Figure 3 · p. 17, §4.3 · p. 18

5. Single-Machine Medium-Scale Experiments

The experiments compare Nyström, random feature maps, and the two-step method for medium-scale kernel k-means. Nyström outperforms the alternatives in most reported comparisons, while the effect of target rank varies by experiment scale.

5. Single-Machine Medium-Scale Experiments

  • Objective values could be evaluated for the Mushrooms and PenDigits datasets in the medium-scale experiments.The comparison also covers NMI and includes the two-step method alongside Nyström and random feature maps.Source: §5 · p. 18, §5.2 · p. 19

5.1 Single-Machine Implementation of Approximate Kernel k-Means

  • The approximate kernel k-means pipeline applies Nyström approximation, dimensionality reduction, then linear k-means to features B.Its parameters satisfy k ≤ s < ℓ ≤ c ≪ n; uniform sampling can form the sketches while avoiding most of K.Source: §5.1 · pp. 18–19
  • The implementation uses CW⁻¹_ℓCᵀ rather than CW†Cᵀ because small singular values can make the Moore–Penrose inverse numerically unstable.The authors state that they do not currently have theory for this regularization heuristic.Source: §5.1 · p. 18

5.2 Comparing Nyström, Random Feature Maps, and Two-Step Method

  • Across the experiments, Nyström outperforms random feature maps in most cases, and both consistently outperform the two-step method.All compared methods improve as sketch size c increases; quality is assessed using NMI and objective values.Source: §5.2 · p. 19
  • In medium-scale experiments, target rank s has little impact on NMI and objective value, unlike the large-scale experiments.At large scale, choosing s properly yields better NMI than using an over-small or over-large s.Source: §5.2 · p. 19

6. Large-Scale Experiments using Distributed Computing

The distributed Spark implementation clusters 8.1 million MNIST8M instances, with runtime and clustering quality affected by parallelism, sketch size, and target dimension.

6. Large-Scale Experiments using Distributed Computing

  • The experiments varied node count, sketch size c, and target dimension s to assess runtime and clustering performance.The distributed implementation uses a three-stage workflow: Nyström approximation, dimensionality reduction, and linear k-means clustering.Source: §6 · p. 22

6.1 Experimental Setup

  • The distributed method uses uniform sampling for the Nyström step and Spark for dimensionality reduction and linear k-means on MNIST8M’s 8.1 million instances.The implementation was evaluated on NERSC’s Cori supercomputer.Source: §6 · p. 22, §6.1 · p. 22

6.2 Effect of Increased Parallelism

  • 15 minutes on average sufficed to cluster 8.1 million instances into 10 clusters using 32 nodes; the Nyström stage scaled inversely with node count.The Nyström stage needs only two communication rounds, with time spent mostly on executor computation.Source: §6.2 · p. 23, Figure 6 · p. 24
  • Increasing node count from 32 to 64 and beyond increased dimensionality-reduction and k-means runtimes because Spark communication overheads grew.The per-node computation decreased, but communication overheads made these iterative stages less performant.Source: §6.2 · p. 23

6.3 Effect of Sketch Size c

  • Larger sketch sizes improved clustering performance for fixed k and s, while Nyström runtime grew superlinearly with sketch size.The authors identify a trade-off between clustering performance and computational cost.Source: Table 5 · p. 24, §6.3 · p. 25, Figure 7 · p. 25

6.4 Effect of Target Dimension s

  • For fixed k and c, moderately increasing target dimension s improved clustering, but NMI deteriorated as s increased from 80 to 160.Dimensionality-reduction and linear k-means runtimes increase with s, while the Nyström runtime is unaffected; the authors conclude that setting s properly benefits both accuracy and computation.Source: §6.4 · p. 25, Table 6 · p. 26, Figure 8 · p. 26

7. Conclusion

The paper presents rank-restricted Nyström kernel k-means as a theoretically guaranteed, scalable alternative to approximate spectral clustering. Its guarantees include a kernel k-means approximation ratio and a relative-error trace-norm bound.

7. Conclusion

  • Experiments showed that rank-restricted Nyström kernel k-means consistently outperforms approximate spectral clustering.The conclusion characterizes the kernel k-means combination as theoretically sound, practically useful, and scalable to large datasets.Source: §7 · pp. 26–27
  • Using s = k/ϵ Nyström features guarantees a 1 + O(ϵ) kernel k-means approximation ratio with high probability.The comparison is relative to the guarantee of the same linear k-means algorithm without Nyström approximation.Source: §7 · p. 26
  • The rank-restricted Nyström approximation has a 1 + ϵ relative-error low-rank approximation guarantee in the trace norm.The paper presents this as an intermediate theoretical result of independent interest.Source: §7 · p. 26

Appendix A. Proof of Theorem 1

  • The proof of Theorem 1 uses technical lemmas to establish structural and approximation properties before completing the theorem’s proof.The appendix also describes extending the analysis to the power method.Source: Appendix A · p. 27, §A.1 · p. 29

A.1 Technical Lemmas

  • Lemma 6 establishes a matrix identity used in analyzing the rank-restricted Nyström method.For the specified orthonormal basis Q, QQT A equals U(UT A)s.Source: §A.1 · p. 28

A.2 Structural Result and Approximate Matrix Multiplication Properties

This section develops a structural result for rank-restricted Nyström approximation and identifies sketching properties used in the low-rank approximation analysis.

Structural result

  • Lemma 8 gives a structural result for any sketching matrix P, so randomness in an algorithm enters only through P.The result relates the projection onto a constructed subspace to a truncated approximation of K’s square root.Source: §A.2 · p. 30

Approximate matrix multiplication

  • Lemma 10 identifies subspace-embedding and approximate matrix-multiplication properties used to prove the relative-error result.The properties hold for the listed sketching methods when their sketch dimensions are sufficiently large.Source: §A.2 · pp. 31–32
  • The sketching methods covered include uniform sampling, leverage-score sampling, Gaussian projection, SRHT, and CountSketch.Sufficient sketch dimensions are tabulated for the stated sketching properties.Source: §A.2 · p. 31, Table 7 · p. 32

A.3 Completing the Proof of Theorem 1

The proof sequence applies Theorem 1 and auxiliary lemmas to establish Theorem 2, using projection-cost preservation to connect low-rank approximations with kernel k-means clustering.

A.3 Completing the Proof of Theorem 1

  • Theorem 1’s proof is completed by combining the stated sketching guarantees and structural result, yielding simultaneous properties with probability at least 0.9.The proof invokes Lemmas 7 and 8 to derive the theorem’s claims.Source: §A.3 · pp. 32–33

Appendix B. Proof of Theorem 2

B.1 Projection-Cost Preservation via Low-Rank Approximation

  • A sufficiently accurate trace-norm approximation of AAT by a rank-s matrix in A’s span yields projection-cost preservation.The stated lemma supplies a route from low-rank approximation to preservation of costs over rank-k projections.Source: §B.1 · p. 34

B.2 Linear k-Means Clustering and Projection-Cost Preservation

  • Cluster indicator matrices encode partitions, and their products XXT are rank-k projections used to express the linear k-means objective.The rows of XXT A give the corresponding cluster centroids.Source: §B.2 · pp. 34–35

B.3 Kernel k-Means Clustering

  • For kernel k-means, the kernel matrix K = ΦΦT contains the information in feature matrix Φ relevant to clustering.The kernel-trick lemma relates the clustering objective to the eigendecomposition of K.Source: §B.3 · p. 36

B.4 Completing the Proof of Theorem 2

Theorem 15 states an approximation guarantee for Nyström-based kernel k-means. Its proof connects a rank-restricted Nyström sketch to linear k-means on the kernel features.

B.4 Completing the Proof of Theorem 2

  • The proof uses B as a rank-k projection-cost-preserving sketch, then relates clustering B to linear k-means on the rows of K^1/2.The proof finally invokes the equivalence between clustering rows of K^1/2 and rows of the feature matrix Φ.Source: §B.4 · p. 37
  • Theorem 15 states a 1 + epsilon + k/s approximation ratio with probability at least 0.9 for its Nyström-based kernel k-means construction.It forms B from the rank-s truncation of the Nyström approximation and clusters B's rows with a gamma-approximate k-means algorithm.Source: §B.4 · p. 37
  • Theorem 15 is equivalent to Theorem 2, so proving it establishes Theorem 2.Source: §B.4 · p. 37

Appendix C. Proof of Theorem 4

  • Theorem 4's algorithm draws a Gaussian projection, applies t power iterations, orthogonalizes it, and constructs B from the rank-s Nyström approximation.The construction computes C = KU and W = U^T KU before choosing B so that BB^T equals the rank-s truncation of CW†C^T.Source: Appendix C · p. 38

C.1 Rank-Restricted Nystr¨om with Power Method

This section analyzes rank-restricted Nyström approximation with power iteration. Its theorem and supporting lemma specify the iteration setup and a probability qualification for the bound.

C.1 Rank-Restricted Nystr¨om with Power Method

  • Theorem 16 uses t = O(log(n/epsilon) log(sigma_s/sigma_{s+1})) power iterations; for c = s, its bound holds with constant probability depending on s.Source: §C.1 · p. 38
  • Theorem 16's proof invokes Lemma 17 to establish its result for both c > s and c = s.Source: §C.1 · pp. 38–39
  • Lemma 17 defines U as an orthonormal basis for K^tP and sets C = KU and W = U^T KU, assuming P^T V_s has full column rank.Source: §C.1 · p. 39

C.2 Completing the Proof of Theorem 4

Theorem 18 states a probabilistic guarantee for clustering the rows of B produced by the power-method construction. Its proof derives the needed assumptions from Theorem 16 and Theorem 1.

C.2 Completing the Proof of Theorem 4

  • Theorem 18 bounds the output of any gamma-approximate k-means algorithm applied to B, using t = O(log(n/epsilon) log(sigma_s/sigma_{s+1})) power iterations.Source: §C.2 · p. 40
  • For c = s, the theorem's inequality holds with probability 0.9 - O(s^-tau), where tau is a constant.Source: §C.2 · p. 40
  • The proof applies Theorem 16 to obtain one assumption and uses Theorem 1 to establish the other before invoking Lemma 14.Source: §C.2 · p. 40

Appendix D. Proof of Lemma 11

The proof of Lemma 11 proceeds through Lemma 19, which considers a rank-s approximation under two assumptions and gives a bound for any rank-k orthogonal projection.

Appendix D. Proof of Lemma 11

  • Assumption 2 represents the rank-s approximation through an orthogonal projection matrix M, with the relation stated as A-tilde_s A-tilde_s^T = A M A^T.Source: Appendix D · p. 40
  • Lemma 19 states a bound for any rank-k orthogonal projection when the rank-s approximation satisfies Assumptions 1 and 2.Source: Appendix D · p. 40
  • The proof of Lemma 11 applies Lemma 19 under Assumptions 1 and 2 to bound the expression used in the argument.Source: Appendix D · pp. 41–42

Appendix E. Proof of Lemma 12

The proof invokes B’s projection-cost preservation property and the guarantee of a γ-approximate k-means algorithm; a later inequality uses γ ≥ 1 and α ≥ 0.

Appendix E. Proof of Lemma 12

  • B’s projection-cost preservation property supplies a constant α ≥ 0 for rank-k orthogonal projections Π1 and Π2.The resulting two inequalities hold simultaneously with probability at least 1 − 2δ.Source: Appendix E · p. 42
  • The proof applies the definition of a γ-approximate k-means algorithm to the preceding result.Source: Appendix E · p. 42
  • The second inequality in the combined result follows from γ ≥ 1 and α ≥ 0.Source: Appendix E · p. 42
Loading 1706.02803v4…