TL;DR
This paper introduces a novel, faster algorithm for approximating matrix multiplication using a technique called "matrix sketching." By sparsifying one of the matrices before multiplication, they achieve comparable accuracy to existing methods but with significantly reduced computational cost, especially for large datasets.
What Problem Does This Paper Address?
Matrix multiplication is a fundamental operation in many computational tasks, from machine learning to scientific computing. However, for very large matrices, the standard "naive" multiplication algorithm becomes computationally prohibitive, taking $O(d_A d_B m)$ time. Existing approximate methods, like those using random projections or column sub-sampling, offer speedups but still have significant computational demands, particularly in the preprocessing or sampling stages. This paper aims to develop an approximate matrix multiplication algorithm that is both accurate and more computationally efficient, especially when dealing with massive datasets where $m$ is much larger than the matrix dimensions $d_A$ and $d_B$.
Methods
The core of the proposed method is "entry-wise matrix sketching." Instead of sampling entire columns or using random projections, the algorithm sparsifies one of the input matrices (say, matrix $A$) by randomly selecting and keeping only a subset of its entries. This sparsification is done using an "online matrix sketching algorithm," which means it can be performed iteratively. Once matrix $A$ is sparsified into $\hat{A}$, the approximate matrix product is computed as $\hat{A}B^T$.
The paper then provides theoretical guarantees for the accuracy of this approximation. They prove that with a sufficient number of samples (controlled by $T$), the error between the approximated product $\hat{A}B^T$ and the true product $AB^T$ is bounded with high probability. The analysis involves bounding the norm of independent errors and the variance of the approximation, leveraging techniques like Matrix Bernstein inequalities.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Entry-wise Sparsification is Key: The paper demonstrates that sparsifying individual entries of a matrix, rather than entire columns, can be an effective strategy for approximate matrix multiplication. This is a departure from some prior work that focused on column sub-sampling.
- Computational Efficiency: By sparsifying only one matrix and avoiding complex sampling procedures like Fast Fourier Transforms or Random Hardamard Transforms, the proposed algorithm significantly reduces the computational cost, particularly in the preprocessing/sampling phase.
- Theoretical Guarantees: The authors provide rigorous mathematical proofs that establish the accuracy of their sketched approximation, showing that it can achieve similar error bounds to existing methods with fewer computations.
- Scalability for Big Data: The algorithm is particularly well-suited for scenarios where one dimension ($m$) of the matrices is much larger than the others ($d_A, d_B$), a common characteristic of "big data" problems.
Key Results
The main quantitative result is a bound on the approximation error: $||\hat{A}B^T - AB^T||_2 \leq \eta ||A||_2 ||B||_2$ with probability at least $1 - \delta$. This bound is achieved when the number of samples $T$ is sufficiently large, specifically: $T > \frac{C k_A(\alpha) k_B \log(d_A+d_B)}{\eta^2 \delta}$ where $k_B$ is related to the stable rank of $B$, $k_A(\alpha)$ is a term dependent on the sparsification parameter $\alpha$ and the entries of $A$, and $C$ is a constant.
Crucially, the paper argues that the computational cost for sampling matrix $A$ is $O(d_A d_B m)$, which is significantly better than some prior methods that might require $O((d_A+d_B)m)$ for sampling. When $m \gg d_A$ and $m \gg d_B$, the cost is dominated by $O(d_A d_B m)$, and the paper claims their method can reduce this to $O(\min\{d_A, d_B\}m)$ in certain cases.
Limitations and Future Work
- Parameter Tuning: The accuracy and efficiency of the algorithm depend on the choice of parameters like $\alpha$ (for sparsification) and $T$ (number of samples). The paper provides theoretical bounds for these, but practical tuning might be necessary.
- "Stable Rank" Dependency: The theoretical bounds involve terms like the "stable rank" of matrices, which can be computationally expensive to determine precisely.
- Future Work: The paper suggests that further exploration of truncation methods (as hinted in Section 5) could be beneficial for handling very small entries in matrices. Additionally, the comparison with previous works in Section 6 implies that further empirical validation and comparison on real-world datasets would be valuable. The authors also note that their algorithm is particularly effective when $m$ is large, suggesting future work could explore its performance in other regimes.
Summary updated