Trace Ratio Optimization for High-Dimensional Multi-Class Discrimination

Abstract

In multi-class discrimination with high-dimensional data, identifying a lower-dimensional subspace with maximum class separation is crucial. We propose a new optimization criterion for finding such a discriminant subspace, which is the ratio of two traces: the trace of between-class scatter matrix and the trace of within-class scatter matrix. Since this problem is not well-defined for high-dimensional data, we propose to regularize the within trace and maximize the between trace. A careful investigation reveals that this optimization has an innate connection to the eigenvalue decomposition of an indefinite matrix. For the sake of better interpretability of the classifier, we also consider a sparse estimation via a group-wise soft-thresholding. Interesting relationships between the proposed method and some classical methods such as Fisher’s linear discriminant analysis and its variants are discussed. Empirical examples with simulated and real datasets suggest that the proposed method works well and is often better than some existing approaches in a wide range of problems, with respect to both variable selectivity and classification accuracy. Supplementary files for this article are available online.

Keywords:

• Discriminant subspace
• Groupwise soft-thresholding
• Indefinite matrix
• Linear discriminant analysis
• Ratio trace
• Sparsity

Supplementary Materials

Matlab routine: the code that reproduces the simulation and real data analysis results in the article (compressed files.zip).

Additional information

Funding

Jeon’s research was supported by Basic Science Research Program of the National Research Foundation of Korea (2019R1A2C100597912) funded by the Korean Government.