## 2 Methods
### General Prototype-Based Clustering and Its Convergence
If assignments to clusters and to the closest cluster prototypes do not change,we are done, so let us assume that the repeated step 1 in Algorithm 1 has identified at least one \(1\leq j\leq N\) such that, for \(\mathbf{x}_{j}\in\mathbf{C}_{k}^{t}\), there exists a better prototype candidate:  
\[\|\mathbf{x}_{j}-\mathbf{b}_{k}^{t}\|_{p}>\|\mathbf{x}_{j}-\mathbf{b}_{k}^{t}\| _{p}\quad\text{for some }\;k^{\prime}\
eq k. \tag{3}\]  
Then, a direct computation, using monotonicity of the function \(\|\cdot\|^{q}\) for \(q=\{1,2\}\) and reflecting the change in the assignments, gives  
\[ \begin{split}\mathcal{J}(\{\mathbf{b}_{k}^{t}\})=\sum_{k=1}^{K} \sum_{\mathbf{x}_{i}\in\mathbf{C}_{k}^{t}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{t} \|_{p}^{q}&=\sum_{k=1}^{K}\left(\sum_{\begin{subarray}{c} \mathbf{x}_{i}\in\mathbf{C}_{k}^{t}\\ i\
eq j\end{subarray}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{t}\|_{p}^{q}+\| \mathbf{x}_{j}-\mathbf{b}_{k}^{t}\|_{p}^{q}\right)\\ &>\sum_{k=1}^{K}\left(\sum_{\begin{subarray}{c}\mathbf{x}_{i} \in\mathbf{C}_{k}^{t}\\ i\
eq j\end{subarray}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{t}\|_{p}^{q}+\|\mathbf{x }_{j}-\mathbf{b}_{k}^{t}\|_{p}^{q}\right)=\sum_{k=1}^{K}\sum_{\mathbf{x}_{i} \in\mathbf{C}_{k}^{t+1}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{t}\|_{p}^{q}\\ &\geq\sum_{k=1}^{K}\sum_{\mathbf{x}_{i}\in\mathbf{C}_{k}^{t+1}} \|\mathbf{x}_{i}-\mathbf{b}_{k}^{t+1}\|_{p}^{q}=\mathcal{J}(\{\mathbf{b}_{k}^{ t+1}\}).\end{split}  \tag{4}\]  
Here, the last inequality follows from the repeated Step 2 of Algorithm 1 and from the optimization-based definitions of mean/median/spatial median as minimizers of the \(l_{p}^{q}\)-norm [17] over a dataset:  
\[\sum_{\mathbf{x}_{i}\in\mathbf{C}_{k}^{t+1}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{ t+1}\|_{p}^{q}=\min_{\mathbf{b}\in\mathbb{R}^{n}}\sum_{\mathbf{x}_{i}\in \mathbf{C}_{k}^{t+1}}\|\mathbf{x}_{i}-\mathbf{b}\|_{p}^{q}\leq\sum_{\mathbf{x }_{i}\in\mathbf{C}_{k}^{t+1}}\|\mathbf{x}_{i}-\mathbf{b}_{k}^{t}\|_{p}^{q} \quad\text{for all }\;k. \tag{5}\]  
Because (4) and (5) are valid for any reallocated index \(j\) satisfying (3), we conclude that the clustering error strictly decreases when a reallocation for a set of observations occurs in Algorithm 1. To this end, because there exists only a finite number of possible sets \(\mathbf{C}_{k}^{t}\), we must have \(\mathbf{C}_{k}^{t+1}=\mathbf{C}_{k}^{t}\) after a finite number of steps \(t\mapsto t+1\). This ends the proof. The K-means++ initialization method utilizes squared Euclidean distance-based probabilities to sample initial prototypes from the data points. In Algorithm 2, this initialization strategy is generalized for varying \(l_{p}\)-norms to the \(q\)-th power. Note that Algorithm 2 is the same as the K-means++ initialization algorithm when \(p=q=2\). In order to be successful, one needs to assume in Algorithm 2 that the dataset \(\{\mathbf{x}_{i}\}_{i=1}^{N}\) has at least \(K\) distinct data points, which is a natural and reasonable assumption. In Step 2, the probability for each point \(\mathbf{x}_{i}\) to be selected as the next initial prototype is proportional to the distance to the closest already selected prototype divided by the value of the clustering error Function (2) for the already selected prototypes. Clearly, in each iteration, the most distant points (with respect to the previously selected initial prototypes) have the highest probability of being selected. ```
Input: Dataset \(\{\mathbf{x}_{i}\}_{i=1}^{N}\) and the number of clusters \(K\). Output: Initial prototypes \(\{\mathbf{b}_{k}\}_{k=1}^{K}\). 1. Select \(\mathbf{b}_{1}=\mathbf{x}_{i}\) uniformly randomly, \(i=1,\dots,N\); for\(k=2\), \(k=k+1\), \(k\leq K\)do  2. Select \(\mathbf{b}_{k}=\mathbf{x}_{i}\) with probability \(\dfrac{\min_{j=1,\dots,k-1}\|\mathbf{x}_{i}-\mathbf{b}_{j}\|_{p}^{q}}{ \mathcal{J}(\{\mathbf{b}_{j}\}_{j=1}^{k-1})}\), \(i=1,\dots,N\);  end for
```  
**Algorithm 2**General K-means++-type initialization.