## 3 Traditional KRLS Algorithm
### Traditional KRLS Algorithm
 \tag{12}\]

In another case, when the size of the dictionary reaches the fixed budget, one sample must be discarded from the kernel dictionary in each time slot. In our strategy, we first set a candidate discard set on the basis of the correlation with the new sample, and then determined the optimal discarded sample according to its output value. Candidate discard set \(S\) was composed of the samples that had high correlation with the new sample. Specifically, an existing sample in dictionary \(u_{j}\in D\) was added into \(S\) if \(\kappa(u_{j},u_{j})>\varepsilon\), where \(u_{i}\) is a new sample and \(\varepsilon\) is a threshold. Among the samples in \(S\), the one with the smallest value for prediction may be one that has the most similar information with the new sample or the one that is untypical with little probability to occur. We determined the discarded sample in combination with its corresponding output as following. Suppose that the candidate discard set is \(S=\{u_{1},u_{2},\ldots,u_{n}\}\). The weighted average of the output values can be obtained as \(y=\sum\limits_{j=1}^{n}w_{j}y_{j}\) where

\[w_{j}=\frac{\kappa(u_{i},u_{j})}{\sum\limits_{j=1}^{n}\kappa(u_{i},u_{j})} \tag{13}\]

and \(n\) is the number of samples in \(S\). The deviation between the output value of \(u_{j}\in S\) and the weighted average output value is \(e_{j}=\left|y_{j}-y\right|\). The sample with maximal deviation \(e_{\max}\) is not typical and may have occurred with a small probability, while the one with minimal deviation had similar information to that of the new sample. Suppose that the sample with the maximal deviation is \(u_{j_{max}}\), and the sample with the minimal deviation is \(u_{j_{min}}\). We chose one of these two samples to discard according to the production of \(e_{\max}\) and \(e_{\min}\). If the production of \(e_{\max}\) and \(e_{\min}\) was larger than threshold \(\tau\), this indicated that \(e_{\max}\) was large enough, so we discarded \(u_{j_{max}}\); otherwise, \(e_{\min}\) was small enough, and we discarded \(u_{j_{min}}\). The updated dictionary is:

\[D(i)\!=\!\! \begin{cases}\left[D(i-1)\backslash u_{j_{max}}\ \ u_{i}\right],if\ e_{\max}e_{\min}\geq\tau\\ \left[D(i-1)\backslash u_{j_{min}}\ \ u_{i}\right],if\ e_{\max}e_{\min}<\tau.\end{cases}  \tag{14}\]

### Case I: The Size of \(D(i)\) Is Changed

As mentioned before, the prediction process depends on whether the size of the dictionary has increased or not. In Case I, when the size of dictionary increased, we could obtain from (11) that:

\[ \begin{cases}w_{i}\!=\!\!\Phi_{i}\!\alpha(i)\\ \alpha(i)=Q(i)\,\bar{y}_{i}\\ Q(i)=[\lambda B(i)+B(i)K_{i}]^{-1}.\end{cases}  \tag{15}\]With the combination of \(B(i)\) and \(\mathrm{y}_{i}\), we could obtain exponentially weighted input signal \(\bar{y}_{i}\). We can find that

\[B(i)=\left[ \begin{array}{cc}\beta B(i-1)&0\\ 0^{T}&1\end{array} \right] \tag{16}\]

\[K_{i}=\left[ \begin{array}{cc}K_{i-1}&h(i)\\ h(i)^{T}&\kappa(u_{i},u_{i})\end{array} \right] \tag{17}\]

\[\bar{y}_{i}=\left[ \begin{array}{c}\beta y_{i-1}^{-}\\ \bar{y}_{i}\end{array} \right], \tag{18}\]

where \(h(i)=[\kappa(u_{1},u_{i}),\kappa(u_{2},u_{i}),\ldots,\kappa(u_{i-1},u_{i})]^{T}\). Thus

\[B(i)K_{i}=\left[ \begin{array}{cc}\beta B(i-1)K_{i-1}&\beta B(i-1)h(i)\\ h(i)^{T}&\kappa(u_{i},u_{i})\end{array} \right] \tag{19}\]

By substituting (19) into (15), we can obtain that

\[Q(i)=\left[ \begin{array}{cc}\beta Q(i-1)^{-1}&\beta B(i-1)h(i)\\ h(i)^{T}&\kappa(u_{i},u_{i})+\lambda\end{array} \right]^{-1} \tag{20}\]

With partitioned matrix inversion, we can obtain \(Q(i)\) in recursive form:

\[Q(i)=r(i)^{-1}\Bigg{[} \begin{array}{cc}\beta^{-1}r(i)Q(i-1)+\beta^{-1}z_{B }(i)z(i)^{T}&-z_{B}(i)\\ -\beta^{-1}z(i)^{T}&1\end{array} \Bigg{]}, \tag{21}\]

where

\[ \begin{cases}z_{B}(i)=Q(i-1)B(i-1)h(i)\\ r(i)=\kappa(u_{i},u_{i})+\lambda-h(i)^{T}z_{B}(i)\\ z(i)=Q(i-1)^{T}h(i)\end{cases}  \tag{22}\]

\[\alpha(i)=\left[ \begin{array}{c}\alpha(i-1)-z_{B}(i)r(i)^{-1}e(i)\\ r(i)^{-1}e(i)\end{array}