Making Fisher Discriminant Analysis Scalable
Bojun Tu, Zhihua Zhang, Shusen Wang, Hui Qian · 2014
The Fisher linear discriminant analysis (LDA) is a classical method for classification and dimen-sion reduction jointly. A major limitation of the conventional LDA is a so-called singularity is-sue. Many LDA variants, especially two-stage methods such as PCA+LDA and LDA/QR, were proposed to solve this issue. In the two-stage methods, an intermediate stage for dimension reduction is developed before the actual LDA method works. These two-stage methods are scalable because they are an approximate alter-native of the LDA method. However, there is no theoretical analysis on how well they approx-imate the conventional LDA problem. In this pa-per we present theoretical analysis on the approx-imation error of a two-stage algorithm. Accord-ingly, we develop a new two-stage algorithm. Furthermore, we resort to a random projection approach, making our algorithm scalable. We also provide an implemention on distributed sys-tem to handle large scale problems. Our algo-rithm takes LDA/QR as its special case, and out-performs PCA+LDA while having a similar scal-ability. We also generalize our algorithm to ker-nel discriminant analysis, a nonlinear version of the classical LDA. Extensive experiments show that our algorithms outperform PCA+LDA and have a similar scalability with it.