A proposal for a cheap implementation for the Penrose-pseudoinverse

This is an attempt to implement a method along the idea of Adam W. in MSE, 27.2.2013, using the notation in the matrix-language/software MatMate.

Gottfried Helms/Univ Kassel 27.2.2013 .

We want to find the left-inverse for a n x m - matrix, where m<n . As an example we use a 6x4 random-matrix A

A :

 –6.7475 –0.3647 –0.1494 0.0162 –3.4101 –7.0163 7.7587 –9.5665 –0.6796 7.4867 6.5455 1.8587 –5.0669 –4.2541 –9.5941 –9.8070 6.5135 5.4551 –7.1789 5.4896 –4.4194 9.5292 –7.1299 3.0132

If we would do this along the SVD-decomposition, this would be costful because we needed iterative methods to find the left and right diagonalizing rotation-matrices, which requires either two eigen-decompositions or two iterative Jacobi-rotations towards orthogonality in rows and in columns.

Conversely in this proposal it suffices to rotate the rows only, and also it suffices to rotate them non-iteratively such that A simply gets into upper triangular shape.

We need that rotation later so we append a 6x6-unit-matrix unit(6) to the right of A. In MatMate we have only column-rotations so we need also to transpose that aggregate such that we have a 10 x 6 – matrix, which gets column-rotated and then backtransposed to 6 x 10 :

[19]    tmp = rotate( (A || unit(6)) ' , "triangular") '

Note, that the applied rotation is saved by this in the rightmost 6x6 submatrix now.

Then we need only the 4 rows of it, call the resulting submatrix C :

[20]     C = tmp[1..4,*]

we see, that the rotated submatrix A has become upper triangular in the left, white area. The yellow area is the matrix t which contains the applied rotation.

C :

 12.052 3.0097 0.2875 8.578 –0.5599 –0.2829 –0.0564 –0.4204 0.5405 –0.3667 0 15.3302 –4.7314 10.1494 0.0861 –0.4021 0.4994 –0.1950 0.2497 0.6936 0 0 16.5835 1.0065 0.0253 0.3580 0.5382 –0.6269 –0.3710 –0.2257 0 0 0.0 7.2635 0.5396 –0.4706 –0.4500 –0.4944 –0.1800 –0.0900

After that we need only three Gaussian-eliminations, beginning with the pivot (4,4) and involving the above rows:

[22]     C = gausselim(C , {4,4},1..3)

C :

 12.052 3.0097 0.2875 0 –1.1971 0.2728 0.4750 0.1634 0.7531 –0.2604 0 15.3302 –4.7314 0 –0.6678 0.2555 1.1282 0.4959 0.5013 0.8193 0 0 16.5835 0 –0.0495 0.4232 0.6005 –0.5584 –0.3461 –0.2132 0 0 0.0 7.2635 0.5396 –0.4706 –0.4500 –0.4944 –0.1800 –0.0900

… now with pivot (3,3) and involving the above two rows

[23] C = gausselim( C , {3,3},1..2)

C :

 12.052 3.0097 0 0 –1.1962 0.2655 0.4646 0.1731 0.7591 –0.2567 0 15.3302 0 0 –0.6819 0.3762 1.2995 0.3365 0.4026 0.7585 0 0 16.5835 0 –0.0495 0.4232 0.6005 –0.5584 –0.3461 –0.2132 0 0 0 7.2635 0.5396 –0.4706 –0.4500 –0.4944 –0.1800 –0.0900

Finally with pivot (2,2) and involving the remaining upper row:

[24] C = gausselim( C , {2,2},1..1)

C :

 12.052 0 0 0 –1.0623 0.1916 0.2095 0.1070 0.6800 –0.4056 0 15.3302 0 0 –0.6819 0.3762 1.2995 0.3365 0.4026 0.7585 0 0 16.5835 0 –0.0495 0.4232 0.6005 –0.5584 –0.3461 –0.2132 0 0 0 7.2635 0.5396 –0.4706 –0.4500 –0.4944 –0.1800 –0.0900

We see, that the left white segement is diagonal now; to make it a unit-matrix we scale the rows by the inverses of the diagonal:

[25] D = 1 /# diag(C2)  *# C    // the #-sign at the mathematical operators indicates elementwise operation

D :

 1 0 0 0 –0.0881 0.0159 0.0174 0.0089 0.0564 –0.0337 0 1 0 0 –0.0445 0.0245 0.0848 0.0220 0.0263 0.0495 0 0 1 0 –0.0030 0.0255 0.0362 –0.0337 –0.0209 –0.0129 0 0 0 1 0.0743 –0.0648 –0.0619 –0.0681 –0.0248 –0.0124

… and in the yellow area we have the pseudoinverse of A, let's call it V:

[26] V = D [*,5..10]

We check it by multiplication V*A should be the unit matrix

[27] chk = V*A

chk :

 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

email to the author: helms(at)uni-kassel.de