  Linear discriminant analysis (LDA) is a classical method for dimensionality
reduction, where discriminant vectors are sought to project data to a lower
dimensional space for optimal separability of classes. Several recent papers
have outlined strategies for exploiting sparsity for using LDA with
high-dimensional data. However, many lack scalable methods for solution of the
underlying optimization problems. We propose three new numerical optimization
schemes for solving the sparse optimal scoring formulation of LDA based on
block coordinate descent, the proximal gradient method, and the alternating
direction method of multipliers. We show that the per-iteration cost of these
methods scales linearly in the dimension of the data provided restricted
regularization terms are employed, and cubically in the dimension of the data
in the worst case. Furthermore, we establish that if our block coordinate
descent framework generates convergent subsequences of iterates, then these
subsequences converge to the stationary points of the sparse optimal scoring
problem. We demonstrate the effectiveness of our new methods with empirical
results for classification of Gaussian data and data sets drawn from
benchmarking repositories, including time-series and multispectral X-ray data,
and provide Matlab and R implementations of our optimization schemes.
