Principal Component Analysis (PCA)
PCA is a dimensionality reduction algorithm used to reduce dimensions in large unlabeled data. It is one of the key algorithms in unsupervised machine learning.
 
Mathematical Analysis of PCA
The principle components are computed by calculating the Eigen Values and Eigen Vectors of a data Covariance Matrix . In mathematical terms, PCA is equivalent to finding the axis where the covariance matrix is diagonal. The Eigen vector with highest Eigen value represents the direction of the greatest variance, the one with next Eigen Vector is orthogonal (at 90° to one another) to the first Eigen value. This continues on and on further.
 
  Vector Representation of PCA
  Refer 18
 
Eigen Values and Eigen Vectors
A is a m x n matrix. The Eigen Values of A is defined as the roots of the equation
 
   determinant(A - λI), represented by equation
   | (A - λI) | = 0
   The above polynomial equation has n roots.
   λ represents the Eigen value of matrix A, such that Ax = λx, where x represents the Eigen Vector.
   I in the equation |(A - λI)| = 0, is a n x n identity matrix
   for 2 x 2 matrix it is |[1 0, 0 1]|.
 
 
Below is a table of some data [2 x 2] that we can use for PCA analysis.
 
  Sample Data for PCA Analysis
 
For the above data, we need to compute variance VAR() and covariance COV(). Variance and covariance are computed for the sample data, which is (n - 1) = (6 - 1 = 5). 
AVG(x) = (1+2+3+4+5+6)/6 = 3.5

AVG(y) = (6+8+4+5+3+4)/6 = 5.0

For all values of x and y

VAR(x) = SUM((xi - AVG(x))2)/(n-1)
       = ((1-3.5)2+(2-3.5)2+(3-3.5)2+(4-3.5)2+(5-3.5)2+(6-3.5)2)/5
       = (6.25+2.25+0.25+0.25+2.25+6.25)/5
       = 17.5/5 
       = 3.5

VAR(y) = SUM((yi - AVG(y))2)/(n-1)
       = ((6-5)2+(8-5)2+(4-5)2+(5-5)2+(3-5)2+(4-5)2)/n-1
       = (1+9+1+0+4+1)/5
       = 16/5 
       = 3.2

COV(x,y) = (SUM(x * y) - SUM(y) * SUM(x)/n)/n-1

COV(x,y) = (93 - 30 x (21)/6)/6-1
         = (93 - 105)/5 
         = -2.4

Covariance matrix is

| VAR(x)     COV(x,y) |     |  3.5    -2.4 |
|                     |  =  |              |
| COV(x,y)   VAR(y)   |     | -2.4     3.2 |

Next step is to compute Eigen values by
Eigen decomposition on the Covariance matrix.

It is formulated as Av = λv

This can solved as (A - λI)v = 0

In determinant form it is det(A - λI) = 0

|  3.5   -2.4 |     | 1    0 |
|             | - λ |        | = 0
| -2.4    3.2 |     | 0    1 |


|  3.5   -2.4 |   | λ    0 |
|             | - |        | = 0
| -2.4    3.2 |   | 0    λ |

We can substitute and simplify λ = x

|  3.5   -2.4 |   | x    0 |
|             | - |        | = 0
| -2.4    3.2 |   | 0    x |

|  3.5-x    -2.4  |
|                 | = 0
| -2.4      3.2-x |

(3.5 - x) (3.2 - x) - (-2.4)(-2.4) = 0

11.2 - 3.5x -3.2x + x2 - 5.76 = 0

This becomes 

x2 - 6.7x + 5.44 = 0

Using the solution shown for the quadratic equation 
ax2 + bx + c = 0,

we get the Eigen values (λ = x) as

x = 5.755
x = 0.945

Having known the two Eigen values, we can 
compute Eigen vectors.

A1v1 = λ1v1

For λ = 5.755

| 3.5 - 5.755       -2.4    | | v11 |
|                           | |     | = 0
| -2.4          3.2 - 5.755 | | v21 | 


| -2.25    -2.4  | | v11 |
|                | |     | = 0
| -2.4     -2.55 | | v21 | 

A2v2 = λ2v2

For λ = 0.945

| 3.5 - 0.945       -2.4    | | v21 |
|                           | |     | = 0
| -2.4          3.2 - 0.945 | | v22 | 


| 2.55     -2.4  | | v21 |
|                | |     | = 0
| -2.4      2.25 | | v22 |
To further solve for Eigen Vectors, tools such as MATLAB is recommended (PCA MATLAB Animation of wine data).
 
Shown below is a [4 x 4] covariance matrix. In the same way the matrix can be generalized for a [m x n] dataset. As the matrix expands, computational tools are the best way to analyze Eigen Values, Eigen Vectors, PCA and image recognition. This also highlights how the GPU chip power helps in analysis of very large datasets.

  x1 x2 x3 x4
x1 VAR(x1) COV(x1,x2) COV(x1,x3) COV(x1,x4)
x2 COV(x2,x1) VAR(x2) COV(x2,x3) COV(x2,x4)
x3 COV(x3,x1) COV(x3,x2) VAR(x3) COV(x3,x4)
x4 COV(x4,x1) COV(x4,x2) COV(x4,x3) VAR(x4)


Realtime Use of PCA
The question asked is, where can this complex analysis be used in real time? When we need certain information, we use search engines such as Google and use textual string in the search box to search. We get answers - URL of websites based on the site ranking used by Google that closely match the search string. It would be great if one could input an image and search for close match. This is where PCA becomes one of the best algorithms to search for images/pattern recognition. This would also be of greatest use in autonomous vehicles to rapidly recognize objects, traffic signals, lights and obstacles etc. in real time.
 
Typically a 2D image needs to be compared with several images and best match needs to be identified. This is a common activity in user authentication, identification of a person of interest and so on. The assumption is that most images have similar resolution and positioned in close location in images - main portrait photo and background. Each pixel in the image is treated as a variable and this results in a very large collection of variables. This high dimension problem is simplified by the use of PCA.
 
Let us consider an input image of n-pixels. It is treated as a point in n-dimension space, termed as image space. The intensity of each pixel represents the individual ordinates in the image space, which forms a row vector. The image pixel values are concatenated to form a row vector Px = (i1,i2,i3,.. in).
 
The vector formed row by row for an image could have a resolution of [128 X 128] resulting in diemnsion of 16384. A high resolution image could result in even extremely large vector and matrix. In an image a large number of of pixels are correlated. The background pixels in an image are relatively same and are correlated to adjacent pixels. For this reason a covariance matrix is created and eigen values and vectors are computed as explained in above example of [2 x 2].
 
When comparing two images, it is lot faster to discard common dimensions (dimension reduction) and compare unique dimensions. Thus closely matching images can be identified, which is very useful image recognition in the areas of crime investigation, authentication and so on.


ML Algorithms
 
Table of Content


Top


Revised Date: April 16th, 2024