Singular Value Decomposition (Mathematical Overview)

We are talking about SVD and it is the single most important decomposition in linear algebra.

Let us say we have a matrix X which a collection of data column vector x1, x2,..., xm.

There are a couple of examples from where this matrix could come from.

For example:
I could take a bunch of pictures of people's faces.
Let us say we have a picture of a person's face.

We reshape that image into a tall million by 1 column vector.
And so on and so forth till m.

xn lies in Rn 



Another example could that this could a matrix coming from physical system. I have some fluid flow around circle, and we are generating this data with time repeatedly.

Each state is represented in the form of column vector of shape n X 1.



Through SVD:

We take this matrix X and we represent this matrix as a product of three other matrices.

X = (U)(Sigma)(V-Transpose)

The U matrix and V matrix are called Unitary matrices or Orthogonal matrices. 
The matrix Sigma is a diagonal matrix.

On writing it again in Matrix form:

U is an n-by-n matrix.

In matrix Sigma, there will only be 'm' non-zero diagonal values as there are only 'm' rows in matrix X. Everything else is zero.

Last matrix is this V-transpose.
V = [v1, v2, v3,..., vm]



We are taking are data matrix X and represent in the form of U, Sigma, and V.

The columns of U have the same shape as columns of X so if x1 million-by-1 vector then u1 is also a million-by-1 vector.

Column vectors in U are Eigen faces and u1 is more important than u2 and so on, so forth. They give us a basis to represent our original matrix X.

Column vector are heirarchically arranged representing the variance that goes column by colun in the vector X.

U and V are unitary.
That means:
(U-transpose)(U) = (U)(U-transpose) = I (identity matrix) of shape nXn

U is orthogonal that means:
U-transpose == U-inverse 

For V:

(V-transpose)(V) = (V)(V-transpose) = I (identity matrix) of shape mXm

For Sigma:

It is a diagonal matrix.
It is non-negative and heirarchical.

sig1 >= sig2 >= sig3 >= sig4 >= ... >= sigm >= 0

These heirarchichal property leads us to:
u1, sig1 and v1 are more important than u2, sig2 and v2, and so on and so forth.

The relative importance of each column vector is given by the values in the Sigma matrix.

U -> Left Singular Vectors
V -> Right Singular Vectors
X -> Singular Values

Values in X are orderdered by importance.

If some of the Sigma values sig-n are very, very small, then we can ignore them and chop our matrices into dominant columns of U and V.

Now: Eigen Faces.

X was representing a human face.
Since, u1, u2, etc are of same size of vector x1, x2, and so on and so forth. 
That implies: Vectors u1, u2, u3... can be reshaped into Eigen Faces.

Columns of V:
Taking the example of Eigen fluid flow in time:

U would be energy vectors (Eigen flows) u1, u2, u3,...

In V: v1 would essentially be the time series for the first mode u1.
v2: is how much eigen fluid differs in time after t1.
V: Eigen Time Series 

In case of human faces

V-transpose:
[
 [v1-transpose]
 [v2-transpose]
 [v3-transpose]
]

A column in V-transpose:
would tell me of all of those Eigen faces to add them upto x1.
v1-transpose can understood as: mixtures of U's used to make X's

SVD is guaranteed to exist. And, it is unique.

Tags: Technology,Mathematical Foundations for Data Science,Machine Learning,