Fixed-Budget Kernel RLS

An important aspect of online algorithms is that their computational complexity should be moderate in every iteration. Therefore, one of the design goals for the proposed method was to obtain a complexity not higher than $O(M^2)$, where $M$ is the number of patterns stored in memory.

In the following, we describe the different parts of the algorithm, starting by the algebraic operations necessary to update the KRLS solution efficiently. The criterion used to determine the least significant pattern in memory is discussed in section 3.2, and in section 3.3 we propose a simple memory update formula that allows to deal with time-varying nonlinear mappings. By ${\mathbf K}_n$ we will denote the regularized kernel matrix ${\mathbf K}+\lambda {\mathbf I}$ obtained in the $n$-th iteration.