I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.

Project clustering is a natural generalization of k-means clustering. Given a point set $P$, the goal to find $k$, $j$-dimensional affine spaces(flats) $F_1,\cdots,F_k$, such that the following objective function is minimized

$\sum_{p\in P} \min_{1\leq i \leq k}dist^2(p,F_i)$, where $dist(p,F)$ is the orthogonal distance between point $p$ and flat $F$.

Clearly, as is the case with k-means, the $k$ optimal flats induces a partitioning of the point set $P$, into $k$ subsets $C_1,\cdots,C_k$, such that points in $C_i$ is closer to flat $F_i$ than any other flat $F_j, i\neq j$.

The aforementioned paper (in page 7, third line from last), it is said that "It is easy to see that $F_i$ passes through the mean $o_i$ of $C_i$". I fail to see the simplicity of this. Can someone please elaborate on that, with a proof sketch?

N.B: mean of a point set $P$ is defined as $\frac{1}{|P|}\sum_{p\in P}p$.

  • 1
    $\begingroup$ See the book Foundations of Data Science cs.cornell.edu/jeh/book.pdf, section 3.9.1. $\endgroup$ Commented Apr 15, 2019 at 20:59
  • $\begingroup$ @ChandraChekuri ok, I get it. In fact I have managed to prove something similar. I will post this as an answer tomorrow. $\endgroup$ Commented Apr 15, 2019 at 21:26


Your Answer

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