PCA contstrained Optimization using Lagrangian Multiplier

Pre Requisite:-

1) knowledge of Co-variance Matrix
2) What is eigen vectors and values and its uses,
3) PCA


Constrained Optimization of PCA using lagrangian Multiplier.

Below in the picture 1 , we have the PCA formulation which is maximizing the variance, our task to find the u such that the obtained u maximizes the variance and we also have a constraint that u'u = 1, which is saying u must be a unit vector.

Before , getting further in Optimizing PCA
first
lets learn a general case for constrained Optimization problem,

General Constraint Optimization Problem

for any general constraint optimization problem , given that

                                find maximum x* for a function f(x)
                                such that g(x)  =c

then we use the concept of lagrangian Multiplier which says,

L(x,α) = f(x) - α(g(x) -c ) ............. (1)

here , α is called as  lagrangian multiplier.

so , when solving the two equations
partial derivative L(X,α) wrt x =0 ,
partial derivative L(X,α) wrt α =0 ,

then x ,we obtain is the x which maximizes the function f(x)

Detailly shown in picture 1.
 

Picture 1

Now for Principal Component Analysis.

1) We modify our objective function (reference to picture 2) from equation a to equation b using very simple maths.
      
              a) S in equation b is simple co-variance matrix of X ( Training Data Set )

2) Use lagrangian Multiplier (reference to picture 2)

   we get,
          
             Su = α u




     


        


which is the formulation for eigen vector and eigen value , where u is the eigen vector and α is eigen value.

3) so, the Solution of PCA is to take the top eigen value and vector of the co-variance matrix X.(our training data)