Inverse of symmetric matrix $M = A A^\top$

Question

I have a matrix, generated by the product of a non-square matrix with its own transpose:

$$M = A A^\top.$$

I need the inverse of $M$, assuming $\det(M) \neq 0$.

Given the nature of the matrix $M$, are there any specialised computational methods to find its inverse, prioritising precision over speed? Gauss-Jordan is prone to error, and I hope to find something nicer than and with comparable precision to the adj/det method.

$M$ will either have be around $70 \times 70$, or $1000 \times 1000$ in size.

I've had a quick read of the Matrix Cookbook and of this page, but (at the present time of 1 am) I'm struggling to see how it could help me.

In case it helps, I'm actually trying to calculate:

$$B = (A A^\top)^{-1} A.$$

Answer 1

Cholesky decomposition! It's a very stable method and it works on sparse matrices too.

But if you are just trying to solve the normal equation, I may suggest conjugate gradient or SOR.

Answer 2

Actually, you don't need to calculate $(A A^T)^{-1}$ to compute B. What you are trying to calculate is the left inverse of $A^T$, and it is give by

$$B = (AA^T)^{-1} A = {A^{-T}}_L = ((A^T)^T A^T)^{-1} (A^T)^T$$

Since in your case the left inverse exists, it's equivalent to the pseudo-inverse of $A^T$, which can be computed by SVD. And since the left (right) singular vectors of a matrix are right (left) singular vectors of its transpose or left/pseudo inverse, and a matrix and its transpose have the same singular values, but the pseudo-inverse has inversed singular values (non-zeros ones), the pseudo-inverse of $A^T$ has the same singular vectors with A, and has the inversed singular values of $A$.

So, all you have to do is calculating the SVD of $A$, and inversing it's non-zero singular values, then you will get $B$.