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




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.