| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Generalizing Discriminant Analysis Using the Generalized Singular Value Decomposition
August 2004 (vol. 26 no. 8)
pp. 995-1006
Abstract—Discriminant analysis has been used for decades to extract features that preserve class separability. It is commonly defined as an optimization problem involving covariance matrices that represent the scatter within and between clusters. The requirement that one of these matrices be nonsingular limits its application to data sets with certain relative dimensions. We examine a number of optimization criteria, and extend their applicability by using the generalized singular value decomposition to circumvent the nonsingularity requirement. The result is a generalization of discriminant analysis that can be applied even when the sample size is smaller than the dimension of the sample data. We use classification results from the reduced representation to compare the effectiveness of this approach with some alternatives, and conclude with a discussion of their relative merits.
[1] 995 P.N. Belhumeur, J. Hespanda, and D. Kriegeman, 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.[2] M.W. Berry, S.T. Dumais, and G.W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval SIAM Rev., vol. 37, no. 4, pp. 573-595, 1995.[3] S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman, Indexing by Latent Semantic Analysis J. Am. Soc. for Information Science, vol. 41, pp. 391-407, 1990.[4] R. Duda, P. Hart, and D. Stork, Pattern Classification, second ed. John Wiley&Sons, 2001.[5] K. Fukunaga, Introduction to Statistical Pattern Recognition, second ed. Academic Press, 1990.[6] G.H. Golub and C.F. Van Loan, Matrix Computations, third ed. Johns Hopkins Univ. Press, 1996.[7] P. Howland, M. Jeon, and H. Park, Structure Preserving Dimension Reduction for Clustered Text Data Based on the Generalized Singular Value Decomposition SIAM J. Matrix Analysis Applications, vol. 25, no. 1, pp. 165-179, 2003.[8] P. Howland and H. Park, Equivalence of Several Two-Stage Methods for Linear Discriminant Analysis Technical Report 041, Dept. of Computer Science and Eng., Univ. of Minnesota, 2003.[9] D. Hull, Improving Text Retrieval for the Routing Problem Using Latent Semantic Indexing Proc. 17th Ann. Int'l ACM SIGIR Conf. Research and Development in Information Retrieval, pp. 282-291, 1994.[10] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Prentice Hall, 1988.[11] G. Kowalski, Information Retrieval Systems: Theory and Implementation. Kluwer Academic, 1997.[12] C.L. Lawson and R.J. Hanson, Solving Least Squares Problems. SIAM, 1995.[13] J. Ortega, Matrix Theory: A Second Course. Plenum Press, 1987.[14] C.C. Paige and M.A. Saunders, Towards a Generalized Singular Value Decomposition SIAM J. Numerical Analysis, vol. 18, no. 3, pp. 398-405, 1981.[15] H. Park, M. Jeon, and J.B. Rosen, Lower Dimensional Representation of Text Data Based on Centroids and Least Squares BIT Numerical Math., vol. 42, no. 2, pp. 1-22, 2003.[16] H. Schütze, D. Hull, and J. Pedersen, A Comparison of Classifiers and Document Representations for the Routing Problem Proc. 18th Ann. Int'l ACM SIGIR Conf. Research and Development in Information Retrieval, pp. 229-237, 1995.[17] D.L. Swets and J. Weng, Using Discriminant Eigenfeatures for Image Retrieval IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 8, pp. 831-836, Aug. 1996.[18] S. Theodoridis and K. Koutroumbas, Pattern Recognition. Academic Press, 1999.[19] K. Torkkola, Linear Discriminant Analysis in Document Classification Proc. IEEE ICDM Workshop Text Mining, 2001.[20] C.F. Van Loan, Generalizing the Singular Value Decomposition SIAM J. Numerical Analysis, vol. 13, no. 1, pp. 76-83, 1976.[21] J. Yang and J.Y. Yang, Why Can LDA Be Performed in PCA Transformed Space? Pattern Recognition, vol. 36, no. 2, pp. 563-566, 2003.
Index Terms:
Linear discriminant analysis, latent semantic indexing, principal component analysis, generalized singular value decomposition, QR decomposition, trace optimization.
Citation:
Peg Howland, Haesun Park, "Generalizing Discriminant Analysis Using the Generalized Singular Value Decomposition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 995-1006, Aug. 2004, doi:10.1109/TPAMI.2004.46
