Eigendecomposition, Singular Value Decomposition, and Power Iterations

The objectives are to

 

1.      Find eigenvectors/eigenvalues

2.      Relate the eigen decomposition to Singular Value Decomposition

3.      Power iterations for computing the eigenvector with the largest Eigenvalue.

Now eigendecomposition happens solely to square matrices.

Taking the matrix B multiplied by the eigenvector is equivalent to an eigenvalue multiplied by an eigenvector. The multiplication of a specific vector is equal to the multiplication of a scalar.

There are K eigen values. If there are distinct eigenvalues, this means there are linearly independent eigenvectors. If the given matrix B is symmetric; as a result, we have K orthonormal eigenvectors. The following are some equations that correspond to these eigenvectors. The matrix B can be written as E * lambda * E(transpose).  

 

Bei =λiei = B[e1 e2 e3 … ek] = [e1 …. Ek] * λ identity matrix (diagonals are λ1 … λk). We can also determine

B = EλET or ∑ from i=1 to k of λi Ei (EiT)

A is from a1 to and the rows are x1 transpose to x2 transpose. B = A multiplied by A transpose.

B can be written as U∑VTV∑TUT

The left singular vectors of A turn out to be the eigenvectors of A, and the left singular values, then there are a number of 0 aeigenvalues.

The other case is when B is ATA. Now B is the sum of the outer products of the rows of A. Remember UTU is a diagonal matrix, so then I have the V * diagonal matrix * VT. The eigenvalues are given by the squares of the singular values.

 

Assume a matrix A NxM where N is much greater than A, and we want to find the first principal component, associated with the span of the row of matrix A. B = ATA what is MxM which is a much smaller matrix than A. We just accumulate the outer products of the individual rows of matrix A. 

 

The following algorithm is the Power Iteration Algorithm.

Pick a random C0.

For K = 1 to convergence

Ck = BCk-1/|| BCk-1 ||2

end

V1 = Cend.

BkC0 = V λk g

Singular vectors are λ^(1/2).