# Approximation and Streaming Algorithms for Projective Clustering via Random Projections

arXiv: https://arxiv.org/abs/1407.2063 · HTML: https://mlsanity.com/paper/1407.2063/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2014.

## Built on by (most cited first, 4 of 4)

- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Robust and Provable Guarantees for Sparse Random Embeddings](https://mlsanity.com/paper/2202.10815/) (2022)
- [Compress to Impress: Efficient LLM Adaptation Using a Single Gradient Step on 100 Samples](https://mlsanity.com/paper/2510.20800/) (2025)
- [Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning](https://mlsanity.com/paper/2301.02870/) (2023)

## Abstract (arXiv)

Let P be a set of n points in ℝd. In the projective clustering problem, given k, q and norm ρ ∈ [1,∞], we have to compute a set F of k q-dimensional flats such that (sump∈ Pd(p, F)ρ)1/ρ is minimized; here d(p, F) represents the (Euclidean) distance of p to the closest flat in F. We let fkq(P,ρ) denote the minimal value and interpret fkq(P,∞) to be maxr∈ Pd(r, F). When ρ=1,2 and ∞ and q=0, the problem corresponds to the k-median, k-mean and the k-center clustering problems respectively. For every 0 < ε < 1, Ssubset P and ρ ≥ 1, we show that the orthogonal projection of P onto a randomly chosen flat of dimension O(((q+1)2log(1/ε)/ε3) log n) will ε-approximate f1q(S,ρ). This result combines the concepts of geometric coresets and subspace embeddings based on the Johnson-Lindenstrauss Lemma. As a consequence, an orthogonal projection of P to an O(((q+1)2 log ((q+1)/ε)/ε3) log n) dimensional randomly chosen subspace ε-approximates projective clusterings for every k and ρ simultaneously. Note that the dimension of this subspace is independent of the number of clusters~k. Using this dimension reduction result, we obtain new approximation and streaming algorithms for projective clustering problems. For example, given a stream of n points, we show how to compute an ε-approximate projective clustering for every k and ρ simultaneously using only O((n+d)((q+1)2log ((q+1)/ε))/ε3 log n) space. Compared to standard streaming algorithms with Omega(kd) space requirement, our approach is a significant improvement when the number of input points and their dimensions are of the same order of magnitude.