PaperlayerView exact revision on arXiv

Source-linked AI summary

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu

arXiv:1410.6801v3cs.DScs.LG

TL;DR

The paper asks how to reduce matrix dimensionality while preserving the quality of constrained k-rank approximation, including k-means and low rank approximation. It introduces projection-cost preserving sketches and analyzes SVD, random projection, and column-selection constructions. The results give (1 + ε) guarantees with O(k)-scale sketches and a (9 + ε) k-means approximation in O(log k/ε^2) dimensions.

  • Problem

    The paper addresses how to generically accelerate k-means and low rank approximation by reducing data points to sketches with many fewer columns while retaining approximate optimality.

  • Method

    The paper uses projection-cost preserving sketches built from approximate SVD, Johnson-Lindenstrauss random projection, and column selection.

  • Results

    The methods achieve (1 + ε) relative-error sketches for the covered approximation problems, while k-means admits a (9 + ε) approximation in O(log k/ε^2) dimensions.

  • Takeaways & Limitations

    The sketches can generically accelerate exact, approximate, or heuristic algorithms for k-means and low rank approximation, with applications to streaming and distributed computation.

  • Takeaways & Limitations

    Improving the (9 + ε) k-means guarantee for random projection to O(log k/ε^2) dimensions remains an open question.

Abstract

from arXiv · show

We show how to approximate a data matrix $\mathbf{A}$ with a much smaller sketch $\mathbf{\tilde A}$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+ε)$ error. Importantly, this class of problems includes $k$-means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just $O(k)$ dimensions, our methods generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For $k$-means dimensionality reduction, we provide $(1+ε)$ relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only `cover' a good subspace for $\bv{A}$, but can be used directly to compute this subspace. Finally, for $k$-means clustering, we show how to achieve a $(9+ε)$ approximation by Johnson-Lindenstrauss projecting data points to just $O(\log k/ε^2)$ dimensions. This gives the first result that leverages the specific structure of $k$-means to achieve dimension independent of input size and sublinear in $k$.

1 Introduction

The paper develops projection-cost preserving sketches that reduce dimensionality while approximately preserving constrained k-rank approximation costs, including k-means and low rank approximation. It provides relative-error constructions using SVD, random projection, and feature selection, plus a lower-dimensional constant-factor result specific to k-means.

  • Problem scope: The framework covers k-means clustering, unconstrained low rank approximation, and related constrained problems.The paper explicitly treats k-means and principal component analysis as instances of constrained k-rank approximation.
  • Core framework: Projection-cost preserving sketches approximate the cost of every k-dimensional projection, enabling approximate optimization on a smaller matrix.The guarantee includes a fixed additive constant independent of the chosen subspace.
  • Dimensionality Reduction Results: ⌈k/ε⌉ dimensions suffice for projection-cost preserving SVD sketches, and nearly optimal singular vectors can replace an exact partial SVD.The latter result supports fast approximate SVD methods and can use fewer dimensions when the spectrum is nonuniform.
  • Dimensionality Reduction Results: (1 + ε) error is achieved by random projection to O(k/ε^2) dimensions, sampling O(k log k/ε^2) columns, or selecting O(k/ε^2) columns with BSS.These methods improve on earlier constant-factor bounds.
  • Dimensionality Reduction Results: Random projection also yields an oblivious approach for unconstrained SVD and a non-oblivious O(k/ε)-row method for constrained k-rank approximation.The paper notes applications of the oblivious approach to streaming and a low-communication distributed k-means algorithm.
  • Dimensionality Reduction Results: (9 + ε) approximation for k-means is obtained by projecting to O(log k/ε^2) dimensions, independent of input size and sublinear in k.For general constrained k-rank approximation, the paper states that dimension below Θ(k) is impossible.

2 Preliminaries

The preliminaries define the matrix approximation and projection notation used throughout, then formulate k-means as a constrained low rank approximation problem. In this formulation, cluster indicator matrices produce rank-k orthogonal projections approximating the data columns.

  • Linear Algebra Basics: A singular value decomposition writes A as UΣV⊤, with singular values ordered from largest to smallest and pseudoinverse A+ = VΣ^-1U⊤.U and V contain orthogonal left and right singular vectors, while Σ contains positive singular values.
  • Linear Algebra Basics: The truncated SVD A_k is the closest rank-k approximation to A under any unitarily invariant norm.The residual A − A_k is denoted A_r\k.
  • Linear Algebra Basics: Multiplying by an orthogonal projection cannot increase the Frobenius norm, following spectral submultiplicativity.The Frobenius norm also obeys ∥MN∥_F ≤ ∥M∥_F∥N∥_2 and ∥MN∥_F ≤ ∥N∥_F∥M∥_2.
  • Constrained Low Rank Approximation: When all rank-k orthogonal projections are allowed, minimizing projection cost is equivalent to optimal rank-k approximation solved by the top left singular vectors.The optimal projection is P* = U_kU_k⊤.
  • k-Means Clustering: k-means partitions rows into k clusters and minimizes squared distances from each vector to its assigned centroid.Cluster indicator matrices encode assignments and normalized cluster membership.
  • k-Means Clustering: k-means is a constrained low rank approximation problem because X_CX_C⊤ is a rank-k orthogonal projection restricted to cluster indicator matrices.The resulting projection approximates columns of A, although the original objective is expressed through row-to-centroid distances.

3 Projection-Cost Preserving Sketches

The paper introduces projection-cost preserving sketches as a general sufficient condition for solving constrained low rank approximation on a reduced matrix. Approximate optimization on the sketch then transfers to approximate optimization on the original matrix.

  • Definition: The same framework applies to constrained problems because the allowed projection family is a subset of all rank-k projections.This makes preserving costs for all rank-k projections stronger than necessary but sufficient for constrained optimization.
  • Definition: A sketch is projection-cost preserving when its costs for all rank-k projections approximate those of A up to multiplicative error and a projection-independent constant.The definition considers every rank-k orthogonal projection.
  • Definition: One-sided projection-cost preservation provides a tighter guarantee needed by sketching results without constant factors in the sketch size.The paper distinguishes this from the two-sided definition.
  • Application to Constrained Low Rank Approximation: If a sketch preserves projection costs and a projection is approximately optimal for the sketch, that projection is approximately optimal for the original matrix.The result applies to any set of rank-k orthogonal projections and approximation factor γ ≥ 1.
  • Application to Constrained Low Rank Approximation: The proof combines projection-cost preservation inequalities with the sketch’s approximate optimization guarantee to transfer the bound from the sketch to A.The one-sided variant uses the corresponding one-sided error inequality.

4 Sufficient Conditions

The section characterizes projection-cost preserving sketches through structured error matrices in the covariance approximation ˜A˜A⊤ ≈ AA⊤. One-sided and two-sided guarantees follow from increasingly general spectral, trace, and subspace conditions.

  • General approach: Linear sketches write ˜A = AR, with SVD, Johnson–Lindenstrauss, and column-selection sketches represented by different matrices R.For sketch dimension m = O(k), R is respectively a truncated right-singular-vector matrix, a random projection, or a sparse diagonal selector.
  • Error characterization: Projection-cost preservation analyzes the error E = ˜A˜A⊤ − AA⊤ rather than ˜A directly.The covariance matrices C = AA⊤ and ˜C = ˜A˜A⊤ determine the projection costs.
  • One-sided guarantees: One-sided error suffices when E is symmetric, negative semidefinite, and its largest k eigenvalues have bounded total magnitude.These restrictions control projection-dependent error relative to the residual low-rank approximation cost.
  • Implications: The framework supports exact or approximate low-rank sketches, while other sketching methods require the broader four-component error analysis.This establishes sufficient conditions for constrained low-rank approximation sketches.
  • Two-sided guarantees: Two-sided error permits ˜C = C + E1 + E2 + E3 + E4 when the error components satisfy separate spectral, trace, and subspace-span bounds.The componentwise tolerances combine as ǫ1 + ǫ2 + ǫ′2 + ǫ3 + ǫ4 = ǫ.

5 Singular Value Decomposition

The section shows that truncated or approximate singular-vector sketches preserve projection costs with dimension about k/ǫ, including sketches derived from general low-rank approximations. It also identifies when fewer singular vectors suffice.

  • Exact SVD: ⌈k/ǫ⌉ singular vectors improve on the previously stated O(k/ǫ2) requirement, and this dimension is tight in general.The result follows by recognizing k-means as a constrained low-rank approximation problem.
  • Exact SVD: m = ⌈k/ǫ⌉ top singular vectors yield a projection-cost preserving sketch with one-sided error.The sketch can be represented as UmΣm = AVm, reducing data-point dimension to m.
  • Adaptive dimension: A smaller m can suffice when A’s spectrum decays, because the relevant residual condition may hold before ⌈k/ǫ⌉ singular vectors are retained.The condition can be checked by iteratively computing singular values.
  • Approximate SVD: Approximate top singular vectors also suffice for projection-cost preservation when they provide a nearly optimal rank-m approximation.This permits faster approximate truncated SVD algorithms, including Krylov-subspace and randomized methods.
  • General low-rank approximation: A general rank-m low-rank approximation ˜A, even without the form AZZ⊤, satisfies the two-sided projection-cost guarantee when its approximation error meets the theorem’s bound.A factorization ˜A = LDW⊤ allows LD to serve as the smaller data matrix for k-means or related constrained problems.

6 Reduction to Spectral Norm Matrix Approximation

The section reduces column-selection and random-projection analyses to spectral-norm approximation by decomposing A into structured orthogonal components. A matrix B then transfers approximation guarantees into the error conditions for projection-cost preservation.

  • Reduction framework: Column-selection and random-projection sketches have the linear form ˜A = AR, where R selects and reweights columns or applies a Johnson–Lindenstrauss projection.The analysis constructs an auxiliary matrix B to connect these sketches with spectral approximation.
  • Auxiliary matrix: m ≤ 2k and a suitable orthonormal Z allow construction of B whose spectral and Frobenius properties support the reduction.The resulting B satisfies bounds including ∥BB⊤∥2 between 1 and 2 and tr(BB⊤) ≤ 3k.
  • Error decomposition: The decomposition A = W1B + W2B separates the approximated low-rank component from the residual and enables expansion of ˜C − C into admissible error terms.Each term is matched to one of the four conditions in the two-sided characterization.
  • Error decomposition: Spectral approximation of B transfers to the sketch ˜A = AR, which satisfies the projection-cost preserving conditions.The proof bounds the four error components separately before combining them.
  • Guarantee: 6ǫ is the resulting error guarantee for the reduction in Lemma 10.This follows from the stated conditions on Z, B, and the spectral approximation of BRR⊤B⊤.

7 Random Projection and Feature Selection

The paper constructs projection-cost preserving sketches through random projections, column sampling, deterministic selection, and approximate SVD, enabling (1+ε) relative-error solutions for constrained k-rank approximation.

  • Sketching framework: Projection-cost preserving sketches reduce constrained k-rank approximation to preserving projection costs, using subspace embedding and trace-preservation guarantees.This framework includes k-means and related low-rank problems.
  • Random projection: Theorem 12 shows that random projections produce rank-k projection-cost preserving sketches with error O(ε) with probability at least 1−O(δ).The result applies to the first three Johnson–Lindenstrauss matrix families.
  • Random projection: O(k/ε^2) dimensions suffice for dense Johnson–Lindenstrauss projections, while fully sparse projections use O(k^2/ε^2) dimensions and can be faster on sparse data.A third family trades output dimension against computational cost.
  • Column sampling: O(k log(k/δ)/ε^2) reweighted columns yield a projection-cost preserving sketch with error ε under the stated approximate-basis condition.The algorithm runs in O(nnz(A) log(d/δ) + kd log(d/δ)) time.
  • Deterministic column selection: O(k/ε^2) reweighted columns suffice for deterministic BSS-based feature selection, with success probability at least 1−δ.The stated runtime is O(nnz(A) log(d/δ)+poly(k, ε, log(1/δ))d).

8 Non-Oblivious Random Projection

The non-oblivious approach first projects the data to a random subspace dependent on the input, then uses its row span to construct a projection-cost preserving sketch with controlled dimension.

  • Construction: The method left-multiplies A by a Johnson–Lindenstrauss matrix with O(k/ε) rows, then projects A onto the resulting row span.The random subspace depends on A’s rows, making the projection non-oblivious.
  • Guarantee: Theorem 16 guarantees a projection-cost preserving sketch with error ε with probability 1−δ using a rank-k′ approximation where k′=O(k/ε).The construction uses one of the first three Johnson–Lindenstrauss distributions.
  • Dimension: A dense Johnson–Lindenstrauss construction reduces A to O(k/ε + log(1/δ)) dimensions.The resulting sketch is AZ, where Z spans the rows of the reduced data.
  • Analysis: The analysis requires an approximate SVD with a spectral-norm guarantee, plus a small additive Frobenius-norm error.The paper supplies this extension in Appendix C.

9 Constant Factor Approximation with O(log k) Dimensions

Exploiting the fact that an optimal k-means clustering has only k centers, the paper uses Johnson–Lindenstrauss projection to obtain a constant-factor approximation in logarithmic dimension.

  • Main result: O(log(k/δ)/ε^2) projected dimensions suffice for a (9+ε)-approximation to k-means.The projection is A R^⊤ for a Johnson–Lindenstrauss matrix.
  • Significance: The result is dimension independent of input size and sublinear in k, unlike the general constrained k-rank approximation setting.The paper identifies this as the first constant-factor result with that dimensionality dependence.
  • Scope boundary: Projecting below k dimensions cannot solve general constrained k-rank approximation because the sketch may not retain rank k.The identity-matrix example shows that SVD and column selection can merge zero rows and incur positive original cost.
  • Mechanism: The analysis replaces every row by its optimal cluster center, producing only k distinct rows whose pairwise squared distances are preserved by the projection.Preserving these center distances preserves the cost of any clustering of the projected data.

10 Applications to Streaming and Distributed Algorithms

The sketches accelerate streaming and distributed k-means algorithms by reducing dimension before optimization, with streaming space and distributed communication guarantees stated in the paper.

  • Coresets: The paper’s relative-error sketches use ⌈k/ε⌉ dimensions, while constant-error k-means sketches use O(log k) dimensions, reducing dimension-dependent coreset sizes.The paper identifies these as the smallest known constructions in the stated setting.
  • Streaming: Applying the random-projection result to unconstrained k-rank approximation uses ˜O(dk/ε^2) words and ˜O(log k log n) bits in the general turnstile streaming model.The approach uses a single pass and nearly matches the lower bound for the more restrictive row-wise model.
  • Distributed k-means: The distributed method communicates a shared Johnson–Lindenstrauss matrix specification, avoiding the distributed PCA preprocessing step.Servers independently project their local rows before running the clustering algorithm.
  • Distributed k-means: The dimension can be reduced from O(k/ε^2) to O(k/ε) using the non-oblivious random projection technique.The paper notes this can further improve communication complexity.
  • Distributed k-means: Distributed k-means can achieve a (1+ε)γ-approximation with communication ˜O(s log d log k) bits.This assumes rows are partitioned across s servers and a centralized γ-approximate clustering algorithm is available.

11 Open Questions

The paper identifies two open directions: improving the random-projection k-means guarantee and developing iterative sampling-based low-rank approximation.

  • Random projection: Improving the (9 + ε) k-means approximation achieved by random projection to O(log k/ε^2) dimensions remains an open question.The paper explicitly asks whether this guarantee can be improved.
  • Column sampling: An open question is whether column-sampling results can iteratively refine coarse approximate SVDs or sampling probabilities into relative-error low-rank approximations.Such a method could require exact SVDs only on small column samples, potentially benefiting sparse or structured matrices.

A Matching Lower Bound for SVD Based Reduction

The paper proves a matching lower bound for SVD-based dimensionality reduction by constructing a matrix combining a simplex with a Gaussian cloud. With m = ⌈k/ε⌉ dimensions, the construction shows that fewer SVD dimensions cannot generally preserve the k-means objective within (1 + ε).

  • Lower-bound statement: ⌈k/ε⌉ dimensions are necessary for SVD-based reduction to approximate the k-means objective within (1 + ε).The lower bound also applies to all constrained low-rank approximation problems because k-means is a special case.
  • Proof strategy: The projected construction collapses the simplex vertices together while retaining the Gaussian cloud, forcing a k-means clustering whose cost is large relative to the optimal cost before projection.The proof compares the clustering projection that separates the simplex with the projected instance where the simplex points coincide.
  • Construction: The hard instance uses d = ⌈k/ε⌉ + k −1 dimensions, with a simplex in k −1 dimensions and a Gaussian cloud in the remaining m = ⌈k/ε⌉ dimensions.The Gaussian vectors form a cloud that naturally clusters with one center.
  • Construction: The Gaussian cloud is analyzed through two high-probability properties: a lower bound on its smallest singular value and a one-cluster-versus-k-cluster cost relation.These properties support the separation between the simplex structure and the cloud contribution.
  • Proof strategy: For Gaussian clusters, the proof bounds centroid gains using one-dimensional Gaussian tail estimates and a 1-net over the sphere.The resulting total gain is bounded by a term proportional to log(k), while the original cloud cost is about m = k/ε.

B Approximate SVD and General Low Rank Approximation

The paper extends projection-cost preserving sketches from exact SVDs to approximate SVDs and general low-rank approximations. With m = ⌈k/ε⌉, suitable approximate rank-m representations still preserve projection costs, including spectral-norm variants obtained through random sketches.

  • Approximate SVD: The section extends SVD-sketch analysis to cases where only an approximate SVD or general low-rank approximation of A is available.The goal is to preserve the projection-cost guarantees without requiring an exact SVD.
  • Approximate SVD: m = ⌈k/ε⌉ dimensions suffice when an orthonormal matrix Z provides an appropriate rank-m approximation AZZ⊤ to A.The resulting sketch satisfies the projection-cost-preserving conditions for every rank-k orthogonal projection.
  • Proof approach: The approximate-SVD guarantee is established by combining projection identities, SVD optimality, and Pythagorean decompositions.The proof applies the approximate SVD requirement to bound the reconstruction error before deriving the projection-cost relation.
  • Proof approach: The proof decomposes an approximate low-rank sketch into its projected component and a remainder, then controls the remainder using Frobenius norms, orthogonality, and the triangle inequality.The analysis explicitly relies on the small Frobenius norm of the remainder matrix.
  • Spectral-norm analysis: The analysis extends to sketches whose covariance error decomposes into four terms with separate spectral or span conditions.The total error is controlled when ε is at least ε1 + ε2 + ε3 + ε4.
  • Spectral-norm analysis: Random matrix families with error O(ε) produce rank-k spectral-norm projection-cost-preserving sketches with error ε, with probability at least 1 − O(δ).The guarantee applies to any matrix A and any rank-k orthogonal projection P.
  • Spectral-norm analysis: The resulting approximation guarantee is comparable to guarantees obtained by other techniques for constrained low-rank approximation.The comparison is made with methods cited as HMT11 and BJS15.
Loading 1410.6801v3…