标题： （近似）通过卷积的矩阵乘法 显示英文标题

标题： (Approximate) Matrix Multiplication via Convolutions

摘要： 一个长期悬而未决的算法设计问题是，是否“组合”矩阵乘法算法——避免类似Strassen的分治方法——可以实现真正的亚立方时间复杂度$n^{3-\delta}$。我们提出了一种$O(n^{2.89})$时间的精确算法，该算法仅通过FFT在$\mathbb{Z}_m^k$（多变量多项式乘法）中求和卷积，这是基于Cohn、Kleinberg、Szegedy和Umans（CKSU'05）的工作。尽管该算法避免了递归，但渐进速度提升仅适用于不切实际的大矩阵。受实际应用的启发，我们利用这一基准开发了一个新的快速近似矩阵乘法（AMM）框架，通过CKSU多项式的低次数近似。我们证明，将上述算法与黑箱线性投影结合，已经打破了AMM的长期线性速度-精度权衡（Sarlos'06，Clarkson-Woodruff'13，Pagh'11，Cohn-Lewis'00），在$O(rn^2)$时间内达到$\frac{1}{r^{1.1}}\|\mathbf{A}\|_F^2\|\mathbf{B}\|_F^2$的误差。 我们的主要结果是基于一个傅里叶集中引理，对CKSU多项式的一种低次数近似方案，在分布设置中，$\mathbf{A},\mathbf{B}$来自独立同分布乘积分布时，该方案产生了显著更小的误差；对于随机高斯矩阵，这种实用的AMM算法在时间$O(rn^2)$内达到的误差小于输出矩阵$\mathbf{A}\mathbf{B}$的最佳秩$r$的SVD。 这相对于用于低秩逼近的迭代Krylov子空间方法是一个显著改进。 我们的理论和实验结果表明，在LLM训练和推理中有可能用卷积和代替矩阵乘法。 显示英文摘要

摘要： A longstanding open question in algorithm design is whether "combinatorial" matrix multiplication algorithms -- avoiding Strassen-like divide-and-conquer -- can achieve truly subcubic runtime $n^{3-\delta}$. We present an $O(n^{2.89})$-time exact algorithm, which only sums convolutions in $\mathbb{Z}_m^k$ (multivariate polynomial multiplications) via FFT, building on the work of Cohn, Kleinberg, Szegedy and Umans (CKSU'05). While the algorithm avoids recursion, the asymptotic speedup arises only for impractically large matrices. Motivated by practical applications, we use this baseline to develop a new framework for fast approximate matrix multiplication (AMM), via low-degree approximations of the CKSU polynomials. We show that combining the aforementioned algorithm with black-box linear sketching already breaks the longstanding linear speed-accuracy tradeoff for AMM (Sarlos'06, Clarkson-Woodruff'13 ,Pagh'11, Cohn-Lewis'00), achieving $\frac{1}{r^{1.1}}\|\mathbf{A}\|_F^2\|\mathbf{B}\|_F^2$ error in $O(rn^2)$-time. Our main result is a low-degree approximation scheme for the CKSU polynomials, based on a Fourier-concentration lemma, yielding substantially smaller error in the distributional setting where $\mathbf{A},\mathbf{B}$ come from an i.i.d product-distribution; For random Gaussian matrices, this practical AMM algorithm attains smaller error than the best rank-$r$ SVD of the output matrix $\mathbf{A}\mathbf{B}$, in time $O(rn^2)$. This is a substantial improvement over iterative Krylov subspace methods for low-rank approximation. Our theoretical and empirical results suggest the possibility of replacing MatMuls with sums of convolutions in LLM training and inference.