fast matrix inverse
Author
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?
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.
Please note that it'll only help you if A = UUT, where U is a NxM matrix with M << N.
Author
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
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.
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.
Author
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
Maybe I wasn't paying attention, but why has everybody abandoned Woodbury's formula all of a sudden?
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
Quote:Original post by shaobohouQuote: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
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?
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?
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
