我们介绍了 DS-FD 算法,它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制,证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论,从理论和实证两方面证实了我们算法的正确性和有效性。
May, 2024
使用 Frequent Directions 算法处理 n x d 矩阵,通过确定性地维护一个 l x d 矩阵 Q 来处理每一行,从而获得一个时间复杂度为 O (d l^2) 的方法,其中 l=k+k/eps 返回最佳秩 k 逼近,同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013
该研究论文介绍了一种基于矩阵素描的流式算法,可用于近似项目频率,具有确定性、易于实现和基本易于证明的优点,并在计算上具有竞争力,比目前广泛使用的方法能够得到更为精确的矩阵素描。
Jun, 2012
通过使用 Frequent Directions sketch 低秩技术,可以减少维护矩阵预处理器的内存和计算量,并在多个大规模基准测试中展示出较好的内存 - 质量 Pareto 前沿。
Feb, 2023
介绍了一种基于共现方向的确定性算法,用于流式处理下的矩阵乘积近似,与其他随机和确定性方法相比,共现方向实现了更好的近似误差界限。算法可在较小的草图规模下实现最佳低秩逼近的 $1+ε$- 近似,实验证明该算法胜过竞争算法。
Oct, 2016
本文提出了一种使用随机化算法(稀疏子空间嵌入)以降低计算成本的快速频繁方向算法,它在低秩逼近问题中工作得很好并且利用了频繁方向的自然块结构和稀疏子空间嵌入向每个块发送更多信息,该算法有效且高效,通过在合成和真实数据集上的实验结果以及在网络分析中的应用进行了证明。
May, 2017
本研究对大规模数据分析中矩阵表示及其压缩方法进行了分类和比较,尝试通过优化压缩方法,在保证错误界限的同时实现大小和时间的双重优化。
Jan, 2015
该研究提出新的算法解决回归问题中的稀疏数据,基于迭代法中计算行重要性(行杠杆力分数)的方法,达到比现有技术更好的理论保证。
Nov, 2012
利用随机矩阵的谱分析最新进展,我们开发了一种新的技术,提供了随机投影矩阵的期望值的确切表达式,这些表达式可以用来表征多种常见的机器学习任务中的降维性能,包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法,包括高斯和 Rademacher 草图,结果表明,我们推导出的表达式反映了这些草图方法的实际性能,甚至体现了较低阶效应和恒定因子。
Jun, 2020
该论文介绍了构建输入矩阵的低秩近似的算法套件,这些算法使用矩阵的随机线性图像(称为草图)。这些方法可以保留输入矩阵的结构特性,如半正定性,并且可以生成具有用户指定秩的近似值。此外,每种方法都伴随着一个信息性误差界,允许用户预先选择参数以实现所需的近似质量。这些论断受真实和合成数据的数字实验支持。
Aug, 2016