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:**

- centralize the sample: $x_i \leftarrow x_i - \frac{1}{m} \sum_{i=1}^{m} x_i$;
- compute the covariance matrix of the sample: $XX^T$;
- compute eigen values of the covariance matrix $XX^T$;
- 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(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.**

- 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;
- 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;
- 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)
- Project the matrix to the new k-dimension feature;
- Train our One-VS-One Multiclass SVM model;
- Read the test images, then do 1 and 2 to form our test data;
- Use the trained model to classify test data;
- Compute the accuracy.

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