1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.