# Deterministic Coresets for \(k\)-Means of Big Sparse Data +
## 6 Proof of Correctness
Summing (6) over \(i\in[k]\) yields\[\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}=\sum_{p\in P^{\prime}}u(p)\left(\left\|q_ {p}^{*}-q^{*}\right\|^{2}-\left\|q_{p}^{*}-q_{p}\right\|^{2}\right)\] \[=\sum_{p\in P^{\prime}}u(p)\left(\left\|(q_{p}^{*}-\mu(P))+(\mu(P) -q^{*})\right\|^{2}-\left\|(q_{p}^{*}-\mu(P))+(\mu(P)-q_{p})\right\|^{2}\right) \tag{7}\] \[=\sum_{p\in P^{\prime}}u(p)\left(\left\|\mu(P)-q^{*}\right\|^{2}- \left\|\mu(P)-q_{p}\right\|^{2}\right)\] (8) \[-2\sum_{p\in P^{\prime}}u(p)(q_{p}^{*}-\mu(P))(q^{*}-q_{p}). \tag{9}\]  
To bound (8), we substitute \(x=q^{*}\) and then \(x=q\) in Lemma 1, and obtain that for every \(q\in Q\)  
\[\left(\left\|\mu(P)-q^{*}\right\|^{2}-\left\|\mu(P)-q\right\|^{2} \right)\sum_{p\in P}u(p) =\cos(P,\{q^{*}\})-\cos(P,\mu(P))-\left(\cos(P,\{q\})-\cos(P,\mu (P))\right)\] \[\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}\]0  
where the last inequality is by the definition of \(q^{*}\). This implies that for every \(p\in P^{\prime}\),  
\[\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}\]1  
Plugging the last inequality in (8) yields  
\[\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}\]2 \[\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}\]3 (11) \[\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}\]4 (12) \[\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}\]5  
where (11) is by Cauchy-Schwartz inequality, and in (12) we use the fact that \(2 ab\leq a^{2}+b^{2}\) for every \(a,b\geq 0\). To bound the left term of (13) we use the fact \(q_{p}^{*}=\mu(P_{i})\) and substitute \(x=\mu(P)\), \(P=P_{i}\) in Lemma 1 for every \(i\in[k]\) as follows. \[\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}\]6 \[\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}\]7  
Plugging (14) and the last inequality in (13) yields  
\[\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}\]8 \[\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}\]9  
Rearranging,  
\[=\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)\]0  
Together with (2) this proves Lemma 2. Lemma 3: Let \(S\) be a \((1,\varepsilon)\)-coreset for a weighted set \(P\) in \(\mathbb{R}^{d}\). Let \(Q\subseteq\mathbb{R}^{d}\) be a finite set. Then  
\[=\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)\]1  
Proof. : Let \(q_{P}\in Q\) be a center such that \(\text{cost}(P,\{q_{P}\})=\min_{q\in Q}\text{cost}(P,\{q\})\), and let \(q_{S}\in Q\) be a center such that \(\text{cost}(S,\{q_{S}\})=\min_{q\in Q}\text{cost}(S,\{q\})\). The right side of (15) is bounded by  
\[=\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)\]2  
where the first inequality is by the optimality of \(q_{S}\), and the second inequality is since \(S\) is a coreset for \(P\). Similarly, the left hand side of (15) is bounded by  
\[=\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)\]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  
where the last inequality follows from the assumption \(\varepsilon<1\).