[Math] Efficient diagonal update of matrix inverse

inverselinear algebramatrices

I am computing $(kI + A)^{-1}$ in an iterative algorithm where $k$ changes in each iteration. $I$ is an $n$-by-$n$ identity matrix, $A$ is an $n$-by-$n$ precomputed symmetric positive-definite matrix. Since $A$ is precomputed I may invert, factor, decompose, or do anything to $A$ before the algorithm starts. $k$ will converge (not monotonically) to the sought output.

Now, my question is if there is an efficient way to compute the inverse that does not involve computing the inverse of a full $n$-by-$n$ matrix?

Best Answer

Turns out this was very simple. I'll just write it here if someone else has need for it: $$(kI+A)^{-1}=(kI+PDP^{-1})^{-1}=(P(D + kI)P^{-1})^{-1}=P(D + kI)^{-1}P^{-1}$$ where $A=PDP^{-1}$ is the eigenvalue decomposition. And the inverse of a diagonal matrix is quickly computed as the matrix with diagonal elements the reciprocal of the diagonal elements of the original matrix. This is roughly $50$ times faster than the original solution for my data on my computer.

-- Tommy L

Related Solutions

[Math] Inverse of a symmetric positive semi-definite matrix

The idea is that the singular value decomposition,

$$\mathbf A=\mathbf U\mathbf \Sigma\mathbf V^\top$$

and the eigendecomposition

$$\mathbf A=\mathbf Q\mathbf D\mathbf Q^\top$$

of a symmetric matrix are one and the same.

Thus, if one wants the Moore-Penrose pseudoinverse of $\mathbf A$, either decomposition could be used. (However, an SVD routine generally wouldn't exploit the nice structure of a symmetric matrix, so a bit more computational effort than what is actually needed will be used in that case; thus, use the eigendecomposition.)

The idea is that, letting $\mathbf A^\dagger$ be the Moore-Penrose pseudoinverse, we have the property

$$\mathbf A^\dagger=\mathbf Q\mathbf D^\dagger\mathbf Q^\top$$

where $\mathbf D^\dagger$ is (usually) computed via the following procedure: take $d_1$ to be the largest eigenvalue, and let $\varepsilon$ be machine epsilon. Reciprocate any entry of $\mathbf D$ that is greater than $\varepsilon\cdot d_1$, and set all other entries to zero.

[Math] Efficient computation of Cholesky decomposition during tridiagonal matrix inverse

Here is my matlab code

     function[L]=MyChol(A)

     [n,m]=size(A);
     L=eye(n);
     for k=1:n-1
           L(k,k)=sqrt(A(k,k));
           L(k+1:n,k)=(A(k+1:n,k))/L(k,k);
           A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-L(k+1:n,k)*L(k+1:n,k)';
     end
     L(n,n)=sqrt(A(n,n));
     end

$A=LL^T$

Best Answer

Related Solutions

[Math] Inverse of a symmetric positive semi-definite matrix

[Math] Efficient computation of Cholesky decomposition during tridiagonal matrix inverse

Related Question