Single Pass PCA of Matrix Products
In this paper we present a new algorithm for computing a low rank approximation of the product A T B 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 1 that shows better computational and statistical performance on real-world and synthetic evaluation datasets.
The authors have proposed a novel single pass PCA algorithm for computing the low-rank approximation of the inner product of two matrices A and B. Therefore, two smaller representations of the full-state matrices are computed using matrix sketching. Then, based on the sketched matrices, an estimator for the inner product is computed. The key innovation of the algorithm is the rescaled Johnson–Lindenstrauss (JL) embedding, used to estimate the important entries of the inner product. Finally, a matrix completion algorithm is used to obtain the desired rank-r approximation. In addition to theoretical results, the authors provide an Apache Spark implementation and empirical evaluations using both synthetic and real data. 
The paper is well written, and the theoretically developments seem sound and interesting, though I checked the proofs in the appendix only briefly. The provided code is structured and well readable.  Technical quality: Overall the technical quality is very good. My main concern is with the experiments, specifically the algorithms run-time, shown in Figure (3a). The evaluation seems somewhat fuzzy for two reasons. (1) The sketch size 'k=10' is used, while in Table (1) the sketch size 'k=4000,8000' are shown. (2) The authors excluding the time for executing alternating least squares (ALS), because they claim that this is a common computational step. However, ALS is an iterative algorithms and the time to converge depends considerably on the initial input. Hence, I could assume that the proposed algorithms requires several more iterations to converge. Thus, the algorithm might not be that much faster in practice. I hope this issue can be clarified by the authors. Moreover, a Figure which shows the run-time vs. sketch size and in addition error vs. sketch size for the same data-set would be insightful.   Originality: The theoretical results seem to be different from prior work. In particular the work on rescaled JL embedding is interesting.     Potential impact or usefulness: The usefulness of the proposed algorithm relies mainly on the compute time. However as stated above, the computational gain (in practice) seems somewhat fuzzy. A better illustration of the trade-off between time and error would be useful.   Clarity and presentation: Overall the presentation is very good. The paper is well written. However some of the Figures are non vector graphics, e.g., 1 and 3a. Hence, the Figures look a bit blurry on the printed document or when zooming in.