Exponential Trace‐Ratio Method for High Dimensionality Reduction

ABSTRACT Linear discriminant analysis (LDA) is a classical method for feature extraction and dimensionality reduction. Mathematically, the LDA method resorts to a trace‐ratio problem; however, it often suffers from the small‐sample‐size (SSS) problem for data with high dimension. Matrix exponential discriminant analysis (EDA) methods are efficient ways to deal with the SSS problem. To the best of our knowledge, however, all the existing matrix exponential‐based discriminant methods reduce to ratio‐trace problems, rather than trace‐ratio problems. This goes against the motivation of the original Fisher criterion for LDA. Indeed, it has been shown that the trace‐ratio model can yield markedly improved recognition results for supervised learning tasks. Therefore, it is interesting to investigate discriminant analysis methods that can combine the matrix exponential and trace‐ratio model. To fill in this gap, we first propose a matrix exponential trace‐ratio model and present a fast iterative exponential trace‐ratio (FIETR) algorithm for solving it efficiently. The key is to equivalently transform a large‐scale matrix exponential computation problem into a much smaller one. Second, we give the convergence of the iterative exponential trace‐ratio algorithm, and show that it can converge faster than the popular iterative trace‐ratio algorithm (ITR), which is the state‐of‐the‐art algorithm for the trace‐ratio problem. Thanks to the property of matrix exponential, we prove that the exponential trace‐ratio values generated by our algorithm converge locally and (at least) quadratically to the global optimal objective value. Third, to accelerate the FIETR method further, we propose a non‐iterative algorithm for solving the matrix exponential trace‐ratio problem efficiently. Numerical experiments on some real‐world data sets illustrate the numerical behavior of the proposed algorithms.