<p>I am confused about a statement made in the paper <a href="https://arxiv.org/pdf/1204.6717.pdf" rel="nofollow noreferrer">Linear Time Algorithm for Projective Clustering</a>, section 5.1, second paragraph, second line.</p>

<p>Project clustering is a natural generalization of k-means clustering. Given a point set <span class="math-container">$P$</span>, the goal to find <span class="math-container">$k$</span>, <span class="math-container">$j$</span>-dimensional affine spaces(flats) <span class="math-container">$F_1,\cdots,F_k$</span>, such that the following objective function is minimized</p>

<p><span class="math-container">$\sum_{p\in P} \min_{1\leq i \leq k}dist^2(p,F_i)$</span>, where <span class="math-container">$dist(p,F)$</span> is the orthogonal distance between point <span class="math-container">$p$</span> and flat <span class="math-container">$F$</span>.</p>

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

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

<p>N.B: mean of a point set <span class="math-container">$P$</span> is defined as <span class="math-container">$\frac{1}{|P|}\sum_{p\in P}p$</span>.</p>

CC BY-SA 4.0
2019-04-15T20:59:23.593Z
See the book Foundations of Data Science https://www.cs.cornell.edu/jeh/book.pdf, section 3.9.1.
Chandra Chekuri
CC BY-SA 4.0
2019-04-15T21:26:56.907Z
@ChandraChekuri ok, I get it. In fact I have managed to prove something similar. I will post this as an answer tomorrow.
Sudipta Roy
<linear-algebra><computational-geometry><clustering>
Does optimal fitting flat must pass through the mean of the point set?
Sudipta Roy
# Does optimal fitting flat must pass through the mean of the point set?

(Asked by: username_0 on 2019-04-15)

I am confused about a statement made in the paper [Linear Time Algorithm for Projective Clustering](https://arxiv.org/pdf/1204.6717.pdf), 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$.

**Tags:** linear-algebra, computational-geometry, clustering
> **Comments:**
> **username_1**: See the book Foundations of Data Science https://www.cs.cornell.edu/jeh/book.pdf, section 3.9.1.  
> **username_0**: @ChandraChekuri ok, I get it. In fact I have managed to prove something similar. I will post this as an answer tomorrow.  

---

## 0 answers

