PaperlayerView exact revision on arXiv

Source-linked AI summary

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering

Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn

arXiv:1811.03195v2cs.DScs.LG

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.

    Source: §1 · p. 3, §1.1 · p. 4

  • 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.

    Source: §1 · pp. 2–3

  • 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.

    Source: §1 · p. 2

  • 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.

    Source: §1 · p. 3

    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.

    Source: §1 · pp. 2–3

Abstract

from arXiv · show

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.Source: §1 · pp. 1, 3, 4
  • 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.Source: §1 · p. 2
  • 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.Source: §1 · pp. 2–3
  • 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.Source: §1 · p. 2
  • 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.Source: §1 · p. 3
  • 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.Source: §1 · pp. 2, 4

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.Source: §2 · p. 7

Dimension reduction

  • A random map is an (ε, δ)-dimension reduction when it preserves every pairwise distance within factor 1 + ε with probability at least 1 − δ.Source: §2 · p. 7
  • 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.Source: §2 · p. 7

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.Source: §3 · p. 7

Combinatorial reduction

  • Theorem 3.2 extracts an everywhere-sparse subgraph from a random distortion graph under only per-edge probability bounds.Source: §3.1 · p. 8

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))).Source: §3.1 · p. 8, §3.2 · p. 8

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.Source: §3.3 · pp. 11–12
  • Theorem 3.6 gives, with probability at least 1 − α, (1 − ε) cost_p C ≤ cost_p π(C) ≤ (1 + ε) cost_p C for every clustering C.Source: §3.3 · p. 12

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.Source: §4.1 · pp. 12, 14
  • For V0 = V \ R, every subset S ⊂ V0 satisfies |S| ≤ μ(S)|V0|.Source: §4.1 · p. 14

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.Source: §4.2 · pp. 14–15
  • The construction bounds the removed fraction using the measure estimates and the assumptions on θ, β, M, and δ.Source: §4.2 · p. 15

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.Source: §5 · p. 16

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θ/ε.Source: §5 · p. 16

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).Source: §5 · p. 16
  • The proof chooses ε = θ^(1/(p+1)), transfers an optimal center, and averages pointwise bounds over non-neighboring points.Source: §5 · pp. 16–17

Proof mechanism

  • A minimax argument selects a lifted center for which fewer than θ′(ε)|X| points violate the desired distance bound.Source: §5.1 · pp. 18, 19, 21

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

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

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

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.Source: D Fast dimension reduction · p. 26
  • 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.Source: D Fast dimension reduction · p. 26
  • The proof analyzes the subsampled transform through conditional independence, symmetrization, Khintchine’s inequality, and Cauchy–Schwarz.Source: D Fast dimension reduction · pp. 26–27
  • 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.Source: D Fast dimension reduction · pp. 29–31
  • Combining the fast-map bounds with the main theorem yields the final dimension bound for the clustering result.Source: D Fast dimension reduction · p. 31

Related papers

Loading 1811.03195v2…