metamerist

Friday, September 22, 2006

Linear Algebra for Graphics Geeks (SVD-VIII)


The SVD and the Moore-Penrose Pseudoinverse

Let's look at the SVD and its inverse.

A = USVT

A-1 = (USVT)- 1 =
(VT)-1S-1U-1 =
VS-1UT


Here's the question for this post:

If we substitute the pseudoinverse of S for S-1 in the product above, will we wind up with the pseudoinverse of A?

In other words, is A+ = VS+UT?

The quick answer is yes.

I've read quite a bit on the subject in the past few months, but I don't recall seeing this worked out, so I'm going to do it just for the sake of sanity and entertainment. :)

A few reminders for the sake of clarity:

First, because U and V are orthogonal matrices their inverses and tranposes are the same, which is why either matrix cancels out its transpose (UUT=UTU=VVT=VTV=I). Second, there are several simplifications involving S and S+ that exploit the identities of pseudoinverses. I'll note these when they are applied. Also, the inverse of a matrix product is the reverse product of the individual inverses (likewise with transposes). cf. The Matrix Cookbook.

Matrix A needs to meet four criteria to be a pseudoinverse. Let's substitute USVT for A and VS+UT for A+ and see if everything works out.

Rule #1:

AA+A = A

(USVT)(VS+UT) (USVT) =
US(VTV)S+(UTU) SVT =
U(SS+S)VT =
USVT

note: The last step applies this rule (#1) to (SS+S), which we can do because S+ is a pseudoinverse.


Rule #2:

A+AA+ = A+
(VS+UT)(USVT)(VS+UT) =
VS+(UTU)S(VTV) S+UT =
V(S+SS+)UT =
VS+UT

note: The last step applies this rule (#2) to (S+SS+), which we can do because S+ is a pseudoinverse.


Rule #3:

(AA+)T = AA+

AA+ = (USVT)(VS+UT)
AA+ = USVTVS+UT
AA+ = US(VTV)S+UT
AA+ = USS+UT
AA+ = U(SS+)UT

(AA+)T = (U(SS+)UT)T
(AA+)T = UTT(SS+)TUT
(AA+)T = U(SS+)TUT
(AA+)T = U(SS+)UT

note: The last step applies this rule (#3) to (SS+)T, which we can do because S+ is a pseudoinverse.


Rule #4:

(A+A)T = A+A

A+A = (VS+UT)(USVT)
A+A = VS+(UTU)SVT
A+A = V(S+S)VT

(A+A)T = (V(S+S)VT)T
(A+A)T = VTT(S+S)TVT
(A+A)T = V(S+S)TVT
(A+A)T = V(S+S)VT

note: The last step applies this rule (#4) to (S+S)T, which we can do because S+ is a pseudoinverse.

Finally, let's look at an identity mentioned in a my last post on the subject. This is an important one relating to least squares.

A+ = (ATA)-1AT
A+ = ((USVT)T(USVT))-1(USVT)T
A+ = ((VSTUT)(USVT))-1(VSTUT)
A+ = (USVT)-1(VSUT)-1(VSUT)
A+ = (USVT)-1
A+ = (VT)-1S+U-1
A+ = VS+UT

fin

This is post #10 of Linear Algebra for Graphics Geeks. Here are links to posts #1, #2, #3, #4, #5, #6, #7, #8, #9.

Next: Some insights relating to rotation matrices.

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home