Efficient Leave-One-Out Cross-Validation of Kernel Fisher Discriminant Classifiers

Mika et al. [1] apply the “kernel trick ” to obtain a non-linear variant of Fisher’s linear discriminant analysis method, demonstrating state-of-the-art performance on a range of benchmark datasets. We show that leave-one-out cross-validation of kernel Fisher discriminant classifiers can be implemented with a computational com-plexity of only O(ℓ 3) operations rather than the O(ℓ 4) of a naïve implementation, where ℓ is the number of training patterns. Leave-one-out cross-validation then becomes an attractive means of model selection in large-scale applications of kernel Fisher discriminant analysis, being significantly faster than conventional k-fold cross-validation procedures commonly used