A Non-Greedy Algorithm for L1-Norm LDA

Abstract

Recently, L1-norm-based discriminant subspace learning has attracted much more attention in dimensionality reduction and machine learning. However, most existing approaches solve the column vectors of the optimal projection matrix one by one with greedy strategy. Thus, the obtained optimal projection matrix does not necessarily best optimize the corresponding trace ratio objective function, which is the essential criterion function for general supervised dimensionality reduction. In this paper, we propose a non-greedy iterative algorithm to solve the trace ratio form of L1-norm-based linear discriminant analysis. We analyze the convergence of our proposed algorithm in detail. Extensive experiments on five popular image databases illustrate that our proposed algorithm can maximize the objective function value and is superior to most existing L1-LDA algorithms.