I want to know the time complexity of inverting $K$, where $K$ is an positive-definite $n\times n$ matrix: $$K=\Lambda+Q$$, where $\Lambda$ and $Q$ are both $n\times n$ matrix, $\Lambda$ is a full-rank diagonal matrix and $Q$ has rank $m$.

Snelson claims that $K$ can be inverted in $\mathcal O(nm^2)$ (page 3). However, I tried Sherman-Morrison Formula and Woodbury formula and both result in $\mathcal O(n^2m)$. $$$$

  • Sherman-Morrison Formula says $(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

Let $Q=\sum_{i=1}^mu_iv_i^T$, where $u_i$ and $v_i$ are $n\times 1$ vectors, $i\in\{1,2,...,m\}$. Thus, $K=\Lambda+\sum_{i=1}^mu_iv_i^T$.

By Sherman-Morrison Formula, $$K^{-1}=(\Lambda+\sum_{i=1}^mu_iv_i^T)^{-1}\\=(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}+\frac{(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}u_mv_m^T(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}}{1+v_m^T(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}u_m}$$

By doing so for $m$ times, $K^{-1}$ can be solved by calculating $\Lambda^{-1}$ and $u_iv_i^T$, $i\in\{1,2,...,m\}$. It's obvious that solving $\Lambda$ is easy for it's diagonal, but $u_iv_i^T$ costs $\mathcal O(n^2)$ since they are $n\times 1$ vectors. Overall, the total time complexity should be $\mathcal O(n^2m)$, not $\mathcal O(nm^m)$.$$$$

  • Woodbury formula:$(A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}$, where $U$ is $n\times m$, $C$ is $m\times m$, and $V$ is $m\times n$.

Assuming that $Q$ can be decomposed into $UCV$ just like the $UCV$ above (please do not question the feasibility; it is true in my research area):$$K^{-1}=(\Lambda+UCV)^{-1}\\=\Lambda^{-1}-\Lambda^{-1}U(C^{-1}+V\Lambda^{-1}U)^{-1}V\Lambda^{-1}$$ $\Lambda^{-1}$ is diagonal so the time complexity can be ignored. $C^{-1}$ is $\mathcal O(m^3)$. Note that $\Lambda^{-1}U(C^{-1}+V\Lambda^{-1}U)^{-1}V\Lambda^{-1}$ eventually becomes matrix multiplication of $n\times m$ and $m\times n$ matrices, so the time complexity should be $\mathcal O(n^2m)$, not$\mathcal O(nm^2)$.

$$$$ Where did I go wrong, or there are still some tricks that can do $\mathcal O(nm^2)$?

  • 1
    $\begingroup$ If the paper does say that, it's probably a typo. In general, $K^{-1}$ is dense. As there are $O(n^2)$ entries to determine, the computational complexity shouldn't be $O(n)$ even when $m=1$. $\endgroup$ – user1551 Jun 19 '16 at 12:39
  • $\begingroup$ Make sense. I didn't even notice that I should determine $\mathcal O(n^2)$ entries for $K^{-1}$ since it's $n\times n$. Thanks! $\endgroup$ – mnicnc404 Jun 19 '16 at 12:49
  • 1
    $\begingroup$ My idea is that since $Q$ is rank-$m$, it can be written as $\sum_{i=1}^mu_iv_i^T$, which is the summation of $m$ rank-$1$ matrices. Each $u_iv_i^T$ is a rank-$1$ matrix. Let $A'=\Lambda+\sum_{i=1}^{m-1}u_iv_i^T$, so $\Lambda+\sum_{i=1}^mu_iv_i^T=\Lambda+\sum_{i=1}^{m-1}u_iv_i^T+u_mv_m^T=A'+u_m{v^T_m}$, which can be applied to Sherman-Morrison Formula. By doing so for m times, there would be only $\Lambda^{-1}$ left, thus $\mathcal O(n^2m)$. $\endgroup$ – mnicnc404 Jun 19 '16 at 13:12
  • $\begingroup$ Is $Q$ symmetric? $\endgroup$ – Rodrigo de Azevedo Jun 19 '16 at 22:28
  • $\begingroup$ This question is misleading. In the paper, they don't use a general diagonal matrix. They use $\sigma^2 I_n$, which commutes with every matrix. $\endgroup$ – Rodrigo de Azevedo Jun 19 '16 at 23:01

Your Answer

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

Browse other questions tagged or ask your own question.