  Fisher discriminant analysis (FDA) is a widely used method for classification
and dimensionality reduction. When the number of predictor variables greatly
exceeds the number of observations, one of the alternatives for conventional
FDA is regularized Fisher discriminant analysis (RFDA). In this paper, we
present a simple, iterative, sketching-based algorithm for RFDA that comes with
provable accuracy guarantees when compared to the conventional approach. Our
analysis builds upon two simple structural results that boil down to randomized
matrix multiplication, a fundamental and well-understood primitive of
randomized linear algebra. We analyze the behavior of RFDA when the ridge
leverage and the standard leverage scores are used to select predictor
variables and we prove that accurate approximations can be achieved by a sample
whose size depends on the effective degrees of freedom of the RFDA problem. Our
results yield significant improvements over existing approaches and our
empirical evaluations support our theoretical analyses.
