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.
High dimensional data를 다루는 여러 분야의 classification 문제에서 dimensionality reduction은 중요한 issue이다. Linear discriminant analysis (LDA)는 예전부터 널리 사용된 기법으로, between-class scatter를 maximize 하며 동시에 within-class scatter를 minimize 하는 transformation을 찾는다. 하지만 기존의 LDA는 data의 수가 충분한 (within-class scatter matrix가 nonsingular) 경우에만 적용할 수 있으며, 많은 연산량이 필요한 eigenvalue decomposition을 수행해야 한다. 이 논문에서는 일반화된 LDA를 소개하고 LDA와 모든 data를 변환된 공간에서 class 별로 한 점에 근접하도록 하는 least squares (LS) problem이 등가임을 보인다. 즉, LDA의 해와 이러한 LS의 해는 같은 range를 가진다. 이 등가성을 이용하여 LDA를 푸는 효율적인 algorithm을 제시한다. 이 algorithm은 특정 형태의 generalized eigenvalue problem에도 적용할 수 있다. 또한, centering과 matrix augmentation과의 등가성을 보이고, 이 등가성이 성립하기 위한 조건에 대해 알아본다. 이 등가성으로부터 sparse data에 적용할 수 있는 효율적인 algorithm을 제시한다. 실험적 결과는 제시된 algorithm의 효율성을 뒷받침한다. 이 기법은 기존의 LDA와 마찬가지로 kernel method를 적용할 수 있을 것이며, LASSO regularization을 적용하면 sparse solution을 얻을 수 있을 것이다.