  We propose a new method for high-dimensional semi-supervised learning
problems based on the careful aggregation of the results of a low-dimensional
procedure applied to many axis-aligned random projections of the data. Our
primary goal is to identify important variables for distinguishing between the
classes; existing low-dimensional methods can then be applied for final class
assignment. Motivated by a generalized Rayleigh quotient, we score projections
according to the traces of the estimated whitened between-class covariance
matrices on the projected data. This enables us to assign an importance weight
to each variable for a given projection, and to select our signal variables by
aggregating these weights over high-scoring projections. Our theory shows that
the resulting Sharp-SSL algorithm is able to recover the signal coordinates
with high probability when we aggregate over sufficiently many random
projections and when the base procedure estimates the whitened between-class
covariance matrix sufficiently well. The Gaussian EM algorithm is a natural
choice as a base procedure, and we provide a new analysis of its performance in
semi-supervised settings that controls the parameter estimation error in terms
of the proportion of labeled data in the sample. Numerical results on both
simulated data and a real colon tumor dataset support the excellent empirical
performance of the method.
