Timezone: »

 
Poster
Single Pass PCA of Matrix Products
Shanshan Wu · Srinadh Bhojanapalli · Sujay Sanghavi · Alex Dimakis

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #84
in Wednesday Posters »
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.
Keywords: Spectral Methods · Matrix Factorization · Large Scale Learning and Big Data · Component Analysis (ICA,PCA,CCA, FLDA)

Author Information

Shanshan Wu (UT Austin)

Here is my homepage: http://wushanshan.github.io/

Srinadh Bhojanapalli (TTI Chicago)
Sujay Sanghavi (UT-Austin)
Alex Dimakis (University of Texas, Austin)

More from the Same Authors