Fast Linear Discriminant Analysis using QR Decomposition and Regularization

Abstract

Linear Discriminant Analysis (LDA) is among the most optimal dimension reduction methods for
\nclassification, which provides a high degree of class separability for numerous applications from science
\nand engineering. However, problems arise with this classical method when one or both of the scatter
\nmatrices is singular. Singular scatter matrices are not unusual in many applications, especially for high-dimensional
\ndata. For high-dimensional undersampled and oversampled problems, the classical LDA
\nrequires modification in order to solve a wider range of problems. In recent work the generalized singular
\nvalue decomposition (GSVD) has been shown to mitigate the issue of singular scatter matrices, and a new
\nalgorithm, LDA/GSVD, has been shown to be very robust for many applications in machine learning.
\nHowever, the GSVD inherently has a considerable computational overhead. In this paper, we propose fast
\nalgorithms based on the QR decomposition and regularization that solve the LDA/GSVD computational
\nbottleneck. In addition, we present fast algorithms for classical LDA and regularized LDA utilizing
\nthe framework based on LDA/GSVD and preprocessing by the Cholesky decomposition. Experimental
\nresults are presented that demonstrate substantial speedup in all of classical LDA, regularized LDA, and
\nLDA/GSVD algorithms without any sacrifice in classification performance for a wide range of machine
\nlearning applications.