Sign in to follow this  
shaobohou

fast matrix inverse

Recommended Posts

if I have a symmetric matrix A and a diagonal matrix B, is there a fast way of computing the inverse of A+B using the inverse of A and the inverse of B?

Share this post


Link to post
Share on other sites
In your original post, A is the symmetric matrix.
To avoid any further confusion, can you tell me more about your problem and the kind of matrices that you have.

Woodbury's formula is useful in the following case.
Let's say that you have a matrix A and you already know its inverse matrix.
Now, if you want to update A by adding another matrix B, such that B has a small rank, the inverse of A+B can be computed by the Woodbury's formula.

After reading your original post once again, I noticed that both your A and B are invertible. This means that they have a full rank. If this is really the case, Woodbury's formula is useless.

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
After reading your original post once again, I noticed that both your A and B are invertible. This means that they have a full rank. If this is really the case, Woodbury's formula is useless.


Yes, unfortunately, both A and B have full rank and B is diagonal. Thanks anyway

Share this post


Link to post
Share on other sites
Maybe I wasn't paying attention, but why has everybody abandoned Woodbury's formula all of a sudden?

Quote:
Original post by shaobohou
Quote:
Original post by ury
You might find Woodbury's formula useful.
Please note that it'll only help you if A = UUT, where U is a NxM matrix with M << N.


Hmm, not sure a diagonal matrix can be decomposed into the necessary format

It can over the complex numbers, or even over the reals if B is a positive diagonal matrix. If B = diag(a1, a2, ..., an) then let U = diag(√a1, √a2, ..., √an). As U is also diagonal, it is symmetric and so UUT = B. So Woodbury's formula will apply.
I'm not convinced, though, that application of Woodbury's formula would save you computational time for any reasonably-size matrices.

Matrix sums aren't too friendly with inversion, so I'm afraid I have no suggestions to add.

Regards
Admiral

Share this post


Link to post
Share on other sites
TheAdmiral: your matrix U does not give a solution to UUT=B.

It could be that a general method can be used, say, if AB-1 or BA-1 has a spectral radius or even operator norm under 1?

Share this post


Link to post
Share on other sites
some considerations:

1. A+B is a symmetric matrix itself...therefore, inverting that matrix by method of cofactors (adjoint matrix) can be optimized considering you only have to compute a little more than half the elements.

2. If you can diagonalize A+B, then the diagonalization will break A+B into an orthonormal matrix, times a diagonal matrix, times the transpose of the orthogonal matrix. then, it is elementary to invert the matrix by inverting each element of the diagonal matrix and taking the transpose of each orthonormal matrix.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this