{"id":"79062f3e-8edc-4804-86d6-eb2404d4186f","arxiv_id":"1908.08713","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"QuicK-means represents k-means centroids as a product of sparse learned matrices, reducing per-point assignment cost and preserving the algorithm's convergence guarantee.","lead":"This paper introduces QuicK-means, a version of k-means clustering that stores the cluster centers as a chain of sparse matrices so that assigning a point to a cluster is much cheaper in high dimensions. A general reader might care because clustering is a workhorse behind search, compression, and kernel methods, and a provably convergent way to speed up its bottleneck step could help larger-scale applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The complexity claim is not guaranteed: the projection in Appendix A enforces only a lower bound on per-row/column non-zeros, so learned factors may exceed the O(A)/O(B) sparsity assumed in §3.3.","rationale":"The paper has a coherent idea: approximate the centroid matrix by a product of Q=O(log A) sparse matrices, apply it fast, and alternate with Lloyd assignment. The convergence proposition is plausible because each step minimizes the same objective (assignment step, then a PALM step initialized from the previous factors), and the empirical plots show non-increasing objective on MNIST and Fashion-MNIST. I also credit the authors for explicitly acknowledging in Section 5 that training-time wall-clock gains are not yet achieved and that expressivity is not theoretically established; those are honest limitations, not hidden defects. My concern is different and, to me, more central: the headline complexity O(N(A log A+B)) is a theorem about the algorithm only if the learned factors are sparse with O(A)/O(B) non-zeros. The paper's constraint sets are described only via a relaxation that guarantees 'at least' the sparsity level, never 'at most'. Thus the very quantity that makes the fast transform fast, per-factor nnz, is uncontrolled by the optimization as stated. This undermines the formal complexity claim independently of whether the sparse-product model can express centroid matrices. The reader's weakest assumption flagged the same Section 4.1 sentence but tied it to expressivity and clustering quality; I am flagging it as a direct violation of the complexity theorem's hypothesis. A simple instrumentation of Algorithm 2 would settle it. For these reasons I do not move the verdict: the issue is substantial but likely fixable (enforce an upper bound or state complexity in terms of observed nnz), so CONDITIONAL remains the right call.","tokens_in":12604,"tokens_out":13580,"duration_ms":154763,"concrete_test":"Instrument Algorithm 2 line 9: run palm4MSA on the Blobs and MNIST centroid matrices with the same sparsity levels as in §4, and record for each converged factor the maximum per-row and per-column nnz and the total nnz. Compare to the assumed budgets O(A) for square factors and O(B) for the rectangular factor. If any factor's nnz is not bounded by a constant times A (respectively B), or if the measured per-iteration assignment cost grows faster than N(A log A+B), the complexity theorem's premise is violated. As a complementary check, replace the projection with one that enforces an exact upper bound s per row and per column and rerun Figure 3; if timings are essentially unchanged, the missing upper bound is not practically harmful, but if they differ substantially, the paper should report the bounded variant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central complexity gain rests on the assumption in §3.3 and Appendix A that every square factor has O(A) non-zeros and the rectangular factor has O(B) non-zeros. But the projection used in palm4MSA (Algorithm 2, line 9) is described in §4.1 as 'only guarantees that the number of non-zero coefficients in each row and each column is at least the sparsity level'. Keeping the largest entries row-wise and column-wise can add column-survivor entries to rows that already have their row budget, so no argument in the paper bounds the actual per-factor nnz above by O(A) or O(B). If factors densify, the cost of applying V to a vector, and hence the per-iteration assignment cost O(N(A log A+B)) in Algorithm 1 line 3, is no longer what is stated. This is not an expressivity objection; it attacks the stated complexity theorem directly. The paper reports 'average number of parameters actually learned' in Figures 3 and 4 rather than a per-factor nnz bound, which is consistent with the absence of an upper-bound guarantee. The fix is to add an explicit upper-bound constraint, or a projection that guarantees at most s non-zeros per row/column, and restate the complexity in terms of the resulting nnz, or prove that the relaxed projection keeps nnz within O(A)/O(B).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12944,"tokens_out":11717,"duration_ms":104970,"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":[{"comment":"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.3 and Appendix A (Algorithm 2, line 9)"},{"comment":"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.","section":"Section 3.2, Proposition (convergence)"}],"minor_comments":[{"comment":"In the proof of the Proposition, 'Proove' should be 'Prove'.","section":"Section 3.2 (proof)"},{"comment":"The caption ends with 'to be completed.'; this unfinished phrase should be removed or completed before publication.","section":"Figure 3 caption"},{"comment":"Equation (2) contains malformed norms ('‖‖‖...‖‖‖') that should be cleaned up for readability.","section":"Equation (2)"},{"comment":"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":"Section 2.1"},{"comment":"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.","section":"Section 4.1"},{"comment":"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":"Table 3"},{"comment":"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).","section":"Section 3.2 (proof, bullet list)"}],"recommendation":"major_revision","confidential_remarks":"The paper is a fairly direct application of palm4MSA (Le Magoarou and Gribonval) to K-means; the novelty lies mainly in the convergence guarantee and the complexity analysis. The main issue—the gap between the assumed sparsity and the implemented projection—is fixable within the manuscript's scope, so I recommend major revision rather than rejection. I would encourage the authors to report per-factor nnz maxima rather than only averages if they retain the relaxed projection, and to qualify the convergence proposition for the hierarchical variant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nA 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.\n\nThere 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.\n\nWho 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.","headline":"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.","tokens_in":13436,"tokens_out":3154,"would_cite":false,"duration_ms":32047,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["K-means","sparse matrix factorization","fast transforms","computational complexity","Nyström approximation","clustering"],"falsifier":"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.","tokens_in":12435,"feed_emoji":"⚡","tokens_out":12634,"duration_ms":116408,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sparse factors cut K-means assignment to O(N(A log A + B))","feed_subtitle":"QuicK-means learns centroids as sparse matrix products, keeping clustering quality while cutting the per-iteration assignment cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the sparse-product matrix factorization algorithm that learns the fast transform at each centroid update","marker":"[9]"},{"why":"provides the proximal alternating linearized minimization convergence theory that underpins each factor-update step","marker":"[2]"},{"why":"establishes the linear-complexity principle that an operator factored into sparse matrices can be applied in near-logarithmic time","marker":"[12]"},{"why":"shows how structured fast-transform landmark matrices accelerate Nyström approximation, the application the paper extends","marker":"[19]"},{"why":"shows the number of K-means iterations grows with K, motivating a reduction in per-iteration cost","marker":"[1]"},{"why":"supplies the standard K-means formulation and iteration that QuicK-means modifies","marker":"[5]"}],"fun_headline_variants":["K-means sped up by learning sparse centroid transforms","QuicK-means: sparse factorized centroids cut assignment cost","Fast K-means via learned sparse matrix products","Sparse matrices slash K-means assignment complexity","Accelerating K-means with factorized centroids"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["K-means sped up by learning sparse centroid transforms","QuicK-means: sparse factorized centroids cut assignment cost","Fast K-means via learned sparse matrix products","Sparse matrices slash K-means assignment complexity","Accelerating K-means with factorized centroids"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1547,"prompt_tokens":1099,"completion_tokens":448,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":715,"completion_tokens_details":{"reasoning_tokens":369}},"tokens_in":715,"tokens_out":448,"duration_ms":4898,"temperature":1.0,"reasoning_tokens":369,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:31:29.155659+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Flexible multilayer sparse approximations of matrices and applications","cited_arxiv_id":null,"evidence_quote":"supplies the sparse-product matrix factorization algorithm that learns the fast transform at each centroid update"},{"cited_title":"Proximal alternating linearized minimization or nonconvex and nonsmooth problems.Mathematical Programming, 146(1-2):459–494, 2014","cited_arxiv_id":null,"evidence_quote":"provides the proximal alternating linearized minimization convergence theory that underpins each factor-update step"},{"cited_title":"The Linear Complexity of Computation.Journal of the ACM, 22(2):184–194, April 1975","cited_arxiv_id":null,"evidence_quote":"establishes the linear-complexity principle that an operator factored into sparse matrices can be applied in near-logarithmic time"},{"cited_title":"Computationally efficient nyström approximation using fast transforms","cited_arxiv_id":null,"evidence_quote":"shows how structured fast-transform landmark matrices accelerate Nyström approximation, the application the paper extends"},{"cited_title":"How slow is the k-means method? InSymposium on Computational Geometry, pages 1–10, 2006","cited_arxiv_id":null,"evidence_quote":"shows the number of K-means iterations grows with K, motivating a reduction in per-iteration cost"},{"cited_title":"Algorithm as 136: A k-means clustering algorithm.Journal of the Royal Statistical Society","cited_arxiv_id":null,"evidence_quote":"supplies the standard K-means formulation and iteration that QuicK-means modifies"}],"review_version":1}