Wednesday, August 30, 2006

Linear Algebra for Graphics Geeks (SVD-V)

This is post #5 of Linear Algebra for Graphics Geeks. Here are links to posts #1, #2, #3, #4. The subject at hand is the Singular Value Decomposition.

Let's look at the equation for the SVD again:

A = U*S*V'

We've already seen how to determine if A is singular by examining the diagonal of S. Now we'll consider the subject of matrix inversion.

One rule of linear algebra will help us here:

The inverse of a matrix product is the same as the reverse product of matrix inverses. (Mathworld: Matrix Inverse)


(ABC)-1 = C-1B-1A-1

Given this rule and A = U*S*V', we have the following:

A-1 = (U*S*V')-1 = V'-1*S-1*U-1

In part #2, we discovered U and V are orthogonal matrices. Because of this, their transposes and their inverses are one and the same. Given that knowledge, we can simplify our inverse equation.

A-1 = (V')-1*S-1*U-1 = V*S-1*U'

(See how easy it is to manipulate the SVD!)

Now all we need to do is figure out how to invert S, which is easy because S is a diagonal matrix (a.k.a. scale matrix). Consider a simple 2x2 scale matrix that scales X by 2 and Y by 3:

[2 0]
[0 3]

What's the inverse of this matrix? It's the matrix that scales X by 1/2 and Y by 1/3:

[1/2 0]
[ 0 1/3]

If we multiply these two together, we get the identity matrix.

[2 0]*[1/2 0] = [2*1/2 0] = [1 0]
[0 3]*[0 1/3] . [0 3*1/3] . [0 1]

The inverse of a diagonal matrix is calculated by replacing each element on the diagonal with its reciprocal.

This makes perfect sense. We covered inversion in one dimension in part #3 with our discussion of inches and centimeters. Naturally this extends to multiple dimensions; e.g., scaling width, height, depth all involve multiplying by some scalar, and reversing the scaling requires multiplication by the inverses of those scalars.

Of course, if any element on the diagonal of S is zero, we will wind up trying to divide by zero when we attempt to invert S; when that happens, it's because A is singular (and therefore S is singular #3). Also, if S is almost singular, some of the elements on the diagonal will be very tiny numbers and their reciprocals will be very huge numbers. In such a case, our inverse may not be very useful.

Next, I discuss eigenvectors, eigenvalues and ways in which they are related to the SVD.


Post a Comment

Subscribe to Post Comments [Atom]

<< Home