# Efficient High-Dimensional Kernel k-Means++ with Random Projection
## 3 Our Method  
### Kernel k-Means with Random Projection  
With kernel k-means, similarities are determined by replacing inner products with kernel functions. The complexity of kernel computation is \(O(n^{2}D)\), which is a function of the dimensionality. The intuition of our method is to perform dimensionality reduction to reduce \(D\) with random projection prior to centroid initialization and kernel k-means clustering. The proposed method allows the computation of the kernel matrix and distances for initialization to be performed in a much lower-dimensional space in order to speed up the clustering process. As the complexity of the kernel method with conventional kernel matrix computation \(\mathbf{X}\cdot\mathbf{X}^{\mathbf{T}}\) is \(O(n^{2}D)\), the computation of the kernel matrix can be expensive when the dimensionality \(D\) is very large with genomic data, for example. We propose an approximation to the kernel matrix by using random projection, which maps the data points to a lower-dimensional space \(\phi(\mathbf{X})\cdot\phi(\mathbf{X})^{T}\), with the time complexity of \(O(n^{2})\), which is independent of \(D\). With the same rationale as the method we propose for k-means++, combining random projection with kernel k-means allows the clustering process to be done in a lower-dimensional space without significant performance degradation. With random projection and \(D\)-dimensional data vectors \(\mathbf{x}\) with \(n\) data points, we have \(\mathbf{X}\in\mathbb{R}^{n\times D}\) in which vectors are projected into much lower-dimensional subspace \(\mathbb{R}^{d}\) with \(d\ll D\), i.e.,  
\[\mathbf{X}^{proj}=\mathbf{X}\cdot\mathbf{R} \tag{4}\]  
where \(D\) denotes the original dimensionality, \(d\) denotes the reduced dimensionality, and \(\mathbb{R}^{D\times d}\) is a random matrix with its entries as normal random variables \(N(0,1)\cdot\frac{1}{\sqrt{d}}\). The complexity of this algorithm is of order \(O(Ddn)\). If the data matrix \(\mathbf{X}\) is very sparse with \(\mathbf{s}\) non-zero entries per dimension, the complexity is of order \(O(sdn)\), where \(s\) denotes the non-zero entries per dimension. \(\mathbf{x}\in\mathbb{R}^{D}\) is projected into space \(\mathbb{R}^{d}\), i.e., random projection is the mapping \(f\): \(\mathbb{R}^{D}\Rightarrow\mathbb{R}^{d}\) for all \(\mathbf{u},\mathbf{v}\) pairs in \(\mathbb{R}^{D}\):  
\[(1-\epsilon)\|\mathbf{u}-\mathbf{v}\|^{2}\leq\|f(\mathbf{u})-f(\mathbf{v})\| ^{2}\leq(1+\epsilon)\|\mathbf{u}-\mathbf{v}\|^{2} \tag{5}\]  
where \(\epsilon\) is the error bound that is determined as a function of the number of data points and dimensionality of the projected matrix, i.e., \(n\) and \(d\) as  
\[\epsilon=\sqrt{\frac{20\ log\ n}{d}} \tag{6}\]  
For kernel methods, in Lemma 1 of [1], there is a probability of at least \(1-\delta\) that  
\[\|X^{T}X-X^{T}R\cdot R^{T}X\|_{2}\leq\epsilon_{\delta} \tag{7}\]  
where the distance between the dot product in the original feature space and the dot product in the projected space is bounded by \(\epsilon_{\delta}\). In our method with kernel k-means usingrandom projection, the kernel matrix is approximated in a lower-dimensional space with the above error bound considered, shown in Algorithm 1. ```
1\(\mathbf{R}\in\mathbb{R}^{D\times d}\) random matrix \(k(\centerdot,\centerdot)\)denotes the kernel function. \(\mathbf{X}^{proj}=\mathbf{X}\cdot\mathbf{R}\) Choose initial centers \(\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{k}\) uniformly at random from \(\mathbf{X}^{proj}\).