Hello everyone in the context of my thesis I need to calculate a certain criterion with points arriving sequentially at each time $x_t$. In this criterion, i need to calculate this term at each time $t$ : $(K_t + \lambda I_t )^{-1}$ where the important thing to remember is that this term is a $t \times t$ matrix that we have to invert with :
- $K_t = (k(x_s , x_s'))_{s,s'\leq t}$ the matrix of size $t \times t $ and $k(x,x')$ a kernel function
- $\lambda \in \mathbb{R}$ a regularization parameter
- And $I^t$the identity matrix of size $t \times t$
The problem is that recalculating the inverse for each point has a complexity of $O(t^4)$ which is very quickly not reasonable especially when we have many points.
So I would like to find an alternative method to iteratively invert this matrix.
I saw that we can use the Sherman-Morrison formula:
$(A+uv^{ T})^{-1}=A^{-1}-{A^{-1}uv^{\textsf {T}}A^{-1} \over 1+v^{\textsf {T}}A^{-1}u}$ with $u$ and $v$ two vectors to add. Except that this method works when the matrix to be inverted keeps the same size and is just perturbed. But in our case,e it doesn't work since the matrix changes size at each time t. Do you have any idea of what methods to use to update the inverse of a matrix that increases in size iteratively? The articles I looked at are not very clear on this.
