Approximation and Streaming Algorithms for Projective Clustering via Random Projections

Abstract

Let $P$ be a set of $n$ points in ${\mathbb{R}}^d$. In the projective clustering problem, given $k,q$ and norm $\rho \in [1,\infty ]$, we have to compute a set $\mathcal{F}$ of $k$ $q$-dimensional flats such that $({\sum }_{p\in P}d(p,\mathcal{F}{)}^{\rho }{)}^{1/\rho }$ is minimized; here $d(p,\mathcal{F})$ represents the (Euclidean) distance of $p$ to the closest flat in $\mathcal{F}$. We let $f_k^q(P,\rho )$ denote the minimal value and interpret $f_k^q(P,\infty )$ to be ${\max }_{r\in P}d(r,\mathcal{F})$. When $\rho =1,2$ and $\infty$ and $q=0$, the problem corresponds to the $k$-median, $k$-mean and the $k$-center clustering problems respectively. For every $0<\epsilon <1$, $S\subset P$ and $\rho \ge 1$, we show that the orthogonal projection of $P$ onto a randomly chosen flat of dimension $O(((q+1{)}^2\log (1/\epsilon )/{\epsilon }^3)\log n)$ will $\epsilon$-approximate $f_1^q(S,\rho )$. 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)/\epsilon )/{\epsilon }^3)\log n)$ dimensional randomly chosen subspace $\epsilon$-approximates projective clusterings for every $k$ and $\rho$ 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 $\epsilon$-approximate projective clustering for every $k$ and $\rho$ simultaneously using only $O((n+d)((q+1{)}^2\log ((q+1)/\epsilon ))/{\epsilon }^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.

Canadian Conference on Computational Geometry (CCCG 2015)

References in corpus (1)

• Random Projections for $k$-means Clustering