稀疏矩阵乘积计算中，协同采样比传统方法更省空间且更高效。
Matrix Product Sketching via Coordinated Sampling
- 采用共享随机种子的协同采样，独立生成矩阵压缩快照。
- 稀疏场景下，采样所需存储仅需O(s/ε²)，线性投影需O(d/ε²)或O(m/ε²)。
- 适用于分布式回归与大模型注意力近似，显著降低内存开销。
我们重新研究了基于小规模压缩快照 $ S( A)$ 与 $ S( B)$ 近似矩阵乘积 $ A^T B$ 的经典问题，其中 $ A inom{n imes d}$, $ B inom{n imes m}$。要求快照独立计算，仅共享随机种子。当 $ A$ 与 $ B$ 稀疏时，基于协同随机采样的方法优于经典线性压缩（如 Johnson-Lindenstrauss 投影或 CountSketch）。例如，为获得弗罗贝尼乌斯范数误差 $ε norm{ A} norm{ B}$，协同采样只需大小 $O(s/ε^2)$ 的快照，其中每行非零元不超过 $s leq d,m$；而线性方法则需 $O(d/ε^2)$ 与 $O(m/ε^2)$。我们在两个任务上验证：1）数据库中的分布式线性回归（用于数据集发现与增强）；2）基于 Transformer 的语言模型中注意力矩阵近似。结果表明，采样算法相较线性压缩性能提升一个数量级。
原文摘要 · Abstract (English)
We revisit the well-studied problem of approximating a matrix product, $\mathbf{A}^T\mathbf{B}$, based on small space sketches $\mathcal{S}(\mathbf{A})$ and $\mathcal{S}(\mathbf{B})$ of $\mathbf{A} \in \R^{n \times d}$ and $\mathbf{B}\in \R^{n \times m}$. We are interested in the setting where the sketches must be computed independently of each other, except for the use of a shared random seed. We prove that, when $\mathbf{A}$ and $\mathbf{B}$ are sparse, methods based on \emph{coordinated random sampling} can outperform classical linear sketching approaches, like Johnson-Lindenstrauss Projection or CountSketch. For example, to obtain Frobenius norm error $ε\|\mathbf{A}\|_F\|\mathbf{B}\|_F$, coordinated sampling requires sketches of size $O(s/ε^2)$ when $\mathbf{A}$ and $\mathbf{B}$ have at most $s \leq d,m$ non-zeros per row. In contrast, linear sketching leads to sketches of size $O(d/ε^2)$ and $O(m/ε^2)$ for $\mathbf{A}$ and $\mathbf{B}$. We empirically evaluate our approach on two applications: 1) distributed linear regression in databases, a problem motivated by tasks like dataset discovery and augmentation, and 2) approximating attention matrices in transformer-based language models. In both cases, our sampling algorithms yield an order of magnitude improvement over linear sketching.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。