Feature extraction via generalized uncorrelated linear discriminant analysis

ABSTRACT

Feature extraction is important in many applications, such as text and image retrieval, because of high dimensionality. Uncorrelated Linear Discriminant Analysis (ULDA) was recently proposed for feature extraction. The extracted features via ULDA were shown to be statistically uncorrelated, which is desirable for many applications. In this paper, we will first propose the ULDA/QR algorithm to simplify the previous implementation of ULDA. Then we propose the ULDA/GSVD algorithm, based on a novel optimization criterion, to address the singularity problem. It is applicable for undersampled problem, where the data dimension is much larger than the data size, such as text and image retrieval. The novel criterion used in ULDA/GSVD is the perturbed version of the one from ULDA/QR, while surprisingly, the solution to ULDA/GSVD is shown to be independent of the amount of perturbation applied. We did extensive experiments on text and face image data to show the effectiveness of ULDA/GSVD and compare with other popular feature extraction algorithms.

REFERENCES

• 1: Dudoit, S., Fridlyand, J., & Speed, T. P. (2002). Comparison of discrimination methods for the classification of tumors using gene expression data. Journal of the American Statistical Association, 97, 77--87.
• 2: Friedman, J. (1989). Regularized discriminant analysis. Journal of the American Statistical Association, 84, 165--175.
• 3: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 4: Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Baltimore, MD, USA: The Johns Hopkins University Press. Third edition.
• 5: Peg Howland , Moongu Jeon , Haesun Park, Structure Preserving Dimension Reduction for Clustered Text Data Based on the Generalized Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, v.25 n.1, p.165-179, 2003 [doi>10.1137/S0895479801393666]
• 6: Jin, Z., Yang, J. Y., Hu, Z.-S., & Lou, Z. (2001a). Face recognition based on the uncorrelated discriminant transformation. Pattern Recognition, 34, 1405--1416.
• 7: Jin, Z., Yang, J.-Y., Tang, Z.-M., & Hu, Z.-S. (2001b). A theorem on the uncorrelated optimal discriminant vectors. Pattern Recognition, 34, 2041--2047.
• 8: Jolliffe, I. T. (1986). Principal component analysis. New York: Springer-Verlag.
• 9: Krzanowski, W., Jonathan, P., McCarthy, W., & Thomas, M. (1995). Discriminant analysis with singular covariance matrices: methods and applications to spectroscopic data. Applied Statistics, 44, 101--115.
• 10: Paige, C., & Saunders, M. (1981). Towards a generalized singular value decomposition. SIAM Journal on Numerical Analysis, 18, 398--405.
• 11: Park, H., Jeon, M., & Rosen, J. (2003). Lower dimensional representation of text data based on centroids and least squares. BIT, 43, 1--22.
• 12: Porter, M. (1980). An algorithm for suffix stripping program. Program, 14, 130--137.
• 13: Daniel L. Swets , John Weng, Using Discriminant Eigenfeatures for Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.831-836, August 1996 [doi>10.1109/34.531802]