# PCA Introduction

PCA(Principal Component Analysis) is a common method for Dimensionality Reduction.

Algorithm Procedure

• Input: Sample set $D=\{x_1, x_2, …, x_m\}$, Lower dimension $d’$
• Process:
1. centralize the sample: $x_i \leftarrow x_i - \frac{1}{m} \sum_{i=1}^{m} x_i$;
2. compute the covariance matrix of the sample: $XX^T$;
3. compute eigen values of the covariance matrix $XX^T$;
4. extract top $d’$-th eigen values and its corresponding eigen vectors $w_1, w_2, …, w_{d’}$.
• Output: Projection matrix $W = (w_1, w_2, …, w_{d’})$ .

In this example, I use PCA algorithm to do Dimensionality Reduction among face pictures：the origin size of face pictures are $112 \times 92$ , which will be vectorize to $112 \times 92 = 10304$ dimensional vectors. Using PCA to reduce the dimension of these vectors for our face matching later.

# SVM Introduction

SVM(Support Vector Machine) is a binary classification method.

The hyperplane for classification is:

Its objective function for optimization is: ( $\alpha_i$ is the Lagrange Multiplier)

$\phi(x)$ can map $x$ to a high dimension. $K(x_i, x_j) = \phi(x_i)\cdot\phi(x_j)$ is the Kernel Function, which is used for some nonlinear classifier. Here is a list of common kernel functions:

Name Expression
Linear kernel function $K(x_i, x_j) = x_i^T x_j$
Gaussian kernel function $K(x_i, x_j) = exp(-\frac{\Vert x_i - x_j \Vert ^2}{\delta^2})$

In this example, I will use an One-VS-One Multiclass SVM method to classify the low-dimension features which we extract from PCA.

# Face Recognition Procedure

1. Vectorize every face picture ($m, n$) to ($m\times n, 1$). Suppose we have $l$ images, vectorize each image as a vector, then stack them togther, then we get a $(m \times n, l)$ matrix as our initial matrix;
2. Centralize this matrix: compute the average of each row form a $(m \times n, 1)$ dimension vector, then let each column minus this vector to get the centralized matrx;
3. Calculate the covariance matrix of the centralized matrix, and get its eigen values and eigen vectors, then we sort the top-k of them from largest to smallest; (we get a k-dimension eigen values here)
4. Project the matrix to the new k-dimension feature;
5. Train our One-VS-One Multiclass SVM model;
6. Read the test images, then do 1 and 2 to form our test data;
7. Use the trained model to classify test data;
8. Compute the accuracy.

# Code

For implementation details, please visit https://github.com/techping/pca-face-recognition .