×

A new perspective to null linear discriminant analysis method and its fast implementation using random matrix multiplication with scatter matrices. (English) Zbl 1234.62100

Summary: The null linear discriminant analysis (LDA) method is a popular dimensionality reduction method for solving small sample size problems. The implementation of the null LDA method is, however, computationally very expensive. We theoretically derive the null LDA method from a different perspective and present a computationally efficient implementation of this method. Eigenvalue decomposition (EVD) of \(S_T^{+} S_B\) (where \(S_{B}\) is the between-class scatter matrix and \(S_T^{+}\) is the pseudoinverse of the total scatter matrix \(S_{T}\)) is shown here to be a sufficient condition for the null LDA method. As EVD of \(S_T^{+} S_B\) is computationally expensive, we show that the utilization of random matrix together with \(S_T^{+} S_B\) is also a sufficient condition for the null LDA method. This condition is used here to derive a computationally fast implementation of the null LDA method. We show that the computational complexity of the proposed implementation is significantly lower than the other implementations of the null LDA method reported in the literature. This result is also confirmed by conducting classification experiments on several data sets.

MSC:

62H30 Classification and discrimination; cluster analysis (statistical aspects)
15B52 Random matrices (algebraic aspects)
65C60 Computational problems in statistics (MSC2010)

Software:

UCI-ml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armstrong, S. A.; Staunton, J. E.; Silverman, L. B.; Pieters, R.; den Boer, M. L.; Minden, M. D.; Sallan, S. E.; Lander, E. S.; Golub, T. R.; Korsemeyer, S. J., MLL translocations specify a distinct gene expression profile that distinguishes a unique leukemia, Nature Genetics, 30, 41-47 (2002), [Data Source1:], [Data Source2: ]
[2] Belhumeur, P. N.; Hespanha, J. P.; Kriegman, D. J., Eigenfaces vs. fisherfaces: recognition using class specific linear projection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 7, 711-720 (1997)
[3] C.L. Blake and C.J. Merz, UCI repository of machine learning databases, 〈http://www.ics.uci.edu/∼mlearn; C.L. Blake and C.J. Merz, UCI repository of machine learning databases, 〈http://www.ics.uci.edu/∼mlearn
[4] Cevikalp, H.; Neamtu, M.; Wilkes, M.; Barkana, A., Discriminative common vectors for face recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 1, 4-13 (2005)
[5] Chen, L.-F.; Liao, H.-Y. M.; Ko, M.-T.; Lin, J.-C.; Yu, G.-J., A new LDA-based face recognition system which can solve the small sample size problem, Pattern Recognition, 33, 1713-1726 (2000)
[6] Chu, D.; Thye, G. S., A new and fast implementation for null space based linear discriminant analysis, Pattern Recognition, 43, 1373-1379 (2010) · Zbl 1192.68562
[7] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9, 3, 251-280 (1990) · Zbl 0702.65046
[8] Duda, R. O.; Hart, P. E., Pattern Classification and Scene Analysis (1973), Wiley: Wiley New York · Zbl 0277.68056
[9] Friedman, J. H., Regularized discriminant analysis, Journal of the American Statistical Association, 84, 165-175 (1989)
[10] Fukunaga, K., Introduction to Statistical Pattern Recognition (1990), Academic Press Inc., Hartcourt Brace Jovanovich, Publishers, San Diego, CA 92101-4495, USA · Zbl 0711.62052
[11] Golub, G. H.; Loan, C. F.V., Matrix Computations (1996), The John Hopkins University Press, Baltimore, Maryland 21218-4363, USA
[12] Guo, Y.; Hastie, T.; Tinshirani, R., Regularized discriminant analysis and its application in microarrays, Biostatistics, 8, 1, 86-100 (2007) · Zbl 1170.62382
[13] Hamsici, O. C.; Martinez, A. M., Bayes optimality in linear discriminant analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 647-657 (2008)
[14] Howland, P.; Park, H., Generalizing discriminant analysis using the generalized singular value decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 995-1006 (2004)
[15] Huang, R.; Liu, Q.; Lu, H.; Ma, S., Solving the small sample size problem of LDA, Proceedings of ICPR, 3, 29-32 (2002), 2002
[16] Jiang, X.; Mandal, B.; Kot, A., Eigenfeature regularization and extraction in face recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 3, 383-394 (2008)
[17] Jiang, X., Asymmetric principal component analysis and discriminant analysis for pattern classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31, 5, 931-937 (2009)
[18] Jiang, X., Linear subspace learning-based dimensionality reduction, IEEE Signal Processing Magazine, 28, 2, 16-26 (2011)
[19] Khan, J.; Wei, J. S.; Ringner, M.; Saal, L. H.; Ladanyi, M.; Westermann, F.; Berthold, F.; Schwab, M.; Antonescu, C. R.; Peterson, C.; Meltzer, P. S., Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural network, Nature Medicine, 7, 673-679 (2001), [Data Source: 〈http://research.nhgri.nih.gov/microarray/Supplement/〉]
[20] Jin, Z.; Yang, J. Y.; Tang, Z. M.; Hu, Z. S., A theorem on the uncorrelated optimal discriminant vectors, Pattern Recognition, 24, 10, 2041-2047 (2001) · Zbl 0999.68189
[21] Krzanowski, W. J.; Jonathan, P.; McCarthy, W. V.; Thomas, M. R., Discriminant analysis with singular covariance matrices: methods and applications to spectroscopic data, Applied Statistics, 44, 101-115 (1995) · Zbl 0821.62032
[22] Liu, J.; Chen, S.; Tan, X.; Zhang, D., Efficient pseudoinverse linear discriminant analysis and its non linear form for face recognition, International Journal of Pattern Recognition and Artificial Intelligence, 21, 1265-1278 (2007)
[23] W. Liu, Y. Wang, S.Z. Li and T. Tan, Null Space Approach of Fisher Discriminant Analysis for Face Recognition, ECCV Biometric Authentication Workshop, Prague, Czech, 2004.; W. Liu, Y. Wang, S.Z. Li and T. Tan, Null Space Approach of Fisher Discriminant Analysis for Face Recognition, ECCV Biometric Authentication Workshop, Prague, Czech, 2004.
[24] Lotlikar, R.; Kothari, R., Fractional-step dimensionality reduction, IEEE TransPattern Analysis and Machine Intelligence, 22, 6, 623-627 (2000)
[25] Lu, J.; Plataniotis, K. N.; Venetsanopoulos, A. N., Face recognition using LDA-based algorithms, IEEE Transactions on Neural Networks., 14, 1, 195-200 (2003)
[26] Martinez, A. M., Recognizing imprecisely localized, partially occluded, and expression variant faces from a single sample per class, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 6, 748-763 (2002)
[27] Park, C. H.; Park, H., A comparison of generalized linear discriminant analysis algorithms, Pattern Recognition, 41, 1083-1097 (2008) · Zbl 1132.68656
[28] Ramaswamy, S.; Tamayo, P.; Rifkin, R.; Mukherjee, S.; Yeang, C.-H.; Angelo, M.; Ladd, C.; Reich, M.; Latulippe, E.; Mesirov, J. P.; Poggio, T.; Gerald, W.; Loda, M.; Lander, E. S.; Golub, T. R., Multiclass cancer diagnosis using tumor gene expression signatures, Proceedings of the National Academy of Sciences of the USA, 98, 26, 15149-15154 (2001)
[29] Raudys, S.; Duin, R. P.W., On expected classification error of the Fisher linear classifier with pseudo-inverse covariance matrix, Pattern Recognition Letters, 19, 5-6, 385-392 (1998) · Zbl 0907.68171
[30] F. Samaria and A. Harter, Parameterization of a stochastic model for human face identification, Proc. Second IEEE Workshop Applications of Comp. Vision, pp. 138-142, 1994.; F. Samaria and A. Harter, Parameterization of a stochastic model for human face identification, Proc. Second IEEE Workshop Applications of Comp. Vision, pp. 138-142, 1994.
[31] Sharma, A.; Paliwal, K. K., Cancer classification by gradient LDA technique using microarray gene expression data, Data & Knowledge Engineering, 66, 338-347 (2008)
[32] Sharma, A.; Paliwal, K. K., A gradient linear discriminant analysis for small sample sized problem, Neural Processing Letters, 27, 17-24 (2008)
[33] Singh, D.; Febbo, P. G.; Ross, K.; Jackson, D. G.; Manola, J.; Ladd, C.; Tamayo, P.; Renshaw, A. A.; D’Amico, A. V.; Richie, J. P.; Lander, E. S.; Loda, M.; Kantoff, P. W.; Golub, T. R.; Sellers, W. R., Gene expression correlates of clinical prostate cancer behavior, Cancer Cell, 1, 203-209 (2002), [Data Source:]
[34] Swets, D. L.; Weng, J., Using discriminative eigenfeatures for image retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, 18, 8, 831-836 (1996)
[35] Tian, Q.; Barbero, M.; Gu, Z. H.; Lee, S. H., Image classification by the Foley-Sammon transform, Optical Engineering, 25, 7, 834-840 (1986)
[36] Yang, J.; Zhang, D.; Yang, J.-Y., A generased \(K-L\) expansion method which can deal with small samples size and high-dimensional problems, Pattern Analysis and Applications, 6, 47-54 (2003) · Zbl 1035.68109
[37] Ye, J., Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems, Journal of Machine Learning Research, 6, 483-502 (2005) · Zbl 1222.62081
[38] Ye, J.; Xiong, T., Computational and theoretical analysis of null space and orthogonal linear discriminant analysis, Journal of Machine Learning Research, 7, 1183-1204 (2006) · Zbl 1222.62082
[39] Yeoh, E. J.; Ross, M. E.; Shurtleff, S. A.; Williams, W. K.; Patel, D.; Mahfouz, R.; Behm, F. G.; Raimondi, S. C.; Relling, M. V.; Patel, A.; Cheng, C.; Campana, D.; Wilkins, D.; Zhou, X.; Li, J.; Liu, H.; Pui, C. H.; Evans, W. E.; Naeve, C.; Wong, L.; Downing, J. R., Classification, subtype discovery, and prediction of outcome in pediatric acute lymphoblastic leukemia by gene expression profiling, Cancer, 1, 2, 133-143 (2002), Data Source: 〈http://www.stjuderesearch.org/data/ALL1/〉]
[40] Yu, H.; Yang, J., A direct LDA algorithm for high-dimensional data-with application to face recognition, Pattern Recognition, 34, 2067-2070 (2001) · Zbl 0993.68091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.