SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis
- 27 November 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 20 (1), 1-12
- https://doi.org/10.1109/tkde.2007.190669
Abstract
Linear Discriminant Analysis (LDA) has been a popular method for extracting features that preserves class separability. The projection functions of LDA are commonly obtained by maximizing the between-class covariance and simultaneously minimizing the within-class covariance. It has been widely used in many fields of information processing, such as machine learning, data mining, information retrieval, and pattern recognition. However, the computation of LDA involves dense matrices eigendecomposition, which can be computationally expensive in both time and memory. Specifically, LDA has O(mnt + t3) time complexity and requires O(mn + mt + nt) memory, where m is the number of samples, n is the number of features, and t = min(m,n). When both m and n are large, it is infeasible to apply LDA. In this paper, we propose a novel algorithm for discriminant analysis, called Spectral Regression Discriminant Analysis (SRDA). By using spectral graph analysis, SRDA casts discriminant analysis into a regression framework that facilitates both efficient computation and the use of regularization techniques. Specifically, SRDA only needs to solve a set of regularized least squares problems, and there is no eigenvector computation involved, which is a huge save of both time and memory. Our theoretical analysis shows that SRDA can be computed with O(mn) time and O(ms) memory, where .s(les n) is the average number of nonzero features in each sample. Extensive experimental results on four real-world data sets demonstrate the effectiveness and efficiency of our algorithm.Keywords
This publication has 20 references indexed in Scilit:
- Spectral Regression: A Unified Approach for Sparse Subspace LearningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Efficient Kernel Discriminant Analysis via Spectral RegressionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Spectral regressionPublished by Association for Computing Machinery (ACM) ,2007
- Least squares linear discriminant analysisPublished by Association for Computing Machinery (ACM) ,2007
- Spectral Regression for Efficient Regularized Subspace LearningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Regularized discriminant analysis for high dimensional, low sample size dataPublished by Association for Computing Machinery (ACM) ,2006
- IDR/QR: an incremental dimension reduction algorithm via QR decompositionIEEE Transactions on Knowledge and Data Engineering, 2005
- Matrix AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2001
- Eigenfaces vs. Fisherfaces: recognition using class specific linear projectionIeee Transactions On Pattern Analysis and Machine Intelligence, 1997
- ACM Transactions on Mathematical Software, 1982