A theoretical contribution to the fast implementation of null linear discriminant analysis with random matrix multiplication

Summary The null linear discriminant analysis method is a competitive approach for dimensionality reduction. The implementation of this method, however, is computationally expensive. Recently, a fast implementation of null linear discriminant analysis method was proposed in the paper of Sharma et al. In this method, a random matrix multiplication with scatter matrix is used to produce the orientation matrix. In this paper, we consider whether the random matrix can be replaced by an arbitrary full rank matrix of appropriate size, and focus on the necessary and sufficient condition to guarantee full column rank of the orientation matrix. We investigate how to choose the matrix properly, such that the two criteria of the null linear discriminant analysis method are satisfied. Furthermore, we give a necessary and sufficient condition to guarantee full column rank of the orientation matrix, and describe the geometric characterization of this condition. Numerical experiments justify our theoretical analysis. Copyright © 2015 John Wiley & Sons, Ltd.