A subspace method for large-scale trace ratio problems

We present a subspace method to solve large-scale trace ratio problems. This method is matrix-free, only needing the action of the two matrices in the trace ratio. At each iteration, a smaller trace ratio problem is addressed in the search subspace. Additionally, our algorithm is endowed with a restarting strategy, that ensures the monotonicity of the trace ratio value throughout the iterations. We also investigate the behavior of the approximate solution from a theoretical viewpoint, extending existing results on Ritz values and vectors, as the angle between the search subspace and the exact solution to the trace ratio approaches zero. In the context of multigroup classification, numerical experiments show that the new subspace method tends to be more efficient than iterative approaches that need a (partial) eigenvalue decomposition in every step.