On the equivalence of linear discriminant analysis and least squares

Abstract

In classification, dimensionality reduction has been an important problem in many fields dealing with high dimensional data. Linear discriminant analysis (LDA) is a popular dimensionality reduction and classification method which maximizes between-class scatter and minimizes within-class scatter simultaneously. However, LDA assumes enough number of samples to make within-class scatter matrix nonsingular, and the solution needs generalized eigenvalue decomposition, which is computationally expensive. In this thesis, we introduce a generalized LDA and we verify the equivalence of LDA and certain least squares (LS) problems which cluster all data according to the class. The equivalence is in the sense that LDA solution matrix and LS solution matrix have the same range. Using this equivalence, an efficient algorithm to solve LDA is proposed, and this algorithm is applicable to a class of generalized eigenvalue problems. On the other hand, we discuss the equivalence between centering and matrix augmentation, and examine the conditions for such equivalence. Based on this equivalence, an efficient algorithm for sparse data is proposed. Experimental results demonstrate the efficiency of the proposed algorithms.