Updating the Inverse of the Kernel Matrix

The calculation of the updated solution $\alpha$$_n$ requires the calculation of the $N\times N$ inverse matrix $\textbf{K}_n^{-1}$ for each window. This is costly both computationally and memory-wise (requiring $O(N^3)$ operations). Therefore an update algorithm is developed that can compute $\textbf{K}_n^{-1}$ solely from knowledge of the data of the current window $\{\textbf{X}_n,\textbf{y}_n\}$ and the previous $\textbf{K}_{n-1}^{-1}$. The updated solution $\alpha$$_n$ can then be calculated in a straightforward way using Eq. (9).

Given the regularized kernel matrix $\textbf{K}_{n-1}$, the new regularized kernel matrix $\textbf{K}_n$ can be constructed by removing the first row and column of $\textbf{K}_{n-1}$, referred to as $\textbf{\^K}_{n-1}$, and adding kernels of the new data as the last row and column:

$$\textbf{K}_n = \begin{bmatrix}\textbf{\^K}_{n-1} & \textbf{k}_{n-1}(\textbf{x}_n)\\ \textbf{k}_{n-1}(\textbf{x}_n)^T & k_{nn}+c\end{bmatrix}$$ (10)

where $\textbf{k}_{n-1} (\textbf{x}_n) = [\kappa(\textbf{x}_{n-N+1}, \textbf{x}_n), \dots, \kappa(\textbf{x}_{n-1}, \textbf{x}_n)]^T$ and $k_{nn} = \kappa(\textbf{x}_{n}, \textbf{x}_n)$.

Calculating the inverse kernel matrix $\textbf{K}_n^{-1}$ is done in two steps, using the two inversion formulas derived in appendices A.1 and A.2. Note that these formulas do not calculate the inverse matrices explicitly, but rather derive them from known matrices maintaining an overall time and memory complexity of $O(N^2)$ of the algorithm.

First, given $\textbf{K}_{n-1}$ and $\textbf{K}_{n-1}^{-1}$, the inverse of the $N-1\times N-1$ matrix $\textbf{\^K}_{n-1}$ is calculated according to Eq. (12). Then $\textbf{K}_n^{-1}$ can be calculated applying the matrix inversion formula from Eq. 11, based on the knowledge of $\textbf{\^K}_{n-1}^{-1}$ and $\textbf{K}_{n}$. The complete algorithm is summarized in Alg. (1).