# Deterministic Coresets for \(k\)-Means of Big Sparse Data +
## 6 Proof of Correctness  
The first lemma states the common fact that the sum of squared distances of a set of point to a center is the sum of their squared distances to their center of mass, plus the squared distance to the center (the variance of the set). **Lemma 1**: _For every \(x\in\mathbb{R}^{d}\)_  
\[\operatorname{cost}(P,x)=\operatorname{cost}(P,\mu(P))+\|\mu(P)-x\|^{2}\sum_{ p\in P}u(p).\]  
We have  
\[\operatorname{cost}(P,x)-\rho =\sum_{p\in P}u(p)\left\|p-x\right\|^{2}=\sum_{p\in P}u(p)\left\| (p-\mu(P))+(\mu(P)-x)\right\|^{2}\] \[=\sum_{p\in P}u(p)\left\|p-\mu(P)\right\|^{2}+\sum_{p\in P}u(p) \left\|\mu(P)-x\right\|^{2}+2(\mu(p)-x)\cdot\sum_{p\in P}u(p)(p-\mu(P)).\]  
The last term equals zero since \(\mu(P)=\dfrac{1}{\sum_{p^{\prime}\in P}u(p^{\prime})}\cdot\sum_{p\in P}u(p)\cdot p\), and thus  
\[\sum_{p\in P}u(p)(p-\mu(P))=\sum_{p\in P}u(p)\cdot p-\sum_{p\in P}u(p)\mu(P)= \sum_{p\in P}u(p)\cdot p-\sum_{p\in P}u(p)\cdot p=0.\]Hence,  
\[\text{cost}(P,x)=\rho+\sum_{p\in P}u(p)\left\|p-\mu(P)\right\|^{2}+\sum_{p\in P}u( p)\left\|\mu(P)-x\right\|^{2}=\text{cost}(P,\mu(P))+\left\|\mu(P)-x\right\|^{2} \sum_{p\in P}u(p).\]  
The second lemma shows that assigning all the points of \(P\) to the closest center in \(Q\) yields a small multiplicative error if the 1-mean and the \(k\)-means of \(P\) has roughly the same cost. If \(t=0\), this means that we can approximate \(\text{cost}(P,Q)\) using only one center in the query; see Line 1 of Algorithm 1. Note that \((1+2\varepsilon)/(1-2\varepsilon)\leq 1+4\varepsilon\) for \(\varepsilon<1/4\). Lemma 2: _For every set \(Q\subseteq\mathbb{R}^{d}\) of \(\left|Q\right|=k\) centers we have_  
\[\text{cost}(P,Q)\leq\min_{q\in Q}\text{cost}(P,\{q\})\leq\text{cost}(P,Q) \cdot\frac{1+2\varepsilon}{1-2\varepsilon}+\frac{\text{opt}(P,1)-\text{opt}( P,k)}{(1-2\varepsilon)\varepsilon}. \tag{1}\]  
Proof. : Let \(q^{*}\) denote a center that minimizes \(\text{cost}(P,\{q\})\) over \(q\in Q\). The left inequality of (1) is then straight-forward since  
\[ \begin{split}\text{cost}(P,Q)-\min_{q\in Q}\text{cost}(P,\{q\})& =\sum_{p\in P^{\prime}}\min_{q\in Q}u(p)\left\|p-q\right\|^{2}- \sum_{p\in P^{\prime}}u(p)\left\|p-q^{*}\right\|^{2}\\ &=\sum_{p\in P^{\prime}}u(p)\left(\min_{q\in Q}\left\|p-q\right\|^ {2}-\left\|p-q^{*}\right\|^{2}\right)\leq 0.\end{split}  \tag{2}\]  
It is left to prove the right inequality of (1). Indeed, for every \(p\in P^{\prime}\), let \(q_{p}\in Q\) denote the closest point to \(p\) in \(Q\). Ties are broken arbitrarily. Hence,  
\[\min_{q\in Q}\text{cost}(P,\{q\})-\text{cost}(P,Q)=\sum_{p\in P^{\prime}}u(p) \left\|p-q^{*}\right\|^{2}-\sum_{p\in P^{\prime}}u(p)\left\|p-q_{p}\right\|^ {2}.\]  
Let \(\{P_{1},\cdots,P_{k}\}\) denote the partition of \(P\) by \(Q=\left\{q^{1},\cdots,q^{k}\right\}\), where \(P_{i}\) are the closest points to \(q^{i}\) for every \(i\in[k]\); see Section 4. For every \(p\in P_{i}^{\prime}\), let \(q_{p}^{*}=\mu(P_{i})\). Hence,  
\[\sum_{p\in P_{i}^{\prime}}u(p)\left\|p-q^{*}\right\|^{2}-\sum_{p \in P_{i}^{\prime}}u(p)\left\|p-q_{p}\right\|^{2} \tag{3}\] \[=\sum_{p\in P_{i}^{\prime}}u(p)\left\|p-\mu(P_{i})\right\|^{2}+ \left\|\mu(P_{i})-q^{*}\right\|^{2}\sum_{p\in P_{i}^{\prime}}u(p)\] (4) \[-\left(\sum_{p\in P_{i}^{\prime}}u(p)\left\|p-\mu(P_{i})\right\| ^{2}+\left\|\mu(P_{i})-q^{i}\right\|^{2}\sum_{p\in P_{i}^{\prime}}u(p)\right)\] (5) \[=\sum_{p\in P_{i}^{\prime}}u(p)\left(\left\|q_{p}^{*}-q^{*} \right\|^{2}-\left\|q_{p}^{*}-q_{p}\right\|^{2}\right), \tag{6}\]  
where in (4) and (5) we substituted \(x=q^{*}\) and \(x=q_{p}\) respectively in Lemma 1, and in (6) we use the fact that \(q_{p}^{*}=\mu(P_{i})\) and \(q_{p}=q^{i}\) for every \(p\in P_{i}\).