6

I would like to take the inverse of a nxn matrix to use in my GraphSlam.

The issues that I encountered:

  • .inverse() Eigen-library (3.1.2) doesn't allow zero values, returns NaN
  • The LAPACK (3.4.2) library doesn't allow to use a zero determinant, but allows zero values (used example code from Computing the inverse of a matrix using lapack in C)
  • Seldon library (5.1.2) wouldn't compile for some reason

Did anyone successfully implemented an n x n matrix inversion code that allows negative, zero-values and a determinant of zero? Any good library (C++) recommendations?

I try to calculate the omega in the following for GraphSlam: http://www.acastano.com/others/udacity/cs_373_autonomous_car.html

Simple example:

[ 1 -1  0 0 ]
[ -1 2 -1 0 ]
[ 0 -1  1 0 ]
[ 0  0  0 0 ]

Real example would be 170x170 and contain 0's, negative values, bigger positive values. Given simple example is used to debug the code.

I can calculate this in matlab (Moore-Penrose pseudoinverse) but for some reason I'm not able to program this in C++.

A = [1 -1 0 0; -1 2 -1 0; 0 -1 1 0; 0 0 0 0]
B = pinv(A)
B=
[0.56   -0.12  -0.44  0]
[-0.12  0.22   -0.11  0]
[-0.44  -0.11   0.56  0]
[0  0  0   0]

For my application I can (temporarily) remove the dimension with zero's.
So I am going to remove the 4th column and the 4th row.
I can also do that for my 170x170 matrix, the 4x4 was just an example.

A:

[ 1 -1  0 ]
[ -1 2 -1 ]
[ 0 -1  1 ]

So removing the 4th column and the 4th row wouldn’t bring a zero determinant. But I can still have a zero determinant if my matrix is as above. This when the sum of each row or each column is zero. (Which I will have all the time in GraphSlam)

The LAPACK-solution (Moore-Penrose Inverse based) worked if the determinant was not zero (used example code from Computing the inverse of a matrix using lapack in C).
But failed as a "pseudoinverse" with a determinant of zero.

SOLUTION: (all credits to Frank Reininghaus), using SVD(singular value decomposition)
http://sourceware.org/ml/gsl-discuss/2008-q2/msg00013.html

Works with:

  • Zero values (even full 0 rows and full 0 columns)
  • Negative values
  • Determinant of zero

A^-1:

[0.56   -0.12  -0.44]
[-0.12  0.22   -0.11]
[-0.44  -0.11   0.56]
Community
  • 1
  • 1
Toon
  • 19
  • 1
  • 1
  • 3
  • What's wrong with Gaussian elimination? – Kerrek SB Dec 17 '12 at 18:12
  • Could you include one specific example of a small matrix that none of these would be able to invert? (I assume the matrix is non-singular.) – NPE Dec 17 '12 at 18:13
  • With Gaussian elimination there is still a possibility to have negative and 0 values in your outcome no? – Toon Dec 17 '12 at 18:24
  • 4
    Your example matrix has determinant equals zero. This is not an invertible matrix. I hope you don't try on this one! – ritter Dec 17 '12 at 18:25
  • Can you make this title make sense? Matrices with zero determinant don't have inverses. – djechlin Dec 17 '12 at 20:02

4 Answers4

7

If all you want is to solve problem of the form Ax=B (or equivalently compute products of the form A^-1 * b), then I recommend you not to compute the inverse or pseudo-inverse of A, but directly solve for Ax=b using an appropriate rank-revealing solver. For instance, using Eigen:

x = A.colPivHouseholderQr().solve(b);
x = A.jacobiSvd(ComputeThinU|ComputeThinV).solve(b);
ggael
  • 28,425
  • 2
  • 65
  • 71
5

Your Matlab command does not calculate the inverse in your case because the matrix has determinat zero. The pinv commmand calculates the Moore-Penrose pseudoinverse. pinv(A) has some of, but not all, the properties of inv(A).

So you are not doing the same thing in C++ and in Matlab!

Previous

As in my comment. Now as answer. You must make sure that you invert invertible matrices. That means

det A != 0

Your example matrix has determinant equals zero. This is not an invertible matrix. I hope you don't try on this one!

For example a given matrix has determinant zero if there is a full row or column of zero entries.

finnw
  • 47,861
  • 24
  • 143
  • 221
ritter
  • 7,447
  • 7
  • 51
  • 84
  • My bad. For my application (GraphSlam) the sum of all the values on every line will be equal to zero. But in their code they are still able to invert that omega matrix. – Toon Dec 17 '12 at 18:32
  • If only the sum of each row is zero that does not say anything about its determinant. At least I don't see it quickly ;-) – ritter Dec 17 '12 at 18:36
  • You are trying to solve the linear equation `X=AY`. You can certainly ask for the inverse of A for a general solution to the problem which requires `det A!=0`. However, the linear equation is still solvable with a zero determinant of `A`. Then the solution space has dimension greater 0. Thus a whole subvector-space as possible solutions. I would recommend first testing the determinant and then decide how to solve the linear equation: Inversion, gaussian elimination, etc. – ritter Dec 17 '12 at 18:53
  • Ok, the issue is more clear now, I will start to dig into Moore-Penrose pseudoinverse in c++. I wasn’t really sure what the issue was. Now I know I cannot use normal inversion, but have to do pseudo-inverse. And matlab uses Moore-Penrose pseudo inverse and is able to get descent results. – Toon Dec 17 '12 at 19:03
  • Exactly, it's not the pseudo-inverse you are trying to calculate in your C++ program. – ritter Dec 17 '12 at 19:08
2

Are you sure it's because of the zero/negative values, and not because your matrix is non-invertible?

A matrix only has an inverse if its determinant is nonzero (mathworld link), and the matrix example you posted in the question has a zero determinant and so it has no inverse.

That should explain why those libraries do not allow you to take the inverse of the matrix given, but I can't say if the same reasoning holds for your full size 170x170 matrix.

je4d
  • 7,628
  • 32
  • 46
0

If your matrixes is kind of covariance or weight matrices you can use "generalized cholesky inversion" instead of SVD. The results will be more acceptable for practical use

minorlogic
  • 1,872
  • 1
  • 17
  • 24