论文标题
矩阵乘法和山脊回归的局部草图
Localized sketching for matrix multiplication and ridge regression
论文作者
论文摘要
我们考虑在新的局部草图环境中绘制概述的近似矩阵乘法和脊回归，在任何给定点，只有一部分数据矩阵可用。这对应于草图矩阵上的块对角线结构。我们表明，在温和条件下，块对角素描矩阵仅需要O（稳定等级 /ε^2）和$ O（stat。im。ε）$分别用于矩阵乘法和脊回归的总样品复杂性。这匹配使用全局草图矩阵获得的最新界限。所考虑的草图的本地化性质允许独立绘制数据矩阵的不同部分，因此更适合分布式和流式设置中的计算，并导致较小的内存和计算足迹。
We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching, where at any given point, only part of the data matrix is available. This corresponds to a block diagonal structure on the sketching matrix. We show that, under mild conditions, block diagonal sketching matrices require only O(stable rank / ε^2) and $O( stat. dim. ε)$ total sample complexity for matrix multiplication and ridge regression, respectively. This matches the state-of-the-art bounds that are obtained using global sketching matrices. The localized nature of sketching considered allows for different parts of the data matrix to be sketched independently and hence is more amenable to computation in distributed and streaming settings and results in a smaller memory and computational footprint.
