# PTAS for projective clustering : survey

$$(k,j)$$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $$k$$ $$j$$-flats in $$\mathbb{R}^d$$ that minimizes the cost function as defined below:

Given a $$j$$-flat $$f$$ in $$\mathbb{R}^d$$, and a point $$x$$ in $$\mathbb{R}^d$$, define $$dist(x,f) = \min_{q\in f}{||x-q||}$$.

Given a set of $$k$$ $$j$$-flats $$F$$ in $$\mathbb{R}^d$$, and a point $$x$$ in $$\mathbb{R}^d$$, define $$dist(x,F) = \min_{f\in F}{dist(x,f)}$$.

Given a set $$P$$ of $$n$$ points in $$\mathbb{R}^d$$, a set of $$k$$ $$j$$-flats $$F$$ in $$\mathbb{R}^d$$, define the cost function as $$cost(P,F) = \sum_{p\in P}dist(p,F)^2$$.

This paper gives a PTAS for this problem with a running time $$O(d(\frac{n}{\epsilon})^{\frac{jk^3}{\epsilon}})$$. Further research also gives bicriteria approximation for this problem. A very general framework is given in this paper that achieves better bounds (but not a PTAS).

It would be very nice to have some input from the cs theory community. Some reference to recent paper regarding this problem would be greatly appreciated.

Thanks