7
$\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$
2
  • 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.
    Commented Sep 22, 2014 at 9:19
  • $\begingroup$ I guess you are right. Maybe the best I could do is to find efficient approximations. $\endgroup$
    – aaronqli
    Commented Sep 22, 2014 at 10:01

1 Answer 1

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$
2
  • $\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
    Commented Sep 22, 2014 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
    Commented Sep 22, 2014 at 10:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .