Revising singular value decomposition – Part 1

Few days before I had small issues in understanding the internal workings of SVD. The Worst part is I have already done few projects which has SVD as a major module. This is the time I decided to revisit and recall every thing I need to know about decomposition techniques (Well, this is also he time I realized why missed to document about SVD so long ago).

svd-img

Today there is a lot of decomposition technique available to solve the statistical problems, however most popular and widely used decomposition technique are.

  1.  Eigenvalue decomposition
  2.  Singular value decomposition (SVD)
  3.  Principal component analysis (PCA)

And this post is dedicated for laymen who like to understand the internal workings of Singular value decomposition.

The word decomposition means reduction or breaking down, as the name indicates SVD is one the best factorization (decomposition) technique available for the matrix.

In simpler terms factorization help to break the bigger matrix into small entities such that when multiplying the entities we get the original matrix.  

Example, a matrix AMxN can be broken down and written in a form A = UDVt. Such that when multiplying U * D * vt we get the same matrix A.

matrix-svd

In this representation A = UDVt, U and Vare orthogonal matrix and D is diagonal matrix whose diagonal entries are (d1, d2 …. dn) eigenvalues of the original matrix A.

Proof

Theatrically to believe A = UDVt we need an accurate publishable proof.

To prove A = UDVt.Let say A=UDVT and apply transpose on both side equation to get At = UtDV.

Now we have two equations

A = UDVt

At = VDUt (For the sake of convince I have rearranged UtDV into VDUt)

Having these equations in hand, if we prove the result of AAt is exactly equal to UtDV * VDUt then our A = UDVt assumption is correct and holds good.

AtA = VDUtUDVt

AtA = VD2Vt

AtAV = VD2

Algorithm

To compute SVD find eigenvalues and eigenvectors of AAt and AtA.

Compute U : Find eigenvalues of matrix AAt, from eigenvalues compute eigenvector which is U.

Compute Vt : Find eigenvalue of matrix AtA, from eigenvalues compute eigenvectors which is Vt.

Compute D : Compute the square root of the common positive eigenvalues of AAt and AtA.

Assign computed values to U, V, and D.

Let try with an example. Let A be matrix. 

a

aat ata

Using eigenvalues from AAt U matrix is produced. 

u

Using eigenvalues from AtA V matrix is produced.

v

S is diagonal matrix produced from common positive eigenvalues of AAt and AtA

d

Continue with part 2 –  Low-rank-matrix-approximation-svd

Reference 

http://www.informatik.uni-konstanz.de/fileadmin/informatik/ag-saupe/Webpages/lehre/na_08/Lab1/8_SVD/html/SVD_05.png 

http://en.wikipedia.org/wiki/Singular_value_decomposition 

http://web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm


Post a Comment

Your email is never published nor shared. Required fields are marked *