6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Fun question (+1). $\endgroup$
    – usεr11852
    Mar 4, 2019 at 23:30

1 Answer 1

4
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.