Article

Null space versus orthogonal linear discriminant analysis

Authors:

Tao XiongAuthors Info & Claims

ICML '06: Proceedings of the 23rd international conference on Machine learning

Pages 1073 - 1080

https://doi.org/10.1145/1143844.1143979

Published: 25 June 2006 Publication History

Abstract

Dimensionality reduction is an important pre-processing step for many applications. Linear Discriminant Analysis (LDA) is one of the well known methods for supervised dimensionality reduction. However, the classical LDA formulation requires the nonsingularity of scatter matrices involved. For undersampled problems, where the data dimension is much larger than the sample size, all scatter matrices are singular and classical LDA fails. Many extensions, including null space based LDA (NLDA), orthogonal LDA (OLDA), etc, have been proposed in the past to overcome this problem. In this paper, we present a computational and theoretical analysis of NLDA and OLDA. Our main result shows that under a mild condition which holds in many applications involving high-dimensional data, NLDA is equivalent to OLDA. We have performed extensive experiments on various types of data and results are consistent with our theoretical analysis. The presented analysis and experimental results provide further insight into several LDA based algorithms.

References

[1]

Belhumeour, P., Hespanha, J., & Kriegman, D. (1997). Eigenfaces vs. fisherfaces: Recognition using class specific linear projection. IEEE Trans Pattern Analysis and Machine Intelligence, 19, 711--720.]]

Digital Library

[2]

Chen, L., Liao, H., Ko, M., Lin, J., & Yu, G. (2000). A new LDA-based face recognition system which can solve the small sample size problem. Pattern Recognition, 33, 1713--1726.]]

[3]

Duchene, L., & Leclerq, S. (1988). An optimal transformation for discriminant and principal component analysis. IEEE Trans. Pattern Analysis and Machine Intelligence, 10, 978--983.]]

Digital Library

[4]

Duda, R., Hart, P., & Stork, D. (2000). Pattern classification. Wiley.]]

Digital Library

[5]

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.]]

[6]

Foley, D., & Sammon, J. (1975). An optimal set of discriminant vectors. IEEE Trans Computers, 24, 281--289.]]

Digital Library

[7]

Friedman, J. (1989). Regularized discriminant analysis. Journal of the American Statistical Association, 84, 165--175.]]

[8]

Fukunaga, K. (1990). Introduction to statistical pattern classification. San Diego, California, USA: Academic Press.]]

Digital Library

[9]

Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Baltimore, MD, USA: The Johns Hopkins University Press. Third edition.]]

Digital Library

[10]

Hall, P., Marron, J., & Neeman, A. (2005). Geometric representation of high dimension, low sample size data. Journal of the Royal Statistical Society series B, 67, 427--444.]]

[11]

Hastie, T., Buja, A., & Tibshirani, R. (1995). Penalized discriminant analysis. Annals of Statistics, 23, 73--102.]]

[12]

Hastie, T., Tibshirani, R., & Friedman, J. (2001). The elements of statistical learning: data mining, inference, and prediction. Springer.]]

[13]

Huang, R., Liu, Q., Lu, H., & Ma, S. (2002). Solving the small sample size problem of LDA. Proc. International Conference on Pattern Recognition (pp. 29--32).]]

Digital Library

[14]

Jolliffe, I. T. (1986). Principal component analysis. New York: Springer-Verlag.]]

[15]

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.]]

[16]

Lu, J., Plataniotis, K., & Venetsanopoulos, A. (2003). Face recognition using kernel direct discriminant analysis algorithms. IEEE Trans. Neural Networks, 14, 117--126.]]

Digital Library

[17]

Swets, D. L., & Weng, J. (1996). Using discriminant eigenfeatures for image retrieval. IEEE Trans. Pattern Analysis and Machine Intelligence, 18, 831--836.]]

Digital Library

[18]

Turk, M., & Pentland, A. (1991). Face recognition using eigenfaces. Proc. Computer Vision and Pattern Recognition Conference (pp. 586--591).]]

[19]

Yang, J., Frangi, A., Yang, J., Zhang, D., & Jin, Z. (2005). KPCA plus LDA: a complete kernel fisher discriminant framework for feature extraction and recognition. IEEE Trans. Pattern Analysis and Machine Intelligence, 27, 230-- 244.]]

Digital Library

[20]

Ye, J. (2005). Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems. Journal of Machine Learning Research, 6, 483--502.]]

Digital Library

[21]

Ye, J., Janardan, R., Park, C., & Park, H. (2004a). An optimization criterion for generalized discriminant analysis on undersampled problems. IEEE Trans. Pattern Analysis and Machine Intelligence, 26, 982--994.]]

Digital Library

[22]

Ye, J., Li, T., Xiong, T., & Janardan, R. (2004b). Using uncorrelated discriminant analysis for tissue classification with gene expression data. IEEE/ACM Trans. Computational Biology and Bioinformatics, 1, 181--190.]]

Digital Library

[23]

Yu, H., & Yang, J. (2001). A direct LDA algorithm for high-dimensional data with applications to face recognition. Pattern Recognition, 34, 2067--2070.]]

Cited By

Zhao SZhang BYang JZhou JXu Y(2024)Linear discriminant analysisNature Reviews Methods Primers10.1038/s43586-024-00346-y4:1Online publication date: 26-Sep-2024
https://doi.org/10.1038/s43586-024-00346-y
Chen HZhang HYang YZhang Q(2024)F-Norm-Based Soft LDA Algorithm for Fault Detection in Chemical Production ProcessesACS Omega10.1021/acsomega.4c037479:32(34725-34734)Online publication date: 1-Aug-2024
https://doi.org/10.1021/acsomega.4c03747
Zhou JZhang QZeng SZhang BFang L(2024)Latent Linear Discriminant Analysis for feature extraction via Isometric Structural LearningPattern Recognition10.1016/j.patcog.2023.110218149(110218)Online publication date: May-2024
https://doi.org/10.1016/j.patcog.2023.110218
Show More Cited By

Index Terms

Null space versus orthogonal linear discriminant analysis
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Probability and statistics
    1. Statistical paradigms
      1. Statistical graphics

Recommendations

Feature extraction via generalized uncorrelated linear discriminant analysis
ICML '04: Proceedings of the twenty-first international conference on Machine learning

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 ...
Computational and Theoretical Analysis of Null Space and Orthogonal Linear Discriminant Analysis

Dimensionality reduction is an important pre-processing step in many applications. Linear discriminant analysis (LDA) is a classical statistical approach for supervised dimensionality reduction. It aims to maximize the ratio of the between-class ...
Local Tangent Space Discriminant Analysis

We propose a novel supervised dimensionality reduction method named local tangent space discriminant analysis (TSD) which is capable of utilizing the geometrical information from tangent spaces. The proposed method aims to seek an embedding space where ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '06: Proceedings of the 23rd international conference on Machine learning

June 2006

1154 pages

ISBN:1595933832

DOI:10.1145/1143844

Program Chairs:
William Cohen,
Andrew Moore

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

ICML '06 Paper Acceptance Rate 140 of 548 submissions, 26%;

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
490
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao SZhang BYang JZhou JXu Y(2024)Linear discriminant analysisNature Reviews Methods Primers10.1038/s43586-024-00346-y4:1Online publication date: 26-Sep-2024
https://doi.org/10.1038/s43586-024-00346-y
Chen HZhang HYang YZhang Q(2024)F-Norm-Based Soft LDA Algorithm for Fault Detection in Chemical Production ProcessesACS Omega10.1021/acsomega.4c037479:32(34725-34734)Online publication date: 1-Aug-2024
https://doi.org/10.1021/acsomega.4c03747
Zhou JZhang QZeng SZhang BFang L(2024)Latent Linear Discriminant Analysis for feature extraction via Isometric Structural LearningPattern Recognition10.1016/j.patcog.2023.110218149(110218)Online publication date: May-2024
https://doi.org/10.1016/j.patcog.2023.110218
Zhu YLai ZGao CKong H(2024)Generalized robust linear discriminant analysis for jointly sparse learningApplied Intelligence10.1007/s10489-024-05632-6Online publication date: 17-Jul-2024
https://doi.org/10.1007/s10489-024-05632-6
Cheng HJiang LZhao SZhang XWu J(2024)Sparse Discriminant Graph Embedding for Feature ExtractionAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5594-3_10(111-123)Online publication date: 14-Aug-2024
https://doi.org/10.1007/978-981-97-5594-3_10
Hong SHuu QViet DThi Thuy QQuoc T(2023)Learning binary codes for fast image retrieval with sparse discriminant analysis and deep autoencodersIntelligent Data Analysis10.3233/IDA-22668727:3(809-831)Online publication date: 18-May-2023
https://doi.org/10.3233/IDA-226687
Knowles MBarany ACai ZShaffer D(2023)Multiclass Rotations in Epistemic Network AnalysisAdvances in Quantitative Ethnography10.1007/978-3-031-31726-2_5(58-70)Online publication date: 29-Apr-2023
https://doi.org/10.1007/978-3-031-31726-2_5
Meenakshi Srirangarajan S(2022)Locality-Aware Discriminative Subspace Learning for Image ClassificationIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2022.318773571(1-14)Online publication date: 2022
https://doi.org/10.1109/TIM.2022.3187735
Li LQu HLi ZZheng JGuo F(2022)Discriminative Projection Learning With Adaptive Reversed Graph Embedding for Supervised and Semi-Supervised Dimensionality ReductionIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2022.319665332:12(8688-8702)Online publication date: Dec-2022
https://doi.org/10.1109/TCSVT.2022.3196653
Qu HLi LLi ZZheng JTang X(2022)Robust discriminative projection with dynamic graph regularization for feature extraction and classificationKnowledge-Based Systems10.1016/j.knosys.2022.109563253(109563)Online publication date: Oct-2022
https://doi.org/10.1016/j.knosys.2022.109563
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents