QuicK-means: Acceleration of K-means by learning a fast transform

Hachem Kadri; Liva Ralaivola; Luc Giffon; Valentin Emiya

REVIEW 2 major objections 7 minor 20 references

QuicK-means: Acceleration of K-means by learning a fast transform

T0 review · 2 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read QuicK-means claims that a sparse-factor decomposition of the centroid matrix cuts the per-iteration cost of K-means assignment from $\mathcal{O}(N K D)$ to $\mathcal{O}(N(A \log A + B))$ with a non-increasing objective.

desk verdict Novel and worth refereeing, but the headline complexity guarantee is not actually proven—the sparse-factor projection only enforces a lower bound on non-zeros. read the letter →

arxiv 1908.08713 v1 pith:SLSZ2ELB submitted 2019-08-23 cs.LG stat.ML

Luc Giffon , Valentin Emiya , Liva Ralaivola , Hachem Kadri This is my paper · ORCID

classification cs.LGstat.ML

keywords K-meanssparsematrixfactorizationfasttransformscomputationalcomplexityNyströmapproximationclustering

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

QuicK-means proposes a variant of K-means in which the $K \times D$ centroid matrix is represented as a product of $Q = \mathcal{O}(\log A)$ sparse matrix factors, with $A = \min(K,D)$, learned from data at each iteration. The paper claims this reduces the assignment step, usually the $\mathcal{O}(N K D)$ bottleneck, to $\mathcal{O}(N(A \log A + B))$ operations, where $B = \max(K,D)$, both at training time and when assigning new points. It proves that the objective driving the alternating updates is non-increasing, so the accelerated scheme inherits a convergence guarantee of the same descent kind as the standard K-means algorithm. The payoff is that for large $N$, $K$, or $D$, clustering and downstream tasks such as Nyström approximation become substantially cheaper without a large loss in clustering quality.

What carries the argument

The load-bearing mechanism is the sparse-product approximation of the centroid matrix: $V = \prod_{q=1}^{Q} S_q$ with $Q = \mathcal{O}(\log A)$, each square factor having $\mathcal{O}(A)$ nonzeros per row and column and one end factor having $\mathcal{O}(B)$ nonzeros, where $A = \min(K,D)$ and $B = \max(K,D)$. The factorization is learned with a proximal alternating linearized minimization (PALM) routine that targets the reweighted matrix $\mathbf{A} = D_{\sqrt{n}}\mathbf{U}$; this is the step that turns an arbitrary dense centroid matrix into a fast operator. The same product is then applied as a chain of sparse matrix-vector products, which is exactly what converts the $\mathcal{O}(K D)$ per-point assignment cost into $\mathcal{O}(A \log A + B)$ and is reused unchanged at test time.

What would settle it

Take exact K-means centroids from a large high-dimensional dataset, form the reweighted matrix $\mathbf{A} = D_{\sqrt{n}}\mathbf{U}$, and compute the best relative Frobenius error $\min_{S_1,\ldots,S_Q} \|\mathbf{A} - \prod_{q=1}^{Q} S_q\|_F / \|\mathbf{A}\|_F$ under the sparsity constraints with $Q = \mathcal{O}(\log A)$; if that error stays near 1 for sparsity levels that deliver the advertised time bound, the expressivity premise and the resulting speed-quality trade-off fail.

Watch

Extended reading notes

Core claim

The central claim is that the centroid matrix never has to be formed or multiplied explicitly. After each centroid re-estimation, QuicK-means reweights the $K \times D$ matrix of centroids by the cluster sizes, builds $\mathbf{A} = D_{\sqrt{n}}\mathbf{U}$, and learns a factorization $\mathbf{A} \approx \prod_{q=1}^{Q} S_q$ in which each $S_q$ is sparse, with $\mathcal{O}(A)$ nonzeros per row and column (one rectangular end factor carries $\mathcal{O}(B)$ nonzeros), and the first factor is pinned to the diagonal weighting. Applying this product to a data point costs $\mathcal{O}(A \log A + B)$, so nearest-centroid assignment is no longer linear in $K D$ per point. The paper shows that alternating the assignment step with this factorized centroid update keeps the global objective $g(S_1,\ldots,S_Q,t)$ non-increasing, and it reports experiments on MNIST, Fashion-MNIST, and synthetic blobs where clustering quality stays close to standard K-means while assignment and Nyström inference become faster in high dimension.

Load-bearing premise

Everything rests on the assumption that real centroid matrices, after reweighting by cluster sizes, are well approximated by a product of $\mathcal{O}(\log A)$ sparse factors with bounded nonzeros per row and column; the paper does not prove this expressivity, so if actual centroids cannot be captured by such sparse factors, both the speed-up and the clustering quality degrade.

Editorial extensions

If this is right

Each iteration's assignment step drops from $\mathcal{O}(N K D)$ to $\mathcal{O}(N(A \log A + B))$, so the cost scales almost linearly in the smaller of $K$ and $D$ rather than in their product.
The factorized operator is available at inference time, so assigning a new batch of $N'$ points also costs $\mathcal{O}(N'(A \log A + B))$ instead of $\mathcal{O}(N' K D)$.
The objective $g(S_1,\ldots,S_Q,t)$ is non-increasing over the algorithm's iterations, giving QuicK-means a convergence guarantee of the same descent type as the standard K-means alternation.
When the number of points $N$ is large enough for the $\mathcal{O}(N(A \log A + B))$ term to dominate the $\mathcal{O}(A B \log^2 A)$ factorization overhead, the per-iteration saving translates into reduced training time, not just faster prediction.
Because the learned fast operator stands in for the landmark matrix, Nyström kernel approximation inherits the speed-up while keeping reconstruction and downstream classification accuracy close to the K-means-based Nyström method.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the sparse-product model is expressive enough on other workloads, the same centroid-as-fast-operator idea transfers to any learned-prototype method whose inner loop multiplies a prototype matrix by points, such as k-medoids, learning vector quantization, or dictionary learning.
The convergence result is a descent guarantee, not a guarantee of reaching the standard optimum; a clean test of the price of acceleration would be to compare final objective gaps from identical K-means++ initializations on data with varying intrinsic dimension.
Re-learning the factorization every iteration is the main computational overhead, so online or mini-batch updates of the sparse factors could make the training-time gain visible at smaller $N$ than the paper's experiments reach.
A direct stress test would use centroid matrices that are exactly products of sparse factors (for example, matrices associated with Hadamard or DCT transforms) to check that QuicK-means recovers near-exact clustering in the regime where the model is perfectly specified.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core idea is worth engaging: replace the centroid matrix in Lloyd's algorithm by a product of learned sparse factors, so the assignment step drops from O(NKD) to about O(N(A log A + B)). What is genuinely new is learning the fast transform from data at each Lloyd iteration, rather than fixing Hadamard or Fourier, and the convergence proof is credible: each of the two update steps reduces the objective, assuming palm4MSA has the standard PALM monotonicity. The experiments show real assignment-time speedups on the blobs dataset for K=256/512 and comparable clustering quality on MNIST and Fashion-MNIST, which is a useful proof of concept.

The main soft spot is the complexity theorem. The projection in Appendix A is described as only guaranteeing that each row and column has at least the sparsity level of non-zeros; nothing bounds the number of non-zeros above. The analysis in Section 3.3 simply assumes each square factor has O(A) non-zeros and the rectangular factor O(B). That is an assumption, not a consequence of the algorithm. The paper's own figures report measured parameter counts rather than a per-factor nnz bound, which fits with the absence of an upper-bound guarantee. This directly affects the stated complexity of the assignment step, so it needs fixing: either add an explicit upper-bound projection, or restate the complexity in terms of the actual nnz, or prove the relaxed projection keeps factors sparse enough.

A second honest limitation, acknowledged in the conclusion, is that training-time speedups are not actually achieved in the experiments. The abstract says 'may entail a reduction', which is fair, but the practical case currently rests on inference and Nyström acceleration.

There are also a few unfinished elements that a referee should ask about: a figure caption says 'to be completed', some table entries are N/A, and the notation around S_0 in Algorithm 1 is slightly inconsistent. None of these are load-bearing, but they suggest the manuscript was not fully polished.

Who is this for? Researchers working on K-means acceleration, learned fast transforms, or Nyström methods. The idea is solid enough that a serious editor should send it to peer review, with the expectation of a major revision that tightens the complexity claim and aligns the empirical narrative with what is actually shown.

Referee Report

2 major / 7 minor

Summary. The paper proposes QuicK-means (QK-means), a modification of Lloyd's algorithm in which the K×D centroid matrix U is replaced by a product V = ∏_{q=1}^Q S_q of Q sparse matrices learned via the palm4MSA algorithm. This is intended to reduce the cost of the assignment step (Eq. 2) from O(NKD) to O(N(A log A + B)) per iteration, with A = min(K,D) and B = max(K,D), assuming Q = O(log A) and each factor has O(A) non-zero entries (O(B) for the rectangular factor). The authors prove that the objective in Eq. (5) is non-increasing along the iterates, analyze the complexity of both QK-means and palm4MSA, and present experiments on MNIST, Fashion-MNIST, and a synthetic 'blobs' dataset for clustering, approximate nearest-neighbor search, and Nyström approximation. The paper is transparent about the fact that no expressivity guarantee for the sparse-product model is currently available.

Significance. If the sparsity assumptions were guaranteed, the result would be a useful contribution: it extends the idea of learning fast transforms to K-means, provides a credible monotone convergence argument via PALM, and shows empirically that very sparse factorizations can preserve clustering quality on standard datasets. The paper is also honest about its limitations, including the absence of expressivity guarantees and the lack of an end-to-end training-time speedup in the current implementation. The main correctable weakness is that the central complexity theorem is not actually implied by the algorithm as specified, because the projection used in palm4MSA enforces only a lower bound on per-row/column sparsity. This is a load-bearing gap that should be fixed before publication.

major comments (2)

[§3.3 and Appendix A (Algorithm 2, line 9)] The claimed complexity reductions in §3.3 and Algorithm 2 — O(N(A log A + B)) for the assignment step and O(AB(log^2 A + log B)) per palm4MSA iteration — rest on the assumption that every A×A factor has O(A) non-zero entries and the rectangular factor has O(B) non-zero entries. This assumption is not enforced by the algorithm. As the paper acknowledges in §4.1 and Appendix A, the projection P_E at line 9 of Algorithm 2 'only guarantees that the number of non-zero coefficients in each row and each column is at least the sparsity level', i.e. it imposes a lower bound, not an upper bound. A row-wise then column-wise top-s thresholding can add column-survivor entries to a row that has already used its row budget, so the actual per-factor nnz is not controlled by any argument in the paper. The empirical 'average number of parameters actually learned' (Figures 3 and 4) is not a per-factor nnz bound. To make the central speed claim rigorous, the authors should either (i) use a projection that enforces at most s non-zeros per row/column, or (ii) prove that the relaxed projection keeps each factor within O(A)/O(B) non-zeros, or (iii) state the complexity in terms of the actual nnz of the learned factors. Without one of these, the O(A log A + B) gain is not a theorem.
[Section 3.2, Proposition (convergence)] The Proposition states unconditionally that the objective values produced by Algorithm 1 are non-increasing. However, Algorithm 1 line 7 allows the use of 'palm4MSA algorithm or its hierarchical variant', and Section 4.2 explicitly states that the hierarchical variant is not guaranteed to converge and Figure 2b shows a small increase ('bump') in the objective (iteration 6). The proof of the Proposition assumes that the update step (8) is solved to a local minimum; the hierarchical variant does not satisfy this assumption. The Proposition should therefore be restricted to the standard palm4MSA solver (or to an exact solution of the subproblem), and the behaviour of the hierarchical variant should be stated separately.

minor comments (7)

[Section 3.2 (proof)] In the proof of the Proposition, 'Proove' should be 'Prove'.
[Figure 3 caption] The caption ends with 'to be completed.'; this unfinished phrase should be removed or completed before publication.
[Equation (2)] Equation (2) contains malformed norms ('‖‖‖...‖‖‖') that should be cleaned up for readability.
[Section 2.1] The K-means problem is written as arg min_{U,t} with U described as a set of cluster centers, while later U denotes a K×D matrix; the notation should be harmonized (e.g., using boldface for the matrix).
[Section 4.1] Fashion-MNIST is cited as '[15]', but reference [15] is the scikit-learn paper; the Fashion-MNIST dataset should be cited with its own reference.
[Table 3] The 'N/A' entries for brute-force, KD-tree, and ball-tree nearest-neighbor search are only explained in the caption as 'did not finish'; the text should clarify that these methods were excluded for time reasons.
[Section 3.2 (proof, bullet list)] In the bullet list, c_k is defined as ∑_{n:t_n=k} ‖x_n − u_k‖ without the exponent 2; since c_k is constant for the optimization, the missing square does not affect the argument, but it should be corrected for consistency with Eq. (1).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: QuicK-means complexity and convergence follow from an explicit sparse-product model and externally established PALM convergence, not from fitted values or self-citations.

full rationale

The paper's derivation chain is not circular. The convergence Proposition (Section 3.2) follows from the standard Lloyd argument plus the PALM/palm4MSA convergence guarantee of [2,9], which are external algorithms; the objective g is defined independently of the proof. The complexity claim (Section 3.3) is a direct consequence of the stated model: V is a product of Q=O(log A) sparse factors with O(A) nonzeros (square) and O(B) nonzeros (rectangular), giving O(A log A+B) matrix-vector products. This is an assumption-driven design bound, not a quantity fitted to data and then renamed a prediction. The paper explicitly acknowledges the absence of expressivity guarantees and reports measured parameter counts, so no fitted input is disguised as a prediction. The only caveat is that the palm4MSA projection in Appendix A enforces only a lower bound on per-row/column nonzeros, so the theoretical complexity is not guaranteed by the implementation; this is a correctness/validity concern about an unproven assumption, not a circular reduction. No load-bearing self-citations, imported uniqueness theorems, or ansatz-by-citation patterns are present.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central claims rest on two hyperparameters (number of factors Q and sparsity level), on the external PALM monotonicity result, and on an unproven expressivity assumption for the sparse-product model. No new physical entities are introduced.

free parameters (3)

Q (number of sparse factors) = Q = log2(A), A=min(K,D)
The number of factors is a design hyperparameter set to log2(A) in experiments (Section 4.1); complexity analysis assumes Q=O(log A).
Sparsity level = reported per experiment (e.g., 5)
Controls the number of non-zero coefficients per row/col in each factor; central quality/speed tradeoff knob, chosen before running (Section 4.1).
Lambda scaling factor in palm4MSA = computed internally
Normalization factor used in palm4MSA to avoid scaling indeterminacy (Appendix A); learned during optimization, not a fitted constant of the central claim.

assumptions (3)

standard math palm4MSA (or PALM) monotonically decreases its objective from any initialization.
Used in the centroid update proof (Section 3.2) to conclude g(S^(tau)) <= g(S^(tau-1)); this is a known convergence property of proximal alternating linearized minimization for nonconvex nonsmooth problems with Lipschitz gradients.
domain assumption The K x D centroid matrix can be well approximated by a product of Q sparse factor matrices with controlled sparsity.
No expressivity theorem is given; the paper relies on empirical evidence (Figures 2 and 5) and admits in Section 5 that expressiveness is still to be studied.
ad hoc to paper Sparse factors have at most O(A) non-zero coefficients per row/column (O(B) for the rectangular factor).
Appendix A states this as an assumption for the complexity analysis; the projection used in experiments (Section 4.1) only guarantees the number of nonzeros is at least the sparsity level, not at most, so this bound is not enforced.

how reviews work

0 comments

Cite this review

Pith. "Pith review of QuicK-means: Acceleration of K-means by learning a fast transform." pith.science (2026). https://pith.science/paper/SLSZ2ELB

@misc{pith2026190808713,
  author       = {Pith},
  title        = {Pith review of: QuicK-means: Acceleration of K-means by learning a fast transform},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SLSZ2ELB}},
  note         = {Machine review of arXiv:1908.08713}
}

abstract

K-means -- and the celebrated Lloyd algorithm -- is more than the clustering method it was originally designed to be. It has indeed proven pivotal to help increase the speed of many machine learning and data analysis techniques such as indexing, nearest-neighbor search and prediction, data compression; its beneficial use has been shown to carry over to the acceleration of kernel machines (when using the Nystr\"om method). Here, we propose a fast extension of K-means, dubbed QuicK-means, that rests on the idea of expressing the matrix of the $K$ centroids as a product of sparse matrices, a feat made possible by recent results devoted to find approximations of matrices as a product of sparse factors. Using such a decomposition squashes the complexity of the matrix-vector product between the factorized $K \times D$ centroid matrix $\mathbf{U}$ and any vector from $\mathcal{O}(K D)$ to $\mathcal{O}(A \log A+B)$, with $A=\min (K, D)$ and $B=\max (K, D)$, where $D$ is the dimension of the training data. This drastic computational saving has a direct impact in the assignment process of a point to a cluster, meaning that it is not only tangible at prediction time, but also at training time, provided the factorization procedure is performed during Lloyd's algorithm. We precisely show that resorting to a factorization step at each iteration does not impair the convergence of the optimization scheme and that, depending on the context, it may entail a reduction of the training time. Finally, we provide discussions and numerical simulations that show the versatility of our computationally-efficient QuicK-means algorithm.

Figures

Figures reproduced from arXiv: 1908.08713 by the authors.

**Figure 2.** Clustering results on MNIST (left) and Fashion-MNIST (right) for [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Clustering Blobs data: running times of the assignation step, averaged over 5 runs. The vertical [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Running time of nearest neighbor search on blobs data. Results are averaged over 5 runs (vertical [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]

**Figure 5.** Figure 5: Nyström approximation results: accuracy (left) and running times (right). The uniform sampling [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

[1]

How slow is the k-means method? InSymposium on Computational Geometry, pages 1–10, 2006

David Arthur and Sergei Vassilvitskii. How slow is the k-means method? InSymposium on Computational Geometry, pages 1–10, 2006

work page 2006
[2]

Proximal alternating linearized minimization or nonconvex and nonsmooth problems.Mathematical Programming, 146(1-2):459–494, 2014

Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization or nonconvex and nonsmooth problems.Mathematical Programming, 146(1-2):459–494, 2014

work page 2014
[3]

Randomized dimen- sionality reduction fork-means clustering

Christos Boutsidis, Anastasios Zouzias, Michael W Mahoney, and Petros Drineas. Randomized dimen- sionality reduction fork-means clustering. IEEE Transactions on Information Theory, 61(2):1045–1062, 2014

work page 2014
[4]

Revisiting the nyström method for improved large-scale machine learning

Alex Gittens and Michael W Mahoney. Revisiting the nyström method for improved large-scale machine learning. The Journal of Machine Learning Research, 17(1):3977–4041, 2016

work page 2016
[5]

Algorithm as 136: A k-means clustering algorithm.Journal of the Royal Statistical Society

John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm.Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1):100–108, 1979

work page 1979
[6]

Data clustering: 50 years beyond k-means.Pattern recognition letters, 31(8):651–666, 2010

Anil K Jain. Data clustering: 50 years beyond k-means.Pattern recognition letters, 31(8):651–666, 2010

2010
[7]

Sampling methods for the nyström method

Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Sampling methods for the nyström method. Journal of Machine Learning Research, 13(Apr):981–1006, 2012. 14 (a) Blobs: Nyström reconstruction error. (b) Blobs: Nyström inference time. (c) MNIST: Nyström reconstruction error. (d) MNIST: Nyström inference time. (e) Fashion-MNIST: Nyström reconstruction error. ...

work page 2012
[8]

Fastfood—approximating kernel expansions in loglinear time

Quoc Le, Tamás Sarlós, and Alex Smola. Fastfood—approximating kernel expansions in loglinear time. In International Conference on Machine Learning, 2013

work page 2013

Show all 20 references

[9]

Flexible multilayer sparse approximations of matrices and applications

Luc Le Magoarou and Rémi Gribonval. Flexible multilayer sparse approximations of matrices and applications. IEEE Journal of Selected Topics in Signal Processing, 10(4):688–700, 2016

2016
[10]

MNIST handwritten digit database, 2010

Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010

2010
[11]

Sparse embeddedk-means clustering

Weiwei Liu, Xiaobo Shen, and Ivor Tsang. Sparse embeddedk-means clustering. InAdvances in Neural Information Processing Systems, pages 3319–3327, 2017

2017
[12]

The Linear Complexity of Computation.Journal of the ACM, 22(2):184–194, April 1975

Jacques Morgenstern. The Linear Complexity of Computation.Journal of the ACM, 22(2):184–194, April 1975

1975
[13]

Scalable nearest neighbor algorithms for high dimensional data.IEEE transactions on pattern analysis and machine intelligence, 36(11):2227–2240, 2014

Marius Muja and David G Lowe. Scalable nearest neighbor algorithms for high dimensional data.IEEE transactions on pattern analysis and machine intelligence, 36(11):2227–2240, 2014

2014
[14]

Recursive sampling for the nystrom method

Cameron Musco and Christopher Musco. Recursive sampling for the nystrom method. InAdvances in Neural Information Processing Systems, pages 3833–3845, 2017

2017
[15]

Pedregosa, G

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R.Weiss, V.Dubourg, J.Vanderplas, A.Passos, D.Cournapeau, M.Brucher, M.Perrot, andE.Duchesnay. Scikit-learn: Machine learning in Python.Journal of Machine Learning Research,...

2011
[16]

Back to the future: Radial basis function networks revisited

Qichao Que and Mikhail Belkin. Back to the future: Radial basis function networks revisited. In AISTATS, pages 1375–1383, 2016

2016
[17]

Web-scale k-means clustering

David Sculley. Web-scale k-means clustering. InProceedings of the 19th international conference on World wide web, pages 1177–1178. ACM, 2010

2010
[18]

Compressed k-means for large-scale clustering

Xiaobo Shen, Weiwei Liu, Ivor Tsang, Fumin Shen, and Quan-Sen Sun. Compressed k-means for large-scale clustering. InThirty-First AAAI Conference on Artiﬁcial Intelligence, 2017

2017
[19]

Computationally eﬃcient nyström approximation using fast transforms

Si Si, Cho-Jui Hsieh, and Inderjit Dhillon. Computationally eﬃcient nyström approximation using fast transforms. In International Conference on Machine Learning, pages 2655–2663, 2016

2016
[20]

Local network community detection with continuous optimization of conductance and weighted kernel k-means.The Journal of Machine Learning Research, 17(1):5148–5175, 2016

Twan Van Laarhoven and Elena Marchiori. Local network community detection with continuous optimization of conductance and weighted kernel k-means.The Journal of Machine Learning Research, 17(1):5148–5175, 2016. A palm4MSA algorithm The palm4MSA algorithm [9] is given in Algori...

2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

How slow is the k-means method? InSymposium on Computational Geometry, pages 1–10, 2006

David Arthur and Sergei Vassilvitskii. How slow is the k-means method? InSymposium on Computational Geometry, pages 1–10, 2006

work page 2006

[2] [2]

Proximal alternating linearized minimization or nonconvex and nonsmooth problems.Mathematical Programming, 146(1-2):459–494, 2014

Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization or nonconvex and nonsmooth problems.Mathematical Programming, 146(1-2):459–494, 2014

work page 2014

[3] [3]

Randomized dimen- sionality reduction fork-means clustering

Christos Boutsidis, Anastasios Zouzias, Michael W Mahoney, and Petros Drineas. Randomized dimen- sionality reduction fork-means clustering. IEEE Transactions on Information Theory, 61(2):1045–1062, 2014

work page 2014

[4] [4]

Revisiting the nyström method for improved large-scale machine learning

Alex Gittens and Michael W Mahoney. Revisiting the nyström method for improved large-scale machine learning. The Journal of Machine Learning Research, 17(1):3977–4041, 2016

work page 2016

[5] [5]

Algorithm as 136: A k-means clustering algorithm.Journal of the Royal Statistical Society

John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm.Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1):100–108, 1979

work page 1979

[6] [6]

Data clustering: 50 years beyond k-means.Pattern recognition letters, 31(8):651–666, 2010

Anil K Jain. Data clustering: 50 years beyond k-means.Pattern recognition letters, 31(8):651–666, 2010

2010

[7] [7]

Sampling methods for the nyström method

Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Sampling methods for the nyström method. Journal of Machine Learning Research, 13(Apr):981–1006, 2012. 14 (a) Blobs: Nyström reconstruction error. (b) Blobs: Nyström inference time. (c) MNIST: Nyström reconstruction error. (d) MNIST: Nyström inference time. (e) Fashion-MNIST: Nyström reconstruction error. ...

work page 2012

[8] [8]

Fastfood—approximating kernel expansions in loglinear time

Quoc Le, Tamás Sarlós, and Alex Smola. Fastfood—approximating kernel expansions in loglinear time. In International Conference on Machine Learning, 2013

work page 2013