# Minimizing Interference-to-Signal Ratios in Multi-Cell Telecommunication Networks
## 3 Dot-Product Clustering Algorithm for Total Interference Minimization Problem
### Phase 2: Defining BS Clusters  
As we discussed earlier, we have great freedom to determine the BS clusters. However, for simplicity, here we apply a _hierarchical_ clustering algorithm: we call it DPH-clustering, short for _dot-product hierarchical clustering_. The fixed integer \(M\), which is the size of the cluster system, is part of the input. At the beginning, we assign a cluster to each BS containing it. Then we recursively merge the two clusters that have the highest similarity \(\rho\)between them until the prescribed number of clusters is reached. As we will soon see, this works reasonably well. Here we want to draw attention to the fact that using normalization in Equations (3) and (5) is a natural idea.  
We start with the finest partition: let \(\mathcal{I}_{0}\) consist of the individual clusters for each BS in \(I\) (thus \(|I|=|\mathcal{I}_{0}|\)). We combine two clusters in each of the \(|I|-M\) rounds iteratively to derive a sequence of partitions \(\mathcal{I}_{0},\mathcal{I}_{1},\ldots,\mathcal{I}_{|I|-M}\) of \(I\), where \(|\mathcal{I}_{r}|=|I|-r\). \(\mathcal{I}_{r}\) is obtained from \(\mathcal{I}_{r-1}\) by combining the two clusters of \(\mathcal{I}_{r-1}\) with the largest similarity \(\rho\) between them as defined by Equation (5).  
In Algorithm 1, we maintain the similarity measure \(\rho(I_{k},I_{m})\) for every pair of clusters \(I_{k},I_{m}\in\mathcal{I}_{r}\) as follows. Let us define the symmetric function \(dot\) for every \(k=1,\ldots,M\) as  
\[dot(I_{k},I_{m})=\operatorname{vec}(I_{k})\cdot\operatorname{vec}(I_{m})^{ \top}. \tag{6}\]  
If \(dot\) is already computed for every pair in \(\mathcal{I}_{r}\times\mathcal{I}_{r}\), then the similarity measure \(\rho\) can be computed via three scalar operations for any pair of clusters in \(\mathcal{I}_{r}\times\mathcal{I}_{r}\) since  
\[\rho(I_{k},I_{m})=\frac{dot(I_{k},I_{m})}{\sqrt{dot(I_{k},I_{k})\cdot dot(I_{m },I_{m})}}. \tag{7}\]  
```
functionDPH-clustering(\(I,W,M\)) \(\mathcal{I}_{0}\leftarrow\binom{I}{1}\) \(dot\gets W\cdot W^{T}\)\(\triangleright\) matrix multiplication for\(r=0\) to \(|I|-M-1\)do \(\{I^{\prime},I^{\prime\prime}\}\leftarrow\operatorname*{arg\,max}_{\{I_{k},I_{m} \}\in(\mathcal{I}_{r}^{2})}\rho(I_{k},I_{m})\)\(\triangleright\) (7) \(\mathcal{I}_{r+1}=\mathcal{I}_{r}-\{I^{\prime},I^{\prime\prime}\}+\{I^{\prime} \cup I^{\prime\prime}\}\) update dot \(\triangleright\)\(\mathcal{O}(b)\) scalar operations endfor return\(\mathcal{I}_{|I|-M}\) endfunction
```  
**Algorithm 1** Hierarchical clustering based on the similarity function \(\rho\)  
Lemma 1: _Let the time complexity of the matrix multiplication \(W\cdot W^{T}\) be \(f(W)\). Using a max-heap data structure, DPH-clustering runs in \(f(W)+\mathcal{O}((b-M)b\log b)\) time._  
Proof: It is easy to see that the running time of Algorithm 1 is in the range of \(f(W)+\mathcal{O}\big{(}b^{2}u+(b-M)\cdot b^{2}\big{)}\) because when two clusters are combined, \(dot\) can be updated by summing the corresponding two rows and two columns. Moreover, we can store the \(\rho\)-values of pairs in \(\mathcal{I}_{r}\times\mathcal{I}_{r}\) in a _max-heap_: when two clusters are merged, at most \(2b\) values need to be removed and at most \(b\) new values need to be inserted into the heap that contains the at most \(\binom{b}{2}\) elements of the set \(\{\rho(I_{k},I_{m})\mid\{I_{k},I_{m}\}\in\binom{\mathcal{I}_{r}}{2}\}\). With these optimizations, the _for_-loop takes at most \(\mathcal{O}((b-M)\cdot b\log b)\) steps.  
In theory, the running time of Algorithm 1 is dominated by the matrix multiplication \(W\cdot W^{T}\), unless the magnitude of \(b\) and \(u\) are of different orders. There are many techniques to accelerate the multiplication of matrices, which we do not discuss here. In practice, a plethora of efficient off-the-shelf implementations that take advantage of hardware-accelerated vector instruction are available, so much so that \(f(W)\) can be contained in \(\mathcal{O}((b-M)b\log b)\) for some combination of the CPU and practical instances of the problem.