Convergence Analysis on Trace Ratio Linear Discriminant Analysis Algorithms.

Abstract

Linear discriminant analysis (LDA) may yield an inexact solution by transforming a trace ratio problem into a corresponding ratio trace problem. Most recently, optimal dimensionality LDA (ODLDA) and trace ratio LDA (TRLDA) have been developed to overcome this problem. As one of the greatest contributions, the two methods design efficient iterative algorithms to derive an optimal solution. However, the theoretical evidence for the convergence of these algorithms has not yet been provided, which renders the theory of ODLDA and TRLDA incomplete. In this correspondence, we present some rigorously theoretical insight into the convergence of the iterative algorithms. To be specific, we first demonstrate the existence of lower bounds for the objective functions in both ODLDA and TRLDA, and then establish proofs that the objective functions are monotonically decreasing under the iterative frameworks. Based on the findings, we disclose the convergence of the iterative algorithms finally.