## 3 Traditional KRLS Algorithm
### Traditional KRLS Algorithm  
Assume a set of ordered input-output pairs \(D=\{u_{i},y_{i}\}|_{i=1}^{m}\), where \(m\) is the total number of samples, \(u_{i}\in R^{m}\) are m-dimensional input vectors and \(y_{i}\in R\) is the output. We call \(D\) a dictionary that records the input-output pairs collected before the \(i\)-th time slot. First, according to the Mercer theorem, we can adopt a nonlinear function \(\varphi(\cdot)\) to transform data \(u_{i}\in R^{m}\) into a high-dimensional feature space: \(\varphi(\cdot):\)\(R^{m}\to R^{c}\). The corresponding kernel function is \(\kappa(u,v)=\langle\varphi(u),\varphi(v)\rangle\). We need to minimize the cost function:  
\[J=\sum_{j=1}^{i}\left|y_{i}-w_{i}\varphi_{j}\right|^{2}=\left\|\Phi_{i}{}^{T}w _{i}-y_{i}\right\|^{2}, \tag{2}\]  
where \(\Phi_{i}=[\varphi(u_{1}),...,\varphi(u_{i})]=[\varphi_{1},\ldots,\varphi_{i}]\) is a high-dimensional matrix. By minimizing the cost function as (2), we can obtain weight \(w_{i}=\Phi_{i}^{\dagger}y_{i}\), where \(\Phi_{i}^{\dagger}\) is the pseudoinverse of \(\Phi_{i}\). \(\Phi_{i}^{\dagger}\) cannot be solved directly because kernel function \(\kappa(u,v)\) is a high-dimensional  
Figure 3: An illustration of the input and output pairs in a channel prediction module. mapping, and the exact mapping function is unknown. To avoid overfitting when the samples are small, we used L2 regularization, so the cost function is reformulated as:  
\[J=\Big{\|}\Phi_{i}^{T}w_{i}-y_{i}\Big{\|}^{2}+\lambda\|w_{i}\|^{2}. \tag{3}\]  
By letting \(\frac{\partial J}{\partial w_{i}}=0\), we can obtain that  
\[w_{i}=\Phi_{i}[\lambda I+\Phi_{i}^{T}\Phi_{i}]^{-1}y_{i}=\Phi_{i}\alpha(i). \tag{4}\]  
By substituting (4) into (3), the cost function can be reformulated as:  
\[J=\Big{\|}\Phi_{i}^{T}\Phi_{i}\alpha(i)-y_{i}\Big{\|}^{2}+\lambda\|w_{i}\|^{2} =\|K_{i}\alpha(i)-y_{i}\|^{2}+\lambda\|w_{i}\|^{2}, \tag{5}\]  
where \(K_{i}\) is the kernel matrix and the element located at the \(i\)-th row and \(j\)-th column of \(K_{i}\) is \(K_{i}(i,j)=\kappa\big{(}u_{i},u_{j}\big{)}\). The problem is to solve  
\[\alpha(i)=[\lambda I+\Phi_{i}^{T}\Phi_{i}]^{-1}y_{i}=[\lambda I+K_{i}]^{-1}y_ {i}=Q(i)y_{i}, \tag{6}\]  
Then, the inverse of \(Q(i)\) can be obtained as:  
\[Q(i)^{-1}=\lambda I+K_{i}=\left[ \begin{array}{cc}Q(i-1)^{-1}&k_{i}\\ {k_{i}}^{T}&\lambda+\kappa(u_{i},u_{i})\end{array} \right], \tag{7}\]  
where \(k_{i}={\Phi_{i-1}}^{T}\varphi_{i}\). Thus, \(Q(i)\) can be solved using the inversion of the partitioned matrix. \[Q(i)=r(i)^{-1}\left[ \begin{array}{cc}Q(i-1)r(i)+z(i)z(i)^{T}&-z(i)\\ -z(i)^{T}&1\end{array} \right], \tag{8}\]  
where \(z(i)=Q(i-1)k_{i}\) and \(r(i)=\lambda+{\varphi_{i}}^{T}\varphi_{i}-z(i)^{-1}\varphi_{i}\). The traditional KRLS algorithm is summarized in Algorithm 1. ```
1:Initialize \(Q(1)=\left(\lambda+k(u_{1},u_{1})\right)^{-1}\) and \(\alpha(1)=Q(1)y_{1}\). 2:Iterate for i > 1: \(k_{i}=\Phi_{i-1}^{T}\varphi_{i}\), \(z(i)=Q(i-1)k_{i}\), \(r(i)=\lambda+{\varphi_{i}}^{T}\varphi_{i}-z(i)^{-1}\varphi_{i}\), \[Q(i)=r(i)^{-1}\left[ \begin{array}{cc}Q(i-1)r(i)+z(i)z(i)^{T}&-z(i)\\ -z(i)^{T}&1\end{array} \right]\]

**Algorithm 1** Traditional KRLS algorithm. By relying on the kernel trick, the traditional KRLS algorithm can deal with nonlinear problems by nonlinearly transforming data into a high-dimensional reproducing kernel Hilbert space, which is similar to other techniques such as support vector machines (SVMs). Compared to SVMs, it avoids large-scale high-dimensional computing through iterative computations. However, the traditional KRLS algorithm grows linearly with the number of processed data, rendering growing complexities for each consecutive update if no additional measures are taken. In order to render online kernel algorithms feasible, growth is typically slowed down by approximately representing the solution using only a subset of bases that are considered to be relevant according to a chosen criterion.