Feature extraction using a fast null space based linear discriminant analysis algorithm

The small sample size problem is often encountered in pattern recognition. Several algorithms for null space based linear discriminant analysis (NLDA) have been developed to solve the problem. However, these algorithms for NLDA have high computational cost. In this paper, we simplify the recently proposed algorithm for NLDA in Chu and Thye (2010) [5] with the assumption that all the training data vectors are linearly independent and propose a new and fast algorithm for NLDA. Our main observation is that two steps of economic QR decomposition with column pivoting can be replaced by one step of economic QR decomposition without column pivoting if the related matrix is of full column rank. The main features of our algorithm for NLDA include: (i) our NLDA algorithm is carried out by only one step of economic QR decomposition and does not compute any singular value decomposition (SVD) when all the training data vectors are linearly independent; (ii) the main cost of our method is the cost of an economic QR decomposition of an m × (n − 1) matrix, here m is the dimension of the training data and n is the number of samples. Our method is a fast one. Experimental studies on ORL, FERET and PIE face databases demonstrate the effectiveness of our new algorithm for NLDA.