Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

1 Introduction

• The paper addresses the difficulty that existing methods handle many records efficiently but struggle when both the number of records and data dimension are large.This motivates algorithms suitable for massive streams and distributed or parallel settings.Source: §1 · p. 2
• The method reduces data to coresets whose size depends on problem parameters and approximation quality, not the number of records or ambient dimension.Any approximation algorithm applied to the reduced set returns an approximate solution for the original data.Source: §1 · p. 2
• The coresets are mergeable: unions of reduced sets approximate unions of the original data, enabling streaming, distributed, parallel, and MapReduce-style processing.Each processor or memory-sized stream chunk can be reduced independently, after which only the reduced sets need communication.Source: §1 · pp. 2–3
• The main dimensionality-reduction result maps n points in d dimensions to n points in O(j/ε2) dimensions while preserving squared-distance sums to every j-dimensional subspace within a (1 + ε) factor.For PCA, the resulting coreset has cardinality O(j/ε), independent of both n and d; constant-cardinality coresets also apply to k-means queries.Source: §1 · p. 3
• For other objectives, the reduction removes ambient-dimension dependence from existing coreset constructions, while projective clustering requires integer-grid assumptions and retains polylogarithmic dependence on grid size and n.The construction applies to objectives such as k-means and k-line-means, but no dimension-independent construction of the stated general form exists for affine j-subspace k-clustering.Source: §1 · p. 3

Erratum

• The authors correct erroneous conference-version coreset sizes; in particular, projective-clustering coreset size is not independent of n.The updated results are summarized in Section 2.4.Source: Erratum · p. 3

Previous publications

• Compared with and, this version adds detailed applications, explicit streaming algorithms, proofs, pseudocode, explanations, and corrections, while lacks streaming algorithms for subspace approximation and projective clustering.The main results were previously published in.Source: Previous publications · p. 3

2 Preliminaries

• The preliminaries establish matrix and SVD notation, orthogonal projections, Frobenius-norm identities, distances to subspaces, and VC-dimension-based (η, ε)-approximation tools.These definitions provide the formal language and sampling bound used by the later coreset constructions.Source: §2 · pp. 4–6

2.1 Data Analysis Methods

• The section defines k-means as minimizing the sum of squared distances from data points to k centers, while noting that the general problem is APX-hard and cannot be approximated better than 1.0013 in polynomial time.The best stated approximation guarantee is 6.357, whereas polynomial-time (1 + ε)-approximations are available when k or d is constant.Source: §2.1 · p. 7

2.1.1 Principal Component Analysis

• PCA is formulated as finding a j-dimensional subspace minimizing squared distances, equivalently retaining the directions of greatest variance; the affine formulation handles unnormalized data.The optimal linear subspace is spanned by the first j right singular vectors, while affine PCA minimizes distance to p + L.Source: §2.1.1 · pp. 7–8

2.1.2 Subspace Clustering

• Subspace clustering generalizes k-means by replacing centers with k linear or affine j-dimensional subspaces and minimizing squared distance to the nearest subspace.It combines clustering with PCA: each cluster’s subspace captures its most important dimensions; k-means and one-subspace approximation are special cases.Source: §2.1.2 · p. 9

2.2 Coresets and Dimensionality Reductions

• The paper’s coreset definition permits a solution-independent additive constant ∆ while still approximating every candidate cost within a factor of 1 ± ε.∆ may depend on A, ε, and the candidate family C, but not on the particular candidate solution.Source: §2.2 · p. 11
• The framework reduces high-dimensional coreset construction by projecting points onto a sufficiently dimensional minimum-cost subspace and assigning discarded costs to ∆.This separates each point’s distance-to-subspace contribution from its contribution inside the low-dimensional subspace.Source: §2.2 · p. 11
• Small coresets do not exist for general j-subspace k-clustering, although integer-coordinate assumptions enable restricted constructions.Related work addresses the integer-coordinate setting and alternative objectives.Source: §2.2 · pp. 11–12
• For k-means, the Johnson–Lindenstrauss lemma reduces any matrix A ∈ R^{n×d} to O(n/ε2) dimensions with a (1 + ε)-factor, whereas BZD10 uses Θ(k/ε2) dimensions with a 2 + ε guarantee.SVD-based reduction gives a 2-approximation onto k dimensions, while approximate SVD gives a 2 + ε-approximation to k dimensions.Source: §2.2 · p. 12

2.3 Streaming algorithms

• In insertion-only streams, merge-and-reduce processes chunks into coresets and combines them in a tree, limiting each input point to O(log n) reductions while requiring precision adjustments as errors accumulate.The method supports arbitrary arrival order and small memory governed mainly by model parameters and the desired approximation factor.Source: §2.3 · pp. 12–13

2.4 Our results and closely related work

• The paper’s new coreset framework replaces high-dimensional inputs by a low-rank structured approximation and charges the projection residual as an additive cost for every clustering.The approximation rank depends only on cluster shape, cluster count, and ε.Source: §2.4 · p. 13
• The resulting coresets are, for most problems, independent of both the input dimension and the number of input points.The paper presents this as its main qualitative improvement over previous results.Source: §2.4 · p. 13
• For integral points with maximum l2-norm M, the j-dimensional subspace k-clustering coreset has size ˜O(log(Mn)h(j,k)/ε2), where h(j,k) depends only on j and k.The guarantee is stated for constant error probability.Source: §2.4 · p. 13
• The paper also provides streaming algorithms for subspace approximation, k-means, and j-dimensional subspace k-clustering, while leaving k-line means implicit through similar techniques.The streaming model maintains a weighted coreset so approximate solutions can be computed on data seen so far.Source: §2.3 · p. 12, §2.4 · p. 14
• A separate construction achieves coreset size independent of n and d for a restricted class of Bregman divergences.This extends the paper’s dimension- and input-size-independent coreset agenda beyond the principal clustering settings.Source: §2.4 · p. 14

3 Coresets for the linear j-subspace problem

• The analysis separates the data into a structured rank-m approximation and a pseudorandom residual whose squared Frobenius error is charged additively.This decomposition leads to an approximation of every j-subspace cost through Corollary 16.Source: §3 · pp. 15–16
• The coreset consists of the first m = O(j/ε) rows of the truncated-SVD matrix Σ^(m)V^T, with all weights equal to one.Truncating the SVD leaves only the first m rows nonzero, so these rows retain the relevant cost contribution.Source: §3 · pp. 16–17
• Theorem 17 guarantees a coreset with at most j + ⌈j/ε⌉ − 1 points that approximates the cost of every j-dimensional linear subspace.The construction outputs (S, ∆, w), with S ∈ R^{m×d} and ∆ > 0.Source: §3 · p. 17
• Computing the coreset by exact SVD takes O(min {nd^2, dn^2}) time.The stated runtime follows directly from the exact SVD computation.Source: §3 · p. 17

3.1 Discussion

• For PCA, the data must be centered at the origin, but coresets with different means cannot be straightforwardly united, limiting streaming use without prior normalization.Maintaining the mean separately does not fix the issue by simply subtracting it from the final coreset points; the affine case is deferred to the next section.Source: §3.1 · p. 17

4 Coresets for the Affine j-Subspace Problem

• The construction centers A by subtracting µ(A), computes a coreset for the centered matrix, doubles it with negatives to enforce zero mean, then scales, weights, and shifts it back.The zero-mean condition enables Lemma 18, while weighting and scaling compensate for the doubled coreset’s point count.Source: §4 · pp. 18–19
• For the affine j-subspace coreset, the construction outputs S ∈ R^(2m)×d, where m ≤ j + ⌈j/ε⌉ − 1, and Δ > 0.Source: §4 · p. 19
• dist2(A′, L) ≤ (n/(2m)) · dist2(S′′, L) + ∆ ≤ (1 + ε) · dist2(A′, L) for every linear subspace L.This centered linear-subspace guarantee combines with the mean-offset identity to obtain the affine guarantee.Source: §4 · pp. 18–19

4.1 Weighted Inputs

• For weighted inputs, integral weights can be represented by copies, while general weights are handled analytically by letting the common weight δ approach zero; algorithmically, scaling by √w represents weight w.The weighted algorithm applies the centered transformation using rows √w_i(A_i∗ − µ(A)^T).Source: §4.1 · p. 20

• The reduction applies to clustering or shape-fitting problems whose candidate solution lies in a j-dimensional subspace, including k-means with j=k.It uses an arbitrary subspace L represented by orthonormal bases for L and its orthogonal complement.Source: §5 · p. 20
• Projecting A and A(m) onto L yields corresponding points whose summed squared differences are small relative to the projection cost.The approximation condition requires m ≥ j + ⌈j/ε⌉ − 1, with m ≤ min{n,d} − 1.Source: §5 · pp. 20–21
• The incurred additive term is ∥A − A(m)∥_F^2, the cost of moving the original points to their projection onto the first m right singular vectors.The weak triangle inequality transfers approximation bounds between distances from corresponding rows to an arbitrary solution set C.Source: §5 · p. 21
• The main reduction replaces A by A(m) for any nonempty set C contained in a j-dimensional subspace, provided m ≥ ⌈8j/ε^2⌉ − 1.Theorem 22 combines the projection approximation with the weak triangle inequality and assumes ε ∈ (0,1] and m ≤ min{n,d} − 1.Source: §5 · pp. 21–22

• The expression contains F.Source: F + dist2(AXXT, C). (9) · p. 22
• It includes the term dist2(A(m)XXT, C).Source: F + dist2(AXXT, C). (9) · p. 22
• The displayed expression continues with a trailing plus sign.Source: F + dist2(AXXT, C). (9) · p. 22

k-means

• The reduction forms A(m) by retaining only the first m singular values in the decomposition A = UΣV^T, then computes an α-approximate k-means solution on A(m).The resulting center set is used as the output for the original input A.Source: F + dist2(AXXT, C) · p. 23
• For k-means, optimizing on A(m) produces an α(1 + ε)-approximation for A, and a (1 + ε)-approximation when α = 1.Corollary 23 applies for ε ∈ (0, 1/3] and α ≥ 1.Source: F + dist2(AXXT, C) · p. 23

Affine j-subspace k-clustering

• For affine j-subspace k-clustering, the algorithm likewise retains the first m singular values in A(m) and computes an α-approximate set of k affine j-subspaces.Its input and output specification uses error parameters α and ε and returns the corresponding approximation for A.Source: F + dist2(AXXT, C) · p. 24
• The same dimensionality-reduction guarantee extends to affine j-subspace k-clustering, returning an α(1 + ε)-approximation and a (1 + ε)-approximation when α = 1.The proof is stated to be similar to the k-means corollary.Source: F + dist2(AXXT, C) · p. 24

6 Small Coresets for C-Clustering Problems

• C-clustering problems closed under rotations and reflections have dimension-independent coresets if they admit coresets in a constant number of dimensions.Each cluster set must be contained in a j-dimensional subspace.Source: §6 · pp. 24–25
• Orthogonal transformations move every candidate affine j-dimensional shape into the reduced subspace while preserving distances from the reduced data points.The construction uses an orthogonal map that fixes the data-containing subspace and maps the candidate shape into a slightly larger subspace.Source: §6 · p. 25
• The resulting construction first projects n points into an m-dimensional subspace, then builds a coreset in an (m+j)-dimensional space, yielding a coreset for the original d-dimensional problem.Closure under rotations and reflections ensures the transformed candidate remains in C, so its cost equals the original candidate’s cost.Source: §6 · p. 26
• An (ε/8)-coreset for the reduced point set in a subspace of dimension at most m+j becomes an ε-coreset for the original set in R^d.The reduction uses m = min {n, d, j + ⌈32j/ε^2⌉} −1 and a subspace containing the rows of A(m).Source: §6 · p. 26

6.1 The Sensitivity Framework

• Sensitivity sampling assigns higher probabilities to influential input objects and rescales sampled functions by reciprocal probabilities to obtain unbiased cost estimates with lower variance.Uniform sampling can miss high-influence points and therefore have high variance; sensitivity-based probabilities address this limitation.Source: §6.1 · p. 29
• The framework analyzes sensitivity sampling through range spaces and VC-dimension, while including very high-sensitivity points directly ensures coreset weights are at least their input weights.For affine j-subspace k-clustering, the total coreset weight for an unweighted n-point set is at most (1 + ε)n.Source: §6.1 · pp. 29–30
• The sensitivity framework converts nonuniform sampling into a coreset by rescaling sampled functions, with preprocessing implementable in O(|F|) time.The construction samples according to sensitivities and combines the rescaled sample with the deterministic part of the reduction.Source: §6.1 · pp. 32, 34

6.2 Bounds on the VC dimension of clustering problems

• The range space for weighted squared distances to k affine j-subspaces has VC-dimension O(jdk log k).The proof represents distances using constant-degree polynomials in O(jd) variables and applies Warren’s sign-pattern bound, extending the k=1 case through k-fold intersections.Source: §6.2 · pp. 34–35

6.3 New Coreset for k-Means Clustering

• Theorem 36 reduces k-means coreset size to independence from d by projecting onto m = O(k/ε^2) singular-vector dimensions before applying the sensitivity construction.For weighted inputs, the projection is obtained from the singular value decomposition after scaling each row by √wi; the stated computation includes O(min{nd^2, n^2d}) and O(nk^2/ε^2 log(1/δ)) terms.Source: §6.3 · p. 36

6.4 Improved Coreset for k-Line-Means

• Theorem 38 similarly gives k-line-means coresets independent of d, computable in O(nd^2) + n(kk log n log(1/δ)/ε)O(1) time.The construction projects to m = O(k/ε^2) dimensions and then applies the earlier k-line-means coreset; the preceding result uses sensitivity bounds based on projected lines and k weighted centers.Source: §6.4 · pp. 37–38

6.5 Computing Approximations Using Coresets

• Algorithm 6 combines an ε/8-coreset with an α-approximation for clustering families closed under rotations and reflections whose sets lie in j-dimensional subspaces, operating in an m+j-dimensional subspace rather than d dimensions.This applies for ε ∈ (0, 1/2], and the α-approximation is computed on the coreset, with Δ′ ignored.Source: §6.5 · pp. 38–39

7 Streaming Algorithms for Subspace Approximation and k-Means Clustering

• Merge-and-reduce combines batch coresets into a coreset for the union, enabling streaming algorithms while each input point participates in O(log n) merges.To achieve final error ε, each merge uses ε′ approximately ε/log n.Source: §7 · pp. 39–40

7.1 Streaming Algorithms for the Linear j-Subspace Problem

• The linear-subspace algorithm maintains O(j log^2 n/ε) points in O(ndj log^2 n/ε) time and outputs a coreset of size j + ⌈j/ε⌉−1.Output-Coreset computes the final coreset in O(dj^2 log^4 n/ε^2) time.Source: §7.1 · p. 40

Claim 41

• Claim 41 bounds the accumulated merge error by (1 + ε/10^h)^h ≤ 1 + ε, yielding the stated approximation guarantee for the streaming construction.The bound controls multiplicative error across h merge levels.Source: Claim 41 · p. 42

7.2 Streaming algorithms for the affine j-subspace problem

• For the affine j-subspace problem, Output-Coreset∗ computes an ε-coreset in O(dj2 log4 n/ε2) time, with size j + ⌈j/ε⌉−1.Source: §7.2 · p. 42

7.3 Streaming algorithms for k-means clustering

• The k-means streaming algorithm succeeds with probability at least 1 − δ, uses M = (k log n log(1/δ)/ε)^O(1) weighted points, and computes a (1 + O(ε))-approximation.Its overall time is nd(k log n log(1/δ)/ε)^O(1), and the final solution is obtained from the coreset in |T|^O(k/ε) time.Source: §7.3 · pp. 43–44

8.1 The Affine j-Dimensional Subspace k-Clustering Problem

• The method combines Theorem 22’s dimensionality reduction with Varadarajan and Xiao’s integer linear projective-clustering coresets, but must address that reduced coordinates need not remain integer.Any k affine j-subspaces lie in a k(j + 1)-dimensional linear subspace, motivating low-rank reduction before integer-grid processing.Source: §8.1 · pp. 44–45
• For A ∈ {−M, . . . , M}ⁿˣᵈ with rank larger than k(j + 1), every set C of k affine j-subspaces satisfies dist∞(A, C) ≥ 1/(dM)ᶜʲ, improving to 1/Mʰ⁽ʲ⁾.Source: §8.1 · p. 45

8.2 L∞-coresets

• L∞-coresets reduce maximum-distance queries to size (log(M)/ε)^f(j,k,r), with construction time (n + d) · |S|^O(1) when the input rank is r.The rank-sensitive bound follows by representing the data in a subspace containing the data and queried affine subspaces, then applying the dimension-dependent result.Source: §8.2 · p. 47

8.3 Sensitivity bounds via L∞-coresets

• L∞-coresets yield sensitivity upper bounds by recursively removing half-approximate coresets, partitioning weighted copies and computing the bounds in n · t(n) time.The construction uses a nested sequence ending with at most g(n) points; weighted implementation produces a fractional partition and computes sensitivity bounds in O(nt(n)) time.Source: §8.3 · pp. 48, 50

8.4 Bounding sensitivities by a movement argument

• A movement argument bounds a point’s sensitivity by comparing its distance to a query subspace with its movement to another point and the total weighted clustering cost.The argument is presented as a variant of Varadarajan and Xiao’s theorem [VX12b] and assumes positive total weighted distance for the reference clustering.Source: §8.4 · p. 50

8.5 Coresets for the Affine j-Dimensional k-Clustering Problem

• Theorem 51 constructs an ε-coreset for weighted affine j-dimensional k-clustering with probability at least 1 −δ, size and running time depending on j and k rather than d.The construction applies when rank(A) ≤ k(j + 1), uses time O(min(n^2d, d^2n) + n(n + d)(log M)^h(j,k)), and produces integer-coordinate points of norm at most M.Source: §8.5 · p. 51
• Theorem 52 constructs an ε-coreset with probability at least 1 −δ in time O(min(n2d, d2n) + n(n + d)(log WnM)h(j,k))), with h depending only on j and k.The input has rank greater than k(j+1), weights at least 1, maximum row norm M ≥4, and ε ∈(0, 1/2).Source: §8.5 · p. 51
• The resulting coreset preserves the input norm bound, with every selected row having norm at most M and every coreset weight at least 1.Source: §8.5 · p. 51
• The proof first projects to a low-rank approximation, then uses an optimal k(j + 1)-dimensional subspace and grid snapping to obtain sensitivity bounds without exponential dependence on 1/ε.Projection primarily controls VC-dimension, while the rank assumption supplies a positive lower bound that permits charging snapping costs.Source: §8.5 · p. 52
• Projecting the weighted points onto the subspace spanned by the first m right singular values yields a matrix whose corresponding row norms are at most M.The argument is proved for unweighted points and transfers to weighted points by reducing weights to multiplicities of points.Source: §8.5 · p. 52
• Grid snapping perturbs costs by a controlled amount, allowing Lemma 50 to bound individual sensitivities and the total sensitivity by a constant multiple of the snapped instance’s sensitivity.For the low-rank snapped instance, an L∞-(j, k)-coreset has size g(n) := (log(MnW))f(k,j), and the total sensitivity is O(log W)g(n).Source: §8.5 · pp. 52–53

Algorithmic strategy

• The method uses Theorem 51 while points remain in a k(j + 1)-dimensional subspace, then switches to Theorem 52 after establishing a lower cost bound and snapping points to a sufficiently fine grid.The first construction preserves integer coordinates; the grid perturbation is charged to the lower bound L on the optimal cost.Source: §9 · pp. 53–55

Guarantee

• Theorem 53 guarantees that algorithms 10 and 11 process n integer-coordinate points of maximum norm M with probability at least 1 −δ, producing a weighted set S and value ∆S.The stated overall running time is nd(k log(Mdn) log(1/δ)/ε)O(f(j,k)).Source: §9 · p. 54
• The maintained coreset has size (k log(Mn) log(1/δ)/ε)f(j,k), independent of the ambient dimension d in its displayed size bound.The theorem states this size together with weights and a real value ∆S.Source: §9 · p. 54

Analysis

• Conditioned on successful coreset constructions, the final error bound follows by treating grid snapping as an additional coreset construction, yielding 2h levels instead of h.The snapping grid has side length γ2L/(100d), and the constructions collectively succeed with probability at least 1 −δ.Source: §9 · pp. 55–56

10 Small Coresets for Other Dissimilarity Measures

• The alternative construction is dimension- and input-size-independent but exponentially dependent on ε^-1, and it covers a restricted Bregman k-means variant outside the earlier C-clustering formulation.Bregman divergences are asymmetric, so this construction addresses a case not covered by the previous sections.Source: §10 · p. 56

10.2 Clustering problems with nice dissimilarity measures

• Nice dissimilarity measures require polynomial-time 1-clustering, coresets for pseudo-random instances, and additive-error representations for sufficiently cheap subsets.These conditions permit errors measured relative to the full clustering cost rather than the represented subset’s own cost.Source: §10.2 · pp. 57–58

10.3 Algorithm for nice dissimilarity measures

• Recursive partitioning separates data into pseudo-random and cheap subsets, combining their representations into a coreset with size k^ν·g(k, ε/2)+h(k^ν, ε/2).The recursion reduces total 1-clustering cost geometrically; for k-means, g ≡ 1 and h(k^ν, ε)=k^ν.Source: §10.3 · pp. 58–59

10.4 Coresets for µ-similar Bregman divergences

• For pseudo-random Bregman instances, one weighted centroid with an additive correction suffices to approximate clustering costs for arbitrary center sets.This establishes g(k, f′(ε^-1)) ≡ 1 under the restricted Bregman assumptions.Source: §10.4 · p. 62
• Restricted m-similar Bregman divergences on convex, A-covering domains admit coresets whose size depends only on k and ε.The theorem applies when m ∈ (0, 1] and the divergence is defined on a convex, A-covering set.Source: §10.4 · pp. 59, 63