Frequent Directions 是一种新的确定性矩阵草图算法,适用于行更新模型。它在空间误差权衡中优于现有的流式算法的示例实现。
Jan, 2015
我们介绍了 DS-FD 算法,它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制,证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论,从理论和实证两方面证实了我们算法的正确性和有效性。
May, 2024
利用随机矩阵的谱分析最新进展,我们开发了一种新的技术,提供了随机投影矩阵的期望值的确切表达式,这些表达式可以用来表征多种常见的机器学习任务中的降维性能,包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法,包括高斯和 Rademacher 草图,结果表明,我们推导出的表达式反映了这些草图方法的实际性能,甚至体现了较低阶效应和恒定因子。
Jun, 2020
该论文介绍了构建输入矩阵的低秩近似的算法套件,这些算法使用矩阵的随机线性图像(称为草图)。这些方法可以保留输入矩阵的结构特性,如半正定性,并且可以生成具有用户指定秩的近似值。此外,每种方法都伴随着一个信息性误差界,允许用户预先选择参数以实现所需的近似质量。这些论断受真实和合成数据的数字实验支持。
Aug, 2016
通过压缩稀疏矩阵,考虑矩阵草图问题,提供针对矩阵非零元素的抽样分布,用最小信息计算以任意顺序呈现且高度可压缩的草图矩阵,且在渐进意义下可以与最优离线分布相竞争。
Nov, 2013
本研究对矩阵进行草图,着重探讨了矩阵的不同类型和查询所需的精度。特别地,我们尤其关注了具有特殊特性的正半定矩阵和图拉普拉斯矩阵,为其设计了更优秀的草图,并探讨了草图的实际应用。
Nov, 2015
本研究提出了基于杠杆得分的矩阵逼近的简洁、直观的在线算法,允许比以前的工作更低的内存使用,并暴露了新的理论性质。
Apr, 2016
本研究对大规模数据分析中矩阵表示及其压缩方法进行了分类和比较,尝试通过优化压缩方法,在保证错误界限的同时实现大小和时间的双重优化。
使用 Frequent Directions 算法处理 n x d 矩阵,通过确定性地维护一个 l x d 矩阵 Q 来处理每一行,从而获得一个时间复杂度为 O (d l^2) 的方法,其中 l=k+k/eps 返回最佳秩 k 逼近,同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013
提出了基于草图的迭代算法,用于解决均方误差损失函数加正则项的岭回归问题,针对早期工作中的子空间嵌入要求而使用更弱的近似矩阵乘法保证,为核岭回归提供了更快的算法,同时我们对均方误差损失函数的算法框架提出了切实可行的草图规模下限。
Apr, 2022