  In our "big data" age, the size and complexity of data is steadily
increasing. Methods for dimension reduction are ever more popular and useful.
Two distinct types of dimension reduction are "data-oblivious" methods such as
random projections and sketching, and "data-aware" methods such as principal
component analysis (PCA). Both have their strengths, such as speed for random
projections, and data-adaptivity for PCA. In this work, we study how to combine
them to get the best of both. We study "sketch and solve" methods that take a
random projection (or sketch) first, and compute PCA after. We compute the
performance of several popular sketching methods (random iid projections,
random sampling, subsampled Hadamard transform, count sketch, etc) in a general
"signal-plus-noise" (or spiked) data model. Compared to well-known works, our
results (1) give asymptotically exact results, and (2) apply when the signal
components are only slightly above the noise, but the projection dimension is
non-negligible. We also study stronger signals allowing more general covariance
structures. We find that (a) signal strength decreases under projection in a
delicate way depending on the structure of the data and the sketching method,
(b) orthogonal projections are more accurate, (c) randomization does not hurt
too much, due to concentration of measure, (d) count sketch can be improved by
a normalization method. Our results have implications for statistical learning
and data analysis. We also illustrate that the results are highly accurate in
simulations and in analyzing empirical data.
