6
$\begingroup$

I am looking for an efficient solution for inverting a matrix of the following form:

$$D+aP$$

where $D$ is a (full-rank) diagonal matrix, $a$ is a constant, and $P$ is an all-ones matrix.

Inverse of constant matrix plus diagonal matrix gives a solution to the special case where all diagonal entries of $D$ are the same.

The Sherman-Morrison formula is also capable of providing a solution to this problem by setting appropriate $u$ and $v$, but it loses efficiency ($O(n^3)$ time complexity to compute) at high dimension. I am hoping to get a result in the same form so the space and time complexity are both $O(n)$.

$\endgroup$
  • 1
    $\begingroup$ I don't think that the inverse of a matrix of the form $D + aP$ is of the same form in general. $\endgroup$ – J. J. Sep 22 '14 at 9:19
  • $\begingroup$ I guess you are right. Maybe the best I could do is to find efficient approximations. $\endgroup$ – aaronqli Sep 22 '14 at 10:01
2
$\begingroup$

What is wrong with using Sheman-Morrison? If $P$ is a matrix of all ones, then setting $$ u=(1,\dots,1)^T, \ v = a\cdot u $$ will do the trick. The matrix-vector product $(D+\alpha P)^{-1}$ can be computed in $O(n)$. The matrix $(D+\alpha P)^{-1}$ it self in $O(n^2)$.

Edit: Here is how to evaluate $(D+\alpha P)^{-1}x$. Let $e=(1,\dots,1)^T$. By Sherman-Morrison $$ \begin{split} (D+a P)^{-1}x = (D+aee^T)^{-1}x&= D^{-1}x + a\frac{D^{-1}ee^TD^{-1}}{1+ae^TD^{-1}e}x\\ &=D^{-1}x + a\frac{(D^{-1}e)(e^T(D^{-1}x))}{1+ae^T(D^{-1}e)}. \end{split}$$ The multiplication $D^{-1}y$ is $O(n)$, computing $e^Ty$ is $O(n)$, so the matrix-vector product above costs $O(n)$ operations.

To compute the inverse you can do $$ (D+a P)^{-1} = D^{-1} + a\frac{(D^{-1}e)(e^TD^{-1})}{1+ae^T(D^{-1}e)}. $$ Here the costly operation is to compute the rank-one matrix $(D^{-1}e)(e^TD^{-1})$ and to add matrices. Filling a $n\times n$ matrix in $O(n^2)$ time is optimal. After all, there are $n^2$ elements that need to be written.

$\endgroup$
  • $\begingroup$ Do you mean $u=a\mathbb{1}^T$? And can you explain more on how matrix-vector product is computed in $O(n)$ (I presume you mean $(D+aP)^{-1}x$ for some vector $x$?)? $O(n^2)$ is still not very efficient. $\endgroup$ – aaronqli Sep 22 '14 at 9:54
  • $\begingroup$ Oops, I am surprised by how simple this is and how stupid I was after you write it up. Need to get more coffee for doing late night math. $\endgroup$ – aaronqli Sep 22 '14 at 10:16

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.