压缩矩阵乘法
用子空间嵌入保证黑盒方式证明,通过降维映射可实现近似矩阵乘法的谱范数保障,其中降维映射具有 O(~r/ε^2)行,且优于以前的工作 [MZ11,KVZ14],对于任何混淆的降维映射也是最佳的。
Jul, 2015
介绍了一种学习算法,用于高效的近似矩阵乘法,其常用特性是需要零次乘积添加操作。实验表明,它比现有方法快 10 倍以上,而且比确切矩阵积快 100 倍。此外,核心操作 - 混合哈希,平均和字节混洗,可以是机器学习的更有前途的构建块,而不是近期研究和硬件投资重点的稀疏、因式分解和 / 或标量量化矩阵乘积。
Jun, 2021
本文提出了一种新的算法,通过仅对两个矩阵进行一次遍历即可计算出 $A^TB$ 的低秩逼近,该算法保留有关 A、B 的附加信息(例如行和列范数等)并利用这些附加信息从草图中获得改进的逼近。我们的主要分析结果将该方法的谱范数保证与现有的两个遍历方法相媲美,并且我们还提供了 Apache Spark 实现的结果,显示在实际和合成评估数据集上具有更好的计算性能和统计性能。
Oct, 2016
该论文研究了计算两个实矩阵乘积的近似算法,提出了核秩的概念,并应用于线性低维嵌入中,使得任何核秩有界的欧几里得点集能够在独立于输入维度的投影空间上实现加性误差保证。
Mar, 2014
本文提出一项新的算法,使用随机痕量估计方法,多项式逼近,以及快速系统求解器等高效地获得一个矩阵的奇异值谱的直方图,并用其来求解一类对称矩阵范数。同时,证明了精度高的算法可以在次立方时间内进行矩阵乘法,从而限制了计算有效电阻的难度。
Apr, 2017
本研究提出一种可以对一个 n x n 的矩阵进行零化处理和元素保留的稀疏化算法,并运用一种新型的非交换 Bernstein 不等式进行分析和比较。
Jun, 2010
通过研究矩阵的随机子矩阵,证明了用最小可能 O(rlogr)的随机子矩阵(其中 r 是矩阵的数值秩),可以近似计算其谱范数,并给出了在该领域中的最优保证,并使用概率论的方法。Banach 空间中的操作型随机变量的大数定律证明了其工作原理。
Mar, 2005