A new perspective to null linear discriminant analysis method and its fast implementation using random matrix multiplication with scatter matrices

Null linear discriminant analysis (LDA) method is a popular dimensionality reduction method for solving small sample size problem. The implementation of null LDA method is, however, computationally very expensive. In this paper, we theoretically derive the null LDA method from a different perspective and present a computationally efficient implementation of this method. Eigenvalue decomposition (EVD) of ST+SB (where SB is the between-class scatter matrix and ST+ is the pseudoinverse of the total scatter matrix ST) is shown here to be a sufficient condition for the null LDA method. As EVD of ST+SBis computationally expensive, we show that the utilization of random matrix together with ST+SB is also a sufficient condition for null LDA method. This condition is used here to derive a computationally fast implementation of the null LDA method. We show that the computational complexity of the proposed implementation is significantly lower than the other implementations of the null LDA method reported in the literature. This result is also confirmed by conducting classification experiments on several datasets.

► A new perspective of null LDA method has been presented using random matrix multiplication.
► The method is computationally efficient compared to other implementations of null LDA method.
► The implementation has been experimented on several types of datasets.
► The eigenvalue decomposition of ST+SB is shown to be a sufficient condition for null LDA method.
► The utilization of random matrix together with ST+SB is also a sufficient condition for null LDA method.