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.

  • $\begingroup$ I think it might be useful to know how are you actually computing/expanding $K_t$ from $K_{t-1}$ $\endgroup$
    – VanBaffo
    Mar 17 at 11:49
  • $\begingroup$ I changed the post $\endgroup$ Mar 17 at 12:07
  • $\begingroup$ Did you try to see how the eigenvalues of such sequence of matrices change? Is there a pattern? That can be easily coded $\endgroup$
    – VanBaffo
    Mar 17 at 13:27
  • $\begingroup$ If A is a square block sub matrix of a slightly larger square matrix A', then old-fashioned row-reduction should solve your problem. Suppose you already know the inverse of the smaller block $A$. Row reduce the augmented matrix [A',I'] by multiplying the upper left block by the known $A^{-1}$. Since there is only one new column and row in the big matrix, the arithmetic involved in tidying up the last column and row is straightforward. $\endgroup$
    – MathWonk
    Mar 17 at 15:26


You must log in to answer this question.