[Paper Reading] Graph Embedding and Extensions: A General Framework for Dimensionality Reduction

Problem Definition

Propose a general framework for dimensionality reduction

Introduction

• Linear models: Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA) Locality Preserving Projections (LPP)
• Nonlinear models: ISOMAP, LLE, and Laplacian Eigenmap
• Kernel trick

Method

Graph Embedding

X: N*m dataset (m is usually very large)>>> N*m’ by a mapping function F

Weighted graph G: {X, W}

Diagonal matrix D and the Laplacian matrix L of a graph G

Linearization

Kernelization

Tensorization

General Framework for Dimensionality Reduction

Related Works and Discussions

Kernel Interpretation and Out-of-Sample Extension

Brand’s Work

Laplacian Eigenmap and LPP

MARGINAL FISHER ANALYSIS

Marginal Fisher Analysis

1. PCA projection. We first project the data set into the PCA subspace by retaining N  Nc dimensions or a certain energy. Let WPCA denote the transformation matrix of PCA.
2. Constructing the intraclass compactness and interclass separability graphs. In the intraclass compactness graph, for each sample xi, set the adjacency matrix Wij ¼ Wji ¼ 1 if xi is among the k1-nearest neighbors of xj in the same class. In the interclass separability graph, for each class c, set the similarity matrix Wp ij ¼ 1 if the pair ði; jÞ is among the k2 shortest pairs among the set fði; jÞ; i 2 c; j 62 cg.
3. Marginal Fisher Criterion. From the linearization of the graph embedding framework (4), we have the Marginal Fisher Criterion which is a special linearization of the graph embedding framework with B ¼ Dp  Wp :

4. Output the final linear projection direction as

w ¼ WPCAw

Kernel Marginal Fisher Analysis

Tensor Marginal Fisher Analysis

EXPERIMENTS

Face Recognition

A Non-Gaussian Case

CONCLUSION

• A general framework known as graph embedding, along with its linearization, kernelization, and tensorization, has been proposed to provide a unified perspective for the understanding and comparison of many popular dimensionality reduction algorithms
• Proposed a novel dimensionality reduction algorithm called Marginal Fisher Analysis by designing two graphs that characterize the intraclass compactness and the interclass separability, respectively, and by optimizing their corresponding criteria based on the graph embedding framework

FUTURE WORK

• To systematically compare all possible extensions of the algorithms mentioned in this paper.
• The combination of the kernel trick and tensorization

Reference

Yan, Shuicheng, et al. “Graph embedding and extensions: A general framework for dimensionality reduction.” IEEE Transactions on Pattern Analysis & Machine Intelligence 1 (2007): 40–51.