Singular Value Decomposition

notes by Steve Borgatti

1. Review of Correlation of Two Vectors

Suppose A and Y are two column vectors. Suppose they are standardized. What’s the correlation between them?  Sum(AiYi)/n

In matrix or vector notation, this is 1/nA’Y. You remember that A’Y is basically correlation, right? So what is it if mean centered but not standardized?  Sum(AiYi)/(n||A||*||Y||)

In textbooks, you often see A’Y defined as ||A||*||Y||Cos(theta). Theta is the angle between A and Y in geometric space. This tells you that cos(theta) is a measure of correlation, since    ).

[figure 2.6 in textbook]

A’Y has another interpretation as well. It is the projection of A along the axis defined by Y.

2. Multiplying a series of row vectors (collected into a matrix ) by a vector of weights

Let the matrix be X. Let the vector of weights by V. Suppose it has just two columns and n rows. Each row is a row vector. XV is a new vector Z.

So this gives the projection of each row in X onto the dimension defined by V.

[figure 2.8 in textbook]

3. Orthogonality

Two vectors are orthogonal if they are at right angles of each other. We can express this mathematically as A’B = 0. in other words, if the correlation between them is zero. In other words, if the cos of the angle between them is 0.

[figure 2.9 in textbook]

A matrix V of many column vectors is orthogonal if V’V = I. i.e., if every pair of column vectors V1’V2  = 0. if V is standardize by columns, this means the columns are uncorrelated.

4. Rotation of Axes

Suppose X is a matrix of column vectors. And V is an orthogonal matrix. Say column 1 is .707 .707, a 45 deg ray. What vector is orthogonal to it?  -707 707. test it.

[figure 2.9 again]

Suppose we multiply XV to get Z.

What is Z? first column is projection of the row points of X onto coordinate system defined by col 1 of V. 2^nd col is projection of the points onto coord sys defined by col 2 of V. In other words, is a rotation of X to new coordinate system defined by V. is clockwise rotation of points 45 deg. Or counterclockwise rotation of axes by 45 deg.

Called a rigid rotation.  To rotate any specified number of degrees, multiply all points by this:

Cos(theta)        Sin

-Sin                  Cos

Here's some height by weight data:

Plot of the mean-centered data:

Now we rotate by multiplying by

.707    -.707

.707     .707

5. Stretching and Shrinking

We can stretch a picture up and down or left and right by simply multiplying each column of X by some constant > 0. If > 1 then stretch otherwise is shrink. Often expressed by storing the constants in a diagonal matrix D’ and multiplying XD^-1.

For example, let D contain the std deviations of each column in X (which is mean centered). Then multiplying X by D^-1 would adjust the configuration along each axis to have same length

6. SVD

Suppose we rotate and then stretch a data matrix X, to yield U. i.e. U= XVD^-1

Now let’s solve for X.

UD = XV

UDV^-1 = UDV’ = X

X  is nxm, U is nxm, D is mxm and V is mxm as is V’.

Let’s write that differently.

Xij = SUMk( UikDkkVjk)

Xij = U_i1*D₁₁*V_j1 + U_i2*D₂₂*V_j2 + …

Suppose we sort columns of U , the rows and columns of D and columns of V so that the singular values are in descending order. Then we can drop off the ones in which Dkk are small. So we can approximate the matrix:

Xij == U_i1*D₁₁*V_j1 + U_i2*D₂₂*V_j2 + …

X  is nxm, U is nxp, D is pxp and V is mxp

7. Generalized inverse

X = UDV’

X^-1 = (UDV’)^-1

X^-1 = (V’)^-1D^-1U^-1

X^-1 = VD^-1U’

\

So we can compute the inverse of any matrix via svd. Presto.

8. Principal components

• We know any matrix A can be decomposed (via svd) as triple product UDV’.
• When A happens to be square and symmetric (like a correlation matrix or a cross-products matrix), we will find that U = V, so that A = UDU’ or A = VDV’.
• Suppose we compute the cross-products matrix from A. That is, we compute S= A’A. Obviously, we can decompose S into a triple product XGY’. Question is, how does X relate to U, and G to D and Y to V?
• Well, if A = UDV’ then A’A = A’UDV’ = (UDV’)’UDV’ = VDU’UDV’. And since U and V are orthogonal (i.e., columns are independent of each other), U’U = I , so VDU’UDV’ = VD²V’. So svd of A’A gets you VD²V’ (and, similarly, svd of AA’ gets you UD²U’)
• We call the svd of a cross-products matrix (such as correlation matrix) the eigen structure of the matrix. The Us and Vs are called eigenvectors, and the D²s are eigenvalues.

Eigenvectors

• Since S=A’A = VD²V’, then SV = D²V’n. So an eigenvector v of a matrix S is any vector that satisfies this equation:  Sv = λv. It’s a vector which, if pre-multiplied by a vector, gets you the matrix back again (a property called idempotency).
• When S is a correlation matrix (or sometimes a covariance matrix), the eigenvectors of S are referred to as factor loadings

9. Correspondence Analysis

Step 1. normalization of the data. Square root transformation.

Hij = fij/sqrt(fi.)*sqrt(f.j)

Step 2. svd of normalized matrix   H = UDV’

Step 3. rescale the Us and Vs. this part varies.

Xik = Uik/sqrt(f../fi.)

Yjk = Vjk/sqrt(f../f.j)

Fij = fi.f.j/f..(1 + sumk(dk*xik*yjk)

Chisq/n = Sum(dk) for k > 1 (exclude trivial first factor).