A Fast Algorithm about Kernel Fisher Discriminant Analysis
Zhao Feng①③; Zhang Jun-ying①②; Liang Jun-li④
①School of Computer Science and Engineering, Xidian University, Xi’an 710071, China; ②National Key Lab of Radar Signal Processing, Xidian University, Xi’an 710071, China; ③School of Science, Jinan University, Jinan 250012, China; ④Institute of Acoustics, Chinese Academy of Sciences, Beijing 100080, China
Abstract：The standard Kernel Fisher Discriminant Analysis(KFDA) may suffer from the large computation complexity and the slow speed of feature extraction for the case of large number of training samples. To tackle these problems, a fast algorithm of KFDA is presented. The algorithm firstly proposes an optimized algorithm based on the theory of linear correlation, which finds out a basis of the sub-space spanned by the training samples mapped onto the feature space and which avoids the operation of matrix inversion ; Then using the linear combination of the basis to express the optimal projection vectors，and combining with Fisher criterion in the feature space, a novel criterion for the computation of the optimal projection vectors is presented, which only needs to calculate the eigenvalue of a matrix which size is the same as the number of the basis. In addition, the feature extraction for one sample only needs to calculate the kernel functions between the basis and the sample. The experimental results using different datasets demonstrate the validity of the presented algorithm.
2007, Vol. 29 
