How to reduce dimension with PCA and random projections?

Abstract

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.

arXiv comment56 pages, 12 figures

References in corpus (16)

• Linear Dimensionality Reduction: Survey, Insights, and Generalizations
• A generalization of the Lindeberg principle
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• Randomized algorithms for matrices and data
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• Randomized Matrix Decompositions using R
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• Efficient Computation of Limit Spectra of Sample Covariance Matrices
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Sharp detection in PCA under correlations: all eigenvalues matter
• Singular vector and singular subspace distribution for the matrix denoising model
• Distributed linear regression by averaging
• Spiked separable covariance matrices and principal components
• Optimal Covariance Estimation for Condition Number Loss in the Spiked Model
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform

Cited by in corpus (5)

• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Sample canonical correlation coefficients of high-dimensional random vectors with finite rank correlations
• Sparse sketches with small inversion bias
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Precise expressions for random projections: Low-rank approximation and randomized Newton