0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ See the book Foundations of Data Science cs.cornell.edu/jeh/book.pdf, section 3.9.1. $\endgroup$
    – Chandra Chekuri
    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$
    – Sudipta Roy
    Apr 15, 2019 at 21:26

0

Reset to default

Your Answer

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