| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Graph Embedding and Extensions: A General Framework for Dimensionality Reduction
January 2007 (vol. 29 no. 1)
pp. 40-51
Over the past few decades, a large family of algorithms—supervised or unsupervised; stemming from statistics or geometry theory—has been designed to provide different solutions to the problem of dimensionality reduction. Despite the different motivations of these algorithms, we present in this paper a general formulation known as graph embedding to unify them within a common framework. In graph embedding, each algorithm can be considered as the direct graph embedding or its linear/kernel/tensor extension of a specific intrinsic graph that describes certain desired statistical or geometric properties of a data set, with constraints from scale normalization or a penalty graph that characterizes a statistical or geometric property that should be avoided. Furthermore, the graph embedding framework can be used as a general platform for developing new dimensionality reduction algorithms. By utilizing this framework as a tool, we propose a new supervised dimensionality reduction algorithm called Marginal Fisher Analysis in which the intrinsic graph characterizes the intraclass compactness and connects each data point with its neighboring points of the same class, while the penalty graph connects the marginal points and characterizes the interclass separability. We show that MFA effectively overcomes the limitations of the traditional Linear Discriminant Analysis algorithm due to data distribution assumptions and available projection directions. Real face recognition experiments show the superiority of our proposed MFA in comparison to LDA, also for corresponding kernel and tensor extensions.
[1] 40 A. Batur and M. Hayes, “Linear Subspaces for Illumination Robust Face Recognition,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 296-301, Dec. 2001.[2] P. Belhumeur, J. Hespanha, and D. Kriegman, “Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 7, pp. 711-720, July 1997.[3] M. Belkin and P. Niyogi, “Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering,” Advances in Neural Information Processing System, vol. 14, pp. 585-591, 2001.[4] Y. Bengio, J. Paiement, P. Vincent, O. Delalleau, N. Roux, and M. Ouimet, “Out-of-Sample Extensions for LLE, ISPMAP, MDS, Eigenmaps, and Spectral Clustering,” Advances in Neural Information Processing Systems, vol. 16, 2004.[5] M. Brand, “Continuous Nonlinear Dimensionality Reduction by Kernel Eigenmaps,” Technical Report 2003-21, Mitsubishi Electric Research Labs, Apr. 2003.[6] F. Chung, “Spectral Graph Theory,” Regional Conf. Series in Math., no. 92, 1997.[7] Y. Fu and T. Huang, “Locally Linear Embedded Eigenspace Analysis,” IFP-TR, Univ. of Illinois at Urbana-Champaign, Jan. 2005.[8] K. Fukunnaga, Introduction to Statistical Pattern Recognition, second ed. Academic Press, 1991.[9] D. Hand, Kernel Discriminant Analysis. Research Studies Press, 1982.[10] X. He, S. Yan, Y. Hu, P. Niyogi, and H. Zhang, “Face Recognition Using Laplacianfaces,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 3, pp. 328-340, Mar. 2005.[11] I. Joliffe, Principal Component Analysis. Springer-Verlag, 1986.[12] J. Luettin and G. Maitre, “Evaluation Protocol for the Extended M2VTS Database (XM2VTS),” DMI for Perceptual Artificial Intelligence, 1998.[13] J. Ham, D. Lee, S. Mika, and B. Schölkopf, “A Kernel View of the Dimensionality Reduction of Manifolds,” Proc. Int'l Conf. Machine Learning, pp. 47-54, 2004.[14] A.M. Martinez and A.C. Kak, “PCA versus LDA,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 2, pp. 228-233, Feb. 2001.[15] B. Moghaddam, T. Jebara, and A. Pentland, “Bayesian Face Recognition,” Pattern Recognition, vol. 33, pp. 1771-1782, 2000.[16] K. Muller, S. Mika, G. Riitsch, K. Tsuda, and B. Schölkopf, “An Introduction to Kernel-Based Learning Algorithms,” IEEE Trans. Neural Networks, vol. 12, pp. 181-201, 2001.[17] Olivetti & Oracle Research Laboratory, The Olivetti & Oracle Research Laboratory Face Database of Faces, http://www.cam-orl.co.ukfacedatabase.html , 1994.[18] S. Roweis and L. Saul, “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” Science, vol. 290, no. 22, pp. 2323-2326, Dec. 2000.[19] T. Sim, S. Baker, and M. Bsat, “The CMU Pose, Illumination, and Expression Database,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 12, pp. 1615-1618, Dec. 2003.[20] J. Tenenbaum, V. Silva, and J. Langford, “A Global Geometric Framework for Nonlinear Dimensionality Reduction,” Science, vol. 290, no. 22, pp. 2319-2323, Dec. 2000.[21] Y. Teh and S. Roweis, “Automatic Alignment of Hidden Representations,” Advances in Neural Information Processing System, vol. 15, pp. 841-848, 2002.[22] M. Turk and A. Pentland, “Face Recognition Using Eigenfaces,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 586-591, 1991.[23] M. Vasilescu and D. Terzopoulos, “TensorTextures: Multilinear Image-Based Rendering,” ACM Trans. Graphics, vol. 23, no. 3, pp.336-342, 2004.[24] X. Wang and X. Tang, “Dual-Space Linear Discriminant Analysis for Face Recognition,” Proc. Computer Vision and Pattern Recognition, vol. 2, pp. 564-569, 2004.[25] D. Xu, S. Yan, L. Zhang, Z. Liu, and H. Zhang, “Coupled Subspaces Analysis,” Microsoft Research Technical Report, MSR-TR-2004-106, Oct. 2004.[26] S. Yan, D. Xu, Q. Yang, L. Zhang, X. Tang, and H. Zhang, “Discriminant Analysis with Tensor Representation,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 526-532, 2005.[27] S. Yan, D. Xu, L. Zhang, B. Zhang, and H. Zhang, “Coupled Kernel-Based Subspace Learning,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 645-650, 2005.[28] S. Yan, H. Zhang, Y. Hu, B. Zhang, and Q. Cheng, “Discriminant Analysis on Embedded Manifold,” Proc. Eighth European Conf. Computer Vision, vol. 1, pp. 121-132, May 2004.[29] J. Yang, D. Zhang, A. Frangi, and J. Yang, “Two-Dimensional PCA: A New Approach to Appearance-Based Face Representation and Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 1, pp. 131-137, Jan. 2004.[30] J. Ye, “Generalized Low Rank Approximations of Matrices,” Proc. Int'l Conf. Machine Learning, pp. 895-902, 2004.[31] J. Ye, R. Janardan, and Q. Li, “Two-Dimensional Linear Discriminant Analysis,” Advances in Neural Information Processing Systems, vol. 17, pp. 1569-1576, 2005.[32] J. Ye, R. Janardan, C. Park, and H. Park, “An Optimization Criterion for Generalized Discriminant Analysis on Undersampled Problems,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 982-994, Aug. 2004.[33] H. Yu and J. Yang, “A Direct LDA Algorithm for High Dimensional Data-with Application to Face Recognition,” Pattern Recognition, vol. 34, pp. 2067-2070, 2001.
Index Terms:
Dimensionality reduction, manifold learning, subspace learning, graph embedding framework.
Citation:
Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Qiang Yang, Stephen Lin, "Graph Embedding and Extensions: A General Framework for Dimensionality Reduction," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 40-51, Jan. 2007, doi:10.1109/TPAMI.2007.12
