PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Dan Feldman, Melanie Schmidt, Christian Sohler

arXiv:1807.04518v1cs.DS

TL;DR

The paper addresses the challenge of analyzing massive, high-dimensional data with methods that reduce data size while preserving approximate analysis results. It constructs mergable coresets through dimensionality reduction and applies them across PCA, k-means, and projective clustering. For k-means and subspace approximation, coreset sizes can be independent of both input count and dimension, while projective clustering has explicit scope limitations.

  • Problem

    Existing approaches can process many records but are insufficient when Big Data also has asymptotically large dimension, motivating streamable and distributable algorithms.

  • Method

    The paper projects points into a low-dimensional space and combines this reduction with coreset constructions, producing representations whose unions remain coresets for unions of the original data.

  • Results

    The approach supports PCA, k-means, and projective clustering; for PCA it yields coreset cardinality O(j/ε), independent of input size n and dimension d.

  • Takeaways & Limitations

    Mergable coresets enable streaming and distributed analysis using local reductions, union operations, and small communication of the reduced sets.

  • Takeaways & Limitations

    Projective-clustering coresets require integral-grid inputs and have size depending polylogarithmically on grid size and n; projective-clustering coreset size is not independent of n.

Abstract

from arXiv · show

We develop and analyze a method to reduce the size of a very large set of data points in a high dimensional Euclidean space R d to a small set of weighted points such that the result of a predetermined data analysis task on the reduced set is approximately the same as that for the original point set. For example, computing the first k principal components of the reduced set will return approximately the first k principal components of the original set or computing the centers of a k-means clustering on the reduced set will return an approximation for the original set. Such a reduced set is also known as a coreset. The main new feature of our construction is that the cardinality of the reduced set is independent of the dimension d of the input space and that the sets are mergable. The latter property means that the union of two reduced sets is a reduced set for the union of the two original sets (this property has recently also been called composability, see Indyk et. al., PODS 2014). It allows us to turn our methods into streaming or distributed algorithms using standard approaches. For problems such as k-means and subspace approximation the coreset sizes are also independent of the number of input points. Our method is based on projecting the points on a low dimensional subspace and reducing the cardinality of the points inside this subspace using known methods. The proposed approach works for a wide range of data analysis techniques including k-means clustering, principal component analysis and subspace clustering. The main conceptual contribution is a new coreset definition that allows to charge costs that appear for every solution to an additive constant.

1 Introduction

The paper introduces constant-size, mergable coresets and dimensionality reduction for analyzing massive, high-dimensional data. The approach supports distributed and streaming computation while approximating tasks including PCA, k-means, and projective clustering.

  • Motivation: Existing methods handle many records but struggle when both the number of records and data dimension are large.The paper motivates algorithms that support massive streams and parallel or distributed processing.
  • Core contribution: The proposed coreset method reduces any number of items to a size depending on problem parameters and approximation quality, not input count or dimension.A coreset preserves approximate analysis results when algorithms are run on the reduced representation.
  • Core contribution: The union of two reduced data sets remains an approximation for the union of the original sets, enabling merge-and-reduce processing.This supports simple distributed and streaming workflows based on locally computed coresets and small inter-computer communication.
  • Technical results: The main dimensionality reduction maps n points in d dimensions to n points in O(j/ε2) dimensions while preserving squared distances to every j-dimensional subspace within a (1 + ε) factor.The result applies to PCA, k-means clustering, and projective clustering.
  • Technical results: For PCA and k-means queries, the paper obtains coresets with cardinality independent of both input size n and dimension d.For PCA, the stated cardinality is O(j/ε).
  • Scope and limitations: Projective-clustering coreset size is not independent of n and requires integral-grid assumptions, with dependence polylogarithmic in grid size and n.The paper also notes that some conference-version coreset sizes were incorrect and updates the results.

2 Preliminaries

The paper develops dimension- and data-size-efficient coresets and streaming methods for clustering and subspace problems. Its framework combines low-rank dimensionality reduction with a coreset definition that permits a solution-independent additive constant.

  • Coreset definition: The generalized coreset definition allows an additive constant Δ that depends on the input, ε, and solution family, but not on the particular solution.Despite this additive term, the target cost remains approximated within a multiplicative factor of 1 ± ε.
  • Coreset definition: The construction replaces the input matrix by a low-rank structured component and adds its projection cost as a constant for every clustering solution.The added constant accounts for the pseudo-random part while preserving multiplicative approximation of the desired cost.
  • Coresets and dimensionality reduction: The method represents an n-point dataset in high-dimensional space using coresets whose size is often independent of both dimension and input-set size.This is identified as the main qualitative improvement over previous results.
  • Applications and algorithms: The framework yields detailed streaming algorithms for subspace approximation, k-means, and j-dimensional subspace k-clustering.A coreset-based k-line-means algorithm is not stated explicitly because similar techniques apply and a weaker version follows from j = 1.
  • Scope and limitations: For projective clustering, an existing dimension-independent coreset construction cannot exist, so the paper uses a different approach; its projective-clustering coreset size is not independent of n.The paper also develops a separate construction independent of n and d for a restricted class of Bregman divergences.

3 Coresets for the linear j-subspace problem

The section constructs a constant-size coreset for approximating squared distances from points to every linear j-dimensional subspace. It uses a truncated SVD to separate structured and residual components, then retains only O(j/ε) rows while preserving the subspace-cost guarantee.

  • Construction: The input matrix is replaced by its rank-m approximation A(m), with m chosen to control the Frobenius-norm projection error.The construction sets m based on j and ε and uses the residual cost Δ = ∥A − A(m)∥_F^2 to account for the discarded component.
  • Construction: The residual projection cost can be added as an additive constant when approximating the cost of any j-dimensional subspace.This allows the structured approximation and the discarded component to jointly approximate the original subspace cost.
  • Coreset construction: O(j/ε) rows suffice for the linear j-subspace coreset, because only the first m rows of Σ(m)V^T are nonzero.The remaining rows contribute nothing to the relevant Frobenius-norm expression, so the coreset consists of the first m rows.
  • Guarantee: Theorem 17 guarantees that the resulting coreset approximates the squared distance to every j-dimensional linear subspace within the stated additive error Δ.Its size satisfies m ≤ j + ⌈j/ε⌉ − 1, and the coreset points are unweighted because scaling implicitly captures weighting.
  • Complexity: The construction computes an exact SVD and therefore takes O(min {nd^2, dn^2}) time.The running-time bound follows directly from exact SVD computation.

4 Coresets for the Affine j-Subspace Problem

The affine extension handles data whose mean is not the origin by centering the input, constructing a balanced coreset, and restoring the mean. It achieves a bounded-size weighted representation for every affine j-dimensional subspace.

  • Construction: The affine construction subtracts the input mean, computes a linear-subspace coreset, and adds the mean back to the coreset points.It must also ensure that the centered coreset has zero mean before restoring the original mean.
  • Construction: Doubling the centered coreset with its negation enforces zero mean, enabling the affine-distance decomposition.The paired representation has mean zero even after scaling, so Lemma 18 can be applied.
  • Weighting and scaling: The doubled coreset uses equal weights n/(2m) to match the point-count contribution of affine translations.Scaling alone would not preserve the translation-dependent term, so the construction combines weighting and scaling.
  • Guarantee: The affine coreset contains at most 2m points, where m ≤ j + ⌈j/ε⌉ − 1.Theorem 19 applies the guarantee to every affine j-dimensional subspace.
  • Guarantee: For the centered data, the construction establishes dist2(A′, L) ≤ (n/(2m))dist2(S′′, L) + Δ ≤ (1 + ε)dist2(A′, L).This bound is then transferred to affine subspaces after translating by the input mean.

5 Dimensionality Reduction for Clustering Problems under ℓ2 2-distance

The section extends dimensionality reduction from subspace approximation to clustering and shape-fitting objectives under squared Euclidean distance. It adds the projection residual as a constant and then applies existing coresets in the reduced subspace.

  • Scope: The reduction targets clustering objectives whose relevant shapes lie in a low-dimensional subspace, including k-means centers contained in a k-dimensional subspace.The method analyzes distances between the original points and their low-rank approximations before reducing the number of points.
  • Dimensionality reduction: A(m) approximates A for any low-dimensional shape when the residual cost ∥A − A(m)∥_F^2 is added to the objective.This residual equals the cost of projecting the points onto the subspace spanned by the first m right singular vectors.
  • Analysis: The weak triangle inequality bounds the difference between the original and reduced squared-distance costs using pointwise displacement and distance terms.The proof applies the inequality row by row and sums the resulting bounds over all input points.
  • Guarantee: Theorem 22 uses m ≥ ⌈8j/ε^2⌉ − 1 to obtain the dimensionality-reduction guarantee for every nonempty set contained in a j-dimensional subspace.The result combines the subspace approximation lemma with the general cost-transfer bounds.

F + dist2(AXXT, C). (9)

The displayed expression records the additive residual term and the reduced-data cost used to approximate the original clustering or shape-fitting objective.

  • Cost decomposition: The expression combines the projection residual ∥A − A(m)∥_F^2 with the cost of the projected points AXX^T to the target set C.It represents the two terms used in the dimensionality-reduction analysis.

F + dist2(AXXT, C)

The dimensionality-reduction algorithm projects the data to a lower-dimensional representation while preserving distances to low-dimensional subspaces, yielding approximate k-means and affine subspace-clustering solutions.

  • Consequences: The reduction can solve k-means and subspace-clustering problems approximately by operating on A(m) instead of A.This is stated as a consequence of the dimensionality-reduction theorem.
  • Dimensionality reduction: The algorithm replaces A with A(m), retaining only the first m singular components, where m is chosen from the approximation parameters.A(m) is formed by setting all but the first m diagonal entries of the singular-value matrix to zero.
  • k-means: For k-means, an α-approximate solution computed after dimensionality reduction becomes an α(1 + ε)-approximation for the original data.When α = 1, the resulting solution is a (1 + ε)-approximation.
  • Affine j-subspace k-clustering: For affine j-subspace k-clustering, the same reduction returns an α(1 + ε)-approximation to the optimal solution.With α = 1, the guarantee specializes to a (1 + ε)-approximation.

6 Small Coresets for C-Clustering Problems

This section develops dimension-independent coresets for rotation- and reflection-invariant C-clustering problems by projecting data to a low-dimensional subspace and transferring guarantees back to the full space. It applies this framework to k-means and k-line means while preserving useful weight and runtime properties.

  • Dimension-independent reduction: C-clustering problems closed under rotations and reflections admit coresets whose cardinality is independent of the ambient dimension when constant-dimensional coresets exist.The framework relies on the closure condition and a dimensionality-reduction theorem for an input projection A(m).
  • Dimension-independent reduction: The construction first projects A onto a low-dimensional subspace, then applies existing coreset constructions there so the reduced point set remains representative for full-dimensional centers.The projection retains n points in an m-dimensional subspace before cardinality reduction, and the orthogonal-map argument extends the guarantee beyond that subspace.
  • Dimension-independent reduction: An orthogonal transformation fixes the data-containing subspace and maps every candidate j-dimensional subspace into a bounded-dimensional subspace, preserving distances to the data.The resulting affine subspace V′ lies within L and has the same distances from every input row as V.
  • Weight guarantees: Coreset weights are guaranteed to be at least the corresponding input weights, while the total weight for unweighted affine j-subspace k-clustering is at most (1 + ε)n.The lower bound is obtained by including points with very high sensitivity approximation values directly in the coreset.
  • Applications: For k-means, the section gives probabilistic coreset constructions and a dimension-independent-size variant whose computation improves on the earlier dimension-dependent theorem.The cited theorem statements include success probability 1−δ and running-time bounds, although the supplied passages do not contain the complete displayed size expressions.
  • Applications: For k-line means, dimensionality reduction yields a coreset construction with running time O(nd^2) + n(kk log n log(1/δ)/ε)O(1), improving on the prior dimension-dependent time bound.The earlier construction has time T(d) = n · (dkk log n log(1/δ)/ε)O(1); sensitivity bounds use an approximate k-line mean and weighted-center distances.

7 Streaming Algorithms for Subspace Approximation and k-Means Clustering

The paper uses merge-and-reduce to build streaming coresets for linear and affine subspace approximation and k-means. These algorithms retain small weighted or unweighted summaries while preserving approximation guarantees with bounded time and space.

  • Streaming framework: Merge-and-reduce unions coresets from successive batches and repeatedly compresses them, enabling streaming and distributed processing.Each input point participates in O(log n) merges, so per-merge errors must be calibrated to preserve the final approximation.
  • Linear subspace approximation: The linear subspace streaming algorithm maintains O(j log^2 n/ε) points in overall time O(ndj log^2 n/ε).It is deterministic and does not require weights; an output coreset has size j + ⌈j/ε⌉−1.
  • Linear subspace approximation: The maintained linear-subspace summary approximates the squared-distance cost for every linear j-subspace within a (1 + ε) factor.The guarantee includes an additive real value carried with the summary.
  • Affine subspace approximation: The affine-subspace algorithm maintains O(j log^2 n/ε) weighted points in overall time O(ndj log^2 n/ε), then outputs a size j + ⌈j/ε⌉−1 coreset.The same framework handles affine j-subspaces by using a construction for weighted inputs.
  • k-means clustering: The streaming k-means algorithm maintains a weighted coreset of size (k log n log(1/δ)/ε)^O(1) with probability at least 1 − δ.From this summary, a (1 + O(ε))-approximation can be computed in |T|^O(k/ε) time, with randomized coreset calls controlling cumulative failure probability.

8 Coresets for Affine j-Dimensional Subspace k-Clustering

For affine j-dimensional k-clustering, the paper combines dimensionality reduction with sensitivity-based coreset construction. Integer-coordinate constraints require grid snapping and rank-dependent lower bounds to control the resulting error.

  • Construction: The construction combines dimensionality reduction from Theorem 22 with Varadarajan and Xiao’s sensitivity-based coresets for integer projective clustering.The sensitivity framework represents each point’s squared distance to candidate subspace unions as a function over the solution family.
  • Construction: Projecting integer data to a lower-dimensional space can destroy integer coordinates, preventing direct use of integer projective-clustering algorithms.The paper addresses this by projecting, snapping to a sufficiently fine grid, and charging snapping cost against a rank-based lower bound.
  • Rank conditions: If the input rank exceeds k(j + 1), Lemma 45 supplies a positive lower bound on the L∞ cost to any set of k affine j-subspaces.This prevents the data from being completely covered and supports the error analysis for grid snapping.
  • Results: The resulting integer-input coreset has size and construction time governed by functions of j, k, ε, δ, M, and total weight, rather than the ambient dimension alone.Theorem 51 covers rank at most k(j + 1), while Theorems 52 and the associated result address the higher-rank setting with bounded integer coordinates.

9 Streaming Algorithms for Affine j-Dimensional Subspace k-Clustering

The affine subspace clustering streaming algorithms adapt merge-and-reduce to integer-coordinate inputs by splitting low-rank and higher-rank cases. They maintain compact weighted summaries with high-probability guarantees while controlling snapping and repeated-compression errors.

  • Algorithm design: The streaming method splits into two cases because recursively reduced coresets need integer coordinates, but dimensionality reduction generally produces non-integer points.One algorithm handles inputs contained in a k(j + 1)-dimensional subspace; the other uses a lower bound on the optimal cost and grid snapping.
  • Algorithm design: The streaming procedures invoke subspace coreset construction when batches reach twice the relevant coreset-size threshold, then merge summaries and their weights.The pseudocode distinguishes whether the batch or merged summary lies in a k(j + 1)-dimensional subspace.
  • Guarantees: The algorithms maintain a weighted set of (k log(Mdn) log(1/δ)/ε)^f(j,k) points with probability at least 1 − δ.The overall running time is nd(k log(Mdn) log(1/δ)/ε)^O(f(j,k)).
  • Higher-rank case: For higher-rank inputs, points are snapped to a grid with side length γ^2 · L/(100d), where L is a lower bound on the optimal cost.The rank condition supplies the lower bound needed to charge the snapping error.
  • Guarantees: Repeated coreset constructions use failure probability δ/j^2 at the jth call, ensuring that all constructions succeed with probability at least 1 − δ.The error analysis treats snapping as an additional coreset level, yielding 2h levels instead of h.

10 Small Coresets for Other Dissimilarity Measures

This section defines “nice” dissimilarities through two coreset-producing conditions and uses them to derive constant-size constructions, including for restricted Bregman divergences.

  • Definition of nice dissimilarities: A nice dissimilarity permits polynomial-time computation of the one-center optimum and satisfies two conditions covering pseudo-random sets and negligible-cost subsets.The first condition yields a small coreset when k-clustering is close to one-clustering; the second approximates a cheap subset with additive error.
  • Recursive construction: The recursive algorithm partitions the input into subsets that are either cheap or pseudo-random, then applies the corresponding coreset routines.The exposition assumes optimal clustering for simplicity, but the algorithm also works with an approximation algorithm.
  • Error analysis: 2ε optk(A) is the combined error before replacing ε by ε/2, yielding an ε-coreset for the full input.Pseudo-random subsets contribute one error term and cheap subsets contribute another.
  • Size bounds: A coreset of size k^ν · g(k, ε/2) + h(k^ν, ε/2) exists for ν = ⌈log_(1+f1(ε/2))(1/f3(ε/2))⌉.For k-means, g ≡ 1 and h(k^ν, ε) = k^ν, giving an overall size of 2k^log_(1+f1(ε))(1/f3(ε)).
  • Bregman divergences: For m-similar Bregman divergences on convex A-covering sets, a constant-size coreset exists, with size depending only on k and ε.Pseudo-random sets can be represented by their centroid with its weight and an additive correction, so g ≡ 1.
Loading 1807.04518v1…