# Incremental solution for matrix inverse using Shermann-Morrison in $O(n^2)$

I have been reading a presentation on Value Function Approximation by David Silver (Introduction to Reinforcement Learning Course). On page 43 he finds a solution for linear least squares for an unknown parameter vector $$w$$. He claims that, for $$N$$ features, inverting a matrix is $$O(N^3)$$, but an incremental solution using Sherman-Morrison algorithm with complexity of $$O(N^2)$$ is possible (see image). Since Sherman–Morrison formula allows for computing an inverse of the sum of an invertible matrix $$A$$ and the outer product, $$uv^T$$, of vectors $$u$$ and $$v$$, I don't really see how this applies to this case as well.

• Fun question (+1). Mar 4, 2019 at 23:30

Within the context of linear regression, the estimated $$\beta$$ parameters are given $$(X^TX)^{-1}X^Ty$$. The main computational burden in this formula is the inversion the matrix $$A = X^TX$$. In the use-case of batch learning, we have already estimate for $$A$$ as well as for $$A^{-1} = (X^TX)^{-1}$$ from our previous iteration. When we get another batch we can look into how this can be expressed as an additive change on $$A$$ in the form of $$A_{new} = A + uv^T$$. Notice that the extra sample/batch will extend $$X$$ by a row but it will leave $$A$$ to be the same dimensions as before. Thus, we have $$A_{new}^{-1}= (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1 + v^TA^{-1}u}$$.