Single Pass PCA of Matrix Products
Shanshan Wu, Srinadh Bhojanapalli, Sujay Sanghavi, Alexandros G Dimakis
Abstract
In this paper we present a new algorithm for computing a low rank approximation of the product $A^TB$ by taking only a single pass of the two matrices $A$ and $B$. The straightforward way to do this is to (a) first sketch $A$ and $B$ individually, and then (b) find the top components using PCA on the sketch. Our algorithm in contrast retains additional summary information about $A,B$ (e.g. row and column norms etc.) and uses this additional information to obtain an improved approximation from the sketches. Our main analytical result establishes a comparable spectral norm guarantee to existing two-pass methods; in addition we also provide results from an Apache Spark implementation that shows better computational and statistical performance on real-world and synthetic evaluation datasets.
BibTeX
@inproceedings{NIPS2016_0e55666a,
author = {Wu, Shanshan and Bhojanapalli, Srinadh and Sanghavi, Sujay and Dimakis, Alexandros G},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Single Pass PCA of Matrix Products},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/0e55666a4ad822e0e34299df3591d979-Paper.pdf},
volume = {29},
year = {2016}
}