$(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
