Source-linked AI summary
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
TL;DR
The paper addresses whether data-oblivious dimension reduction can preserve Euclidean k-clustering costs with dimension depending mainly on k rather than dataset size. It proves simultaneous 1+ε preservation for all clusterings under broad random-map conditions, with an essentially optimal dimension bound and implications for approximate solutions.
Problem
For p ≠ 2, and especially k-medians, prior work did not establish a logarithmic-in-dataset-size dimension bound, while preserving all clusterings requires controlling exponentially many partitions.
Method
The paper analyzes random dimension-reduction maps satisfying a sub-Gaussian-tail or slightly more general standard-map condition and proves a simultaneous guarantee over all partitions.
Results
O(log(k/ε)/ε^2) dimensions preserve optimal and every clustering cost within 1+ε, and the result applies to orthogonal, Gaussian, and sub-Gaussian-tailed maps.
Takeaways & Limitations
Solving the reduced k-clustering instance with approximation λ yields a (1+O(ε))·λ approximation for the original instance, while the dimension bound is nearly optimal.
Takeaways & Limitations
The guarantee assumes a random map satisfying the theorem’s standard dimension-reduction and sub-Gaussian-tail conditions; the nearly optimal lower bound also identifies unavoidable dimension requirements.
Abstract
from arXiv · showhide
Consider an instance of Euclidean $k$-means or $k$-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of $(1+\varepsilon)$ under a projection onto a random $O(\log(k / \varepsilon) / \varepsilon^2)$-dimensional subspace. Further, the cost of every clustering is preserved within $(1+\varepsilon)$. More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean $k$-clustering with the distances raised to the $p$-th power for any constant $p$. For $k$-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for $k$-medians, it answers a question raised by Kannan.
1 Introduction
The paper studies data-oblivious dimension reduction for Euclidean k-clustering and proves that clustering costs remain accurate in substantially fewer dimensions. Its guarantees cover all partitions, broad classes of random maps, and p-powered distances, while improving prior bounds and nearly matching lower bounds.
- The framework covers Euclidean k-clustering with distances raised to the p-th power, including k-medians and k-means.Before this work, even an O(log n) bound was unknown for p ≠ 2, and the k-median question was explicitly posed by Kannan.
- O(log(k/ε)/ε^2) dimensions preserve Euclidean k-clustering cost within a factor of 1+ε.The guarantee applies to projections into a target space whose dimension depends logarithmically on k/ε rather than on n.
- The result applies to orthogonal, Gaussian, and any dimension-reduction maps satisfying the sub-Gaussian-tail condition.A slightly more general standard dimension-reduction condition also suffices.
- Every clustering’s cost is preserved within a factor of 1+ε with high probability under the stated random-map conditions.The formal theorem quantifies this simultaneously over all partitions of a finite dataset.
- The dimension bound is nearly optimal: preserving all k-clusterings requires at least Ω(log k/ε^2) dimensions for any dimension-reduction map.For Gaussian maps, the same lower bound applies even when preserving only the optimal clustering.
- The result improves prior k-means guarantees by achieving O(log(k/ε)/ε^2) dimensions with distortion 1+ε and resolves an open problem.Earlier bounds traded O(k/ε^2) dimensions for 1+ε distortion or O(log k/ε^2) dimensions for 9+ε distortion.
2 Preliminaries
The paper formulates Euclidean k-clustering with an ℓp objective and studies data-oblivious random dimension reductions that approximately preserve distances and clustering costs.
- Problem formulation: The optimal point assigned to each cluster is called its center, and the total clustering cost sums the costs of all clusters.
- Dimension reduction: A random map is an (ε, δ)-dimension reduction when it preserves every pairwise distance within factor 1 + ε with probability at least 1 − δ.
- Dimension reduction: The paper studies data-oblivious reductions whose map distribution is independent of the input point set.Known constructions include random-subspace projections and Gaussian or sub-Gaussian random matrices.
3 Dimension reduction preserves cluster costs
This section develops the main preservation theorem: under suitable random dimension reductions, every clustering’s ℓp cost is preserved with high probability, using a sparse distortion structure and deterministic cost-preservation results.
- Proof strategy: The proof reduces the main theorem to two statements: every clustering’s cost does not increase substantially under projection, and the reverse inequality also holds.
- Combinatorial reduction: Theorem 3.2 extracts an everywhere-sparse subgraph from a random distortion graph under only per-edge probability bounds.
- Deterministic cost preservation: Theorem 3.3 converts sparsity of the distortion graph into approximate preservation of cluster costs for every p ≥ 1.Its distortion factor is D = (1 + ε)^p(1 + 3p+2θ^(1/(p+1))).
- Main guarantee: The theorem applies to standard random dimension-reduction maps, with parameters chosen to control distortion, failure probability, and tail behavior.The proof invokes Theorem 3.5 and the standard-map conditions to obtain the stated event simultaneously for all clusterings.
- Main guarantee: Theorem 3.6 gives, with probability at least 1 − α, (1 − ε) cost_p C ≤ cost_p π(C) ≤ (1 + ε) cost_p C for every clustering C.
4 Everywhere sparse subgraph
The section proves that a random distortion graph contains a large induced subset with uniformly sparse degrees, enabling later geometric cost-preservation arguments.
- Random subset lemma: A random subset lemma removes a controlled exceptional set R while providing a deterministic measure μ that lower-bounds the mass of every retained point.
- Random subset lemma: For V0 = V \ R, every subset S ⊂ V0 satisfies |S| ≤ μ(S)|V0|.
- Sparse subgraph construction: The proof separates cases according to whether the bad-edge mass is large and removes bad vertices when necessary to obtain everywhere sparsity.
- Sparse subgraph construction: The construction bounds the removed fraction using the measure estimates and the assumptions on θ, β, M, and δ.
5 One point extension
The section establishes a robust one-point extension theorem: if a map expands distances only on a uniformly sparse set of pairs, centers can be transferred while preserving most point-to-center distances.
- Distance expansion graph: The distance expansion graph connects pairs whose mapped distance exceeds their original Euclidean distance.
- Robust extension: Theorem 5.2 extends a map between finite Euclidean point sets so that, for all but a θ′(ε) fraction of points, distances to any chosen point are preserved within factor 1 + ε.The exceptional fraction is θ′(ε) = 2(1 + ε)^2θ/ε.
- Cost preservation: Lemma 5.3 uses the extension theorem to show that a θ-everywhere-sparse distortion graph preserves cluster cost for every p ≥ 1.The sparsity requirement is θ ≤ 1/10^(p+1).
- Cost preservation: The proof chooses ε = θ^(1/(p+1)), transfers an optimal center, and averages pointwise bounds over non-neighboring points.
- Proof mechanism: A minimax argument selects a lifted center for which fewer than θ′(ε)|X| points violate the desired distance bound.
A Inequality for the sum of p-th powers
This section derives an inequality for sums of p-th powers using convexity and Jensen’s inequality, then states a relaxed triangle inequality for vectors.
- A Inequality for the sum of p-th powers: Jensen’s inequality is applied after expressing the relevant quantity as a convex combination.The convex-combination terms sum to 1.
- A Inequality for the sum of p-th powers: The resulting relaxed triangle inequality applies to arbitrary vectors for ε > 0 and p ≥ 1.
- A Inequality for the sum of p-th powers: ε = 1 and p = 2 yields the inequality used for Item 2.
B Closed-form expression for the cost of a cluster
The cluster-cost formula identifies the optimal center as the weighted center of mass and expresses the k-means cost through variance and an independent-pair expectation.
- B Closed-form expression for the cost of a cluster: The optimal center of a weighted cluster is its center of mass.For independent draws a and b from the cluster’s weight distribution, the cost equals Var[a].
C Sub-Gaussian Tailed Dimension Reduction
This section establishes that sub-Gaussian-tailed dimension reductions are standard and verifies that Gaussian projections satisfy the required tail condition.
- C Sub-Gaussian Tailed Dimension Reduction: Sub-Gaussian-tailed maps satisfying the dimension-reduction theorem are standard dimension reductions.
- C Sub-Gaussian Tailed Dimension Reduction: The proof controls norm deviations using a sub-Gaussian tail bound and requires d ≥ c(p − 1)/ε^2.The argument bounds the contribution from deviations above ε through an expectation involving (1 + ξ)^p.
- C Sub-Gaussian Tailed Dimension Reduction: A Gaussian projection is defined by a matrix with independent N(0,1) entries and is sub-Gaussian tailed.
- C Sub-Gaussian Tailed Dimension Reduction: For a unit vector, the Gaussian norm analysis uses a chi-square distribution with d degrees of freedom.
D Fast dimension reduction
This section develops a fast dimension-reduction map based on randomized sign flips, a Hadamard transform, and subsampling, then shows that it preserves the paper’s clustering guarantees with adjusted parameters.
- D Fast dimension reduction: The fast map can be applied in O(m log m) time while retaining the conclusion of Theorem 1.3 with modified parameters.
- D Fast dimension reduction: The construction uses a random sign diagonal matrix, a normalized Hadamard transform, and a diagonal subsampling matrix.Padding allows the input dimension m to be treated as a power of two.
- D Fast dimension reduction: The proof analyzes the subsampled transform through conditional independence, symmetrization, Khintchine’s inequality, and Cauchy–Schwarz.
- D Fast dimension reduction: The resulting map is an (ε, δ)-dimension reduction under a stated lower bound on d, with additional conditions for the stronger tail guarantee.The stronger guarantee uses δ ≤ ε and d much larger than p^2.
- D Fast dimension reduction: Combining the fast-map bounds with the main theorem yields the final dimension bound for the clustering result.