6
$\begingroup$

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.$$

  • 0
    Do you have $\mathbf A$, or just $\mathbf M$?2012-08-15
  • 1
    Your $\mathbf B$ is in fact expressible in terms of the Moore-Penrose pseudoinverse, of which much has been written about...2012-08-15
  • 0
    @J.M. - I have the "A" matrix2012-08-15
  • 0
    Then chao's solution would be most appropriate to your circumstances.2012-08-15
  • 0
    Thanks. I've already started implementing Cholesky (which vectorises easily with SSE), I'll give SVD a go later though since I'll need to implement it anyway soon in another project.2012-08-15
  • 0
    @MarkKCowan have you tried the opencv library for using Cholesky or are you using matlab or something ?2013-03-06
  • 0
    @Ritwik G: I've implemented Cholesky in C2013-03-07

3 Answers 3

4

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.

  • 0
    Just to let you know that Cholesky worked a charm, thank you!2013-07-03
3

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$.

  • 1
    "...the pseudo-inverse has inversed singular values..." - if none of the singular values are zero, of course.2012-08-15
  • 0
    @J.M. you are right. Answer edited.2012-08-15
  • 0
    Thanks - I've not done much linear algebra since I started university (6 years ago...) so it'll take me a while to research and digest your suggestions - hopefully by the time I've tried and compared them I'll have enough rep to give your answers the appropriate votes!2012-08-15
1

$ B = \left(A A^\top\right)^{-1}A = \left(A A^\top\right)^{-1}A A^\top \left(A^\top\right)^{-1} = \left(A A^\top\right)^{-1}A A^\top \left(A^\top\right)^{-1} = I \left(A^\top\right)^{-1} = A^{-\top} $

  • 1
    Please add some english prose to your answer and consider formatting the mathematics in LaTeX.2013-07-02
  • 0
    @Xiang you can wrap the math in dollar signs. The carats do work for powers, but if you have anything more complex than a single character in a power, you need to gather it all together with {} so that it will all become a superscript.2013-07-02
  • 1
    This only applies if $A$ is a square matrix, which I explicitly stated that it is not. Also, a tidier proof (for a square matrix $A$) would be: $B = \left(A A^\top\right)^{-1}A = A^{-\top} A^{-1} A = A^{-\top}$2013-07-03