## 4 Applications to Center-Based Clustering
### Robustness of Generalized Kullback-Leibler Centroids  
The fact that the generalized KLDs are conformal representational Bregman divergences can be used to design efficient algorithms in computational geometry [60]. For example, let us consider the centroid (or barycenter) of a finite set of weighted probability measures \(P_{1},\ldots,P_{n}\ll\mu\) (with RN derivatives \(p_{1},\ldots,p_{n}\)) defined as the minimizer of  
\[\min\sum_{i=1}^{n}w_{i}\,I_{1}^{f,\delta}(p_{i}:c),\]  
where the \(w_{i}\)'s are positive weights summing up to one (\(\sum_{i=1}^{n}w_{i}=1\)). The divergences \(I_{1}^{f,\delta}(p_{i}:c)\) are separable. Thus, consider without loss of generality, the scalar-generalized KLDs so that we have  
\[I_{1}^{f,\delta}(p:q)=\frac{1}{f^{\prime}(p)}\,B_{F}(g(q):g(p)),\]  
where \(p\) and \(q\) are scalars. Since the Bregman centroid is unique and always coincide with the center of mass [72]  
\[c^{*}=\arg\min w_{i}\sum_{i=1}^{n}B_{F}(p_{i}:c)=\sum_{i=1}^{n}w_{i}p_{i},\]  
for positive weights \(w_{i}\)'s summing up to one, we deduce that the right-sided generalized KLD centroid  
\[\arg\min_{c}\frac{1}{n}\sum_{i=1}^{n}I_{1}^{f,\delta}(p_{i}:c)=\arg\min_{c} \frac{1}{n}\sum_{i=1}^{n}\frac{1}{f^{\prime}(p_{i})}\,B_{F}(g(c):g(p_{i}))\]  
amounts to a left-sided Bregman centroid with un-normalized positive weights \(W_{i}=\frac{1}{f^{\prime}(p_{i})}\) for the scalar Bregman generator \(F(x)=f(g^{-1}(x))\) with \(F^{\prime}(x)=\frac{f^{\prime}(g^{-1}(x))}{g^{\prime}(g^{-1}(x))}\). Therefore, the right-sided generalized KLD centroid \(c^{*}\) is calculated for normalized weights \(w_{i}=\frac{W_{i}}{\sum_{i=1}^{n}W_{i}}\) as:  
\[c^{*} = (F^{\prime})^{-1}\Bigg{(}\sum_{i=1}^{n}w_{i}F^{\prime}(g(p_{i})) \Bigg{)}, \tag{111}\] \[= (F^{\prime})^{-1}\left(\sum_{i=1}^{n}\frac{1}{f^{\prime}(p_{i}) \sum_{j=1}^{n}\frac{1}{f^{\prime}(p_{j})}}\frac{f^{\prime}(p_{i})}{\delta^{ \prime}(p_{i})}\right),\] (112) \[= (F^{\prime})^{-1}\left(\sum_{i=1}^{n}\frac{1}{g^{\prime}(p_{i}) \sum_{j=1}^{n}\frac{1}{f^{\prime}(p_{j})}}\right). \tag{113}\]Thus, we obtain a closed-form formula when \((F^{\prime})^{-1}\) is computationally tractable. For example, consider the \((r,s)\)-power KLD (with \(r>s\)). We have \(f^{\prime}(x)=rx^{-1}\), \(g^{\prime}(x)=sx^{s-1}\), \(F(x)=x^{\frac{r}{s}}\), \(F^{\prime}(x)=\frac{r}{s}\,x^{\frac{r-s}{s}}\) and therefore, we get \({F^{\prime}}^{-1}(x)=\left(\frac{s}{x}x\right)^{\frac{s}{r-s}}\). Thus, we get a closed-form formula for the right-sided \((r,s)\)-power Kullback-Leibler centroid using Equation (113). Overall, we can design a \(k\)-means-type algorithm with respect to our generalized KLDs following [72]. Moreover, we can initialize probabilistically \(k\)-means with a fast \(k\)-means++ seeding [34] described in Algorithm 1. The performance of the \(k\)-means++ seeding (i.e., the ratio \(\frac{L_{D}(\mathcal{PC})}{\min_{\mathcal{C}}L_{D}(\mathcal{PC})}\)) is \(O(\log k)\) when \(D(p:q)=\|p-q\|^{2}\), and the analysis has been extended to arbitrary divergences in [75]. The merit of using the \(k\)-means++ seeding is that we do not need to iteratively update the cluster representatives using [PERSON]'s heuristic [69] and we can thus bypass the calculations of centroids and merely choose the cluster representatives from the source data points \(\mathcal{P}\) as described in Algorithm 1.