Abstract
Computing low-rank approximations of matrix products $A^T B$ is a fundamental task in large-scale data analysis, particularly for capturing interactions between massive datasets. Traditional methods often require multiple passes over data or suffer from high memory requirements. We introduce SMP-PCA (Streaming Matrix Product PCA), a novel algorithm that computes a low-rank approximation in a single pass. By integrating random sketching with a "rescaled" Johnson-Lindenstrauss embedding that utilizes column norms as side information, SMP-PCA achieves significant performance gains. In distributed Apache Spark environments, the algorithm provides a 2x speedup over previous two-pass methods while maintaining high spectral norm accuracy.
Introduction
In modern data science, we frequently encounter scenarios where we must analyze the interaction between two large-scale matrices, $A \in \mathbb{R}^{d \times n_1}$ and $B \in \mathbb{R}^{d \times n_2}$. The product $M = A^T B$ captures these interactions, but its direct computation is often infeasible due to memory and I/O constraints. While Principal Component Analysis (PCA) can provide a low-rank summary of $M$, standard SVD requires the full product, and iterative power methods require multiple passes over the raw data—a significant bottleneck for disk-resident or streaming datasets.
Existing randomized approaches typically require at least two passes: one to estimate importance (e.g., column norms) and another for sampling. SMP-PCA addresses this by performing sketching and norm recording simultaneously in a single pass, enabling efficient computation in streaming and distributed settings.
Methodology: The SMP-PCA Pipeline
The SMP-PCA algorithm operates through a three-stage process designed to minimize data access while maximizing approximation quality.
- Sketching and Side Information Acquisition: As $A$ and $B$ stream through the system, the algorithm computes sketches $\tilde{A} = \Pi A$ and $\tilde{B} = \Pi B$ using a random projection matrix $\Pi$. Crucially, it also records the $L_2$ norms of every column in $A$ and $B$. This "side information" is negligible in size but critical for error reduction.
-
Rescaled Johnson-Lindenstrauss (JL) Embedding: Standard sketching can distort vector norms, introducing noise into dot product estimates. SMP-PCA employs a "rescaled" estimator for each entry $(i, j)$ of the product: $$\tilde{M}(i, j) = \|A_i\| \cdot \|B_j\| \cdot \frac{\tilde{A}_i^T \tilde{B}_j}{\|\tilde{A}_i\| \cdot \|\tilde{B}_j\|}$$ By normalizing the sketched dot product and re-introducing the true norms, the algorithm effectively cancels out the variance introduced by the random projection.
-
Biased Sampling and Matrix Completion: Rather than reconstructing the entire matrix $M$, the algorithm uses the recorded norms to identify and sample "important" entries. A Weighted Alternating Least Squares (WAltMin) approach is then used to complete the low-rank factors $U$ and $V^T$ from these samples.
Experimental Results
SMP-PCA was evaluated against synthetic datasets and real-world benchmarks including SIFT10K, NIPS-BW, and a massive URL-reputation dataset.
Computational Efficiency
In distributed tests using Apache Spark on a 150GB dataset, SMP-PCA demonstrated a 2x speedup over LELA, the previous state-of-the-art two-pass algorithm. This improvement is directly attributable to the elimination of the second data pass, which significantly reduces I/O overhead in distributed clusters.
Approximation Accuracy
The "rescaling" technique provides a substantial accuracy boost. On the SIFT10K dataset, SMP-PCA outperformed standard single-pass sketching (SVD of the sketch product) by a factor of 1.8x in terms of spectral norm error. Theoretical analysis confirms that SMP-PCA provides error bounds comparable to two-pass methods, despite the single-pass constraint.
Conclusion
SMP-PCA demonstrates that high-quality low-rank approximations of matrix products can be achieved in a single pass by intelligently leveraging side information. The combination of sketching and rescaled estimation offers a robust framework for large-scale interaction analysis. While performance can be sensitive to the orthogonality of the input matrices, the algorithm's efficiency in distributed environments makes it a powerful tool for modern big data pipelines.
Summary updated