Least squares online linear discriminant analysis

Linear discriminant analysis (LDA) is one of the most widely used supervised dimensionality reduction algorithms. Standard LDA performs in batch way which needs all the data be available before learning. However, in many real world applications, data is coming continuously over time and sometimes undergoing concept drift, so it is more desirable to only keep the most recent data by using a certain slide window. Several incremental LDA algorithms have been developed and achieved success, however, they do not consider the case when an instance is deleted and require large computational cost. In this paper, we propose a new online LDA algorithm, LS-OLDA, based on the least square solution of LDA. When an instance is inserted or deleted, it dynamically updates the least square solution of LDA. Our analysis reveals that this algorithm produces the exact least square solution of batch LDA, while its computational cost is O(min(n; d) × d + nk) for one update on dataset containing n instances in d-dimensional space with k classes. Experimental results show that our proposed algorithm could achieve high accuracy with low time cost.