用于近似矩阵乘法的共现方向素描
Frequent Directions 是一种新的确定性矩阵草图算法,适用于行更新模型。它在空间误差权衡中优于现有的流式算法的示例实现。
Jan, 2015
该研究论文介绍了一种基于矩阵素描的流式算法,可用于近似项目频率,具有确定性、易于实现和基本易于证明的优点,并在计算上具有竞争力,比目前广泛使用的方法能够得到更为精确的矩阵素描。
Jun, 2012
提出一种新的矩阵近似方法,使用基于协同聚类的加法模型取代低秩分解,实现对多维用户偏好数据的高效建模与近似,其优于传统的低秩分解和协同聚类方法,该方法在 Netflix 问题下表现出色。
Dec, 2014
提出了基于草图的迭代算法,用于解决均方误差损失函数加正则项的岭回归问题,针对早期工作中的子空间嵌入要求而使用更弱的近似矩阵乘法保证,为核岭回归提供了更快的算法,同时我们对均方误差损失函数的算法框架提出了切实可行的草图规模下限。
Apr, 2022
通过使用 Frequent Directions sketch 低秩技术,可以减少维护矩阵预处理器的内存和计算量,并在多个大规模基准测试中展示出较好的内存 - 质量 Pareto 前沿。
Feb, 2023
我们介绍了 DS-FD 算法,它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制,证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论,从理论和实证两方面证实了我们算法的正确性和有效性。
May, 2024
介绍了一种学习算法,用于高效的近似矩阵乘法,其常用特性是需要零次乘积添加操作。实验表明,它比现有方法快 10 倍以上,而且比确切矩阵积快 100 倍。此外,核心操作 - 混合哈希,平均和字节混洗,可以是机器学习的更有前途的构建块,而不是近期研究和硬件投资重点的稀疏、因式分解和 / 或标量量化矩阵乘积。
Jun, 2021
使用 Frequent Directions 算法处理 n x d 矩阵,通过确定性地维护一个 l x d 矩阵 Q 来处理每一行,从而获得一个时间复杂度为 O (d l^2) 的方法,其中 l=k+k/eps 返回最佳秩 k 逼近,同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013