一种用于低秩近似的快速频率方向算法
Frequent Directions 是一种新的确定性矩阵草图算法,适用于行更新模型。它在空间误差权衡中优于现有的流式算法的示例实现。
Jan, 2015
使用 Frequent Directions 算法处理 n x d 矩阵,通过确定性地维护一个 l x d 矩阵 Q 来处理每一行,从而获得一个时间复杂度为 O (d l^2) 的方法,其中 l=k+k/eps 返回最佳秩 k 逼近,同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013
通过使用 Frequent Directions sketch 低秩技术,可以减少维护矩阵预处理器的内存和计算量,并在多个大规模基准测试中展示出较好的内存 - 质量 Pareto 前沿。
Feb, 2023
本文介绍了一种利用等级约束估计和低维度标签嵌入之间的对应关系发现的快速标签嵌入算法,该算法适用于多类和多标签数据集,并且其运行时间比朴素算法快效果显著,该方法在两个大规模公共数据集上进行了验证,并获得了最先进的结果。
Dec, 2014
本文介绍了一个基于矩阵奇异值分解的矩阵草图方法 ——FREDE,该方法以线性空间复杂度、非线性变换和优质保障作为其基础,可在各种数据科学任务中与最先进的嵌入方法相媲美,即使基于仅 10%的节点相似性。
Jun, 2020
本文提出了利用排名约束估计与低维标签嵌入之间的对应关系来发现一种新的、快速的标签嵌入算法,并展示了其在多类问题和多标签问题中的应用,最终实现了指数级的运行时间优化,其中在两个大规模公共数据集上的结果优于现有技术。
Mar, 2015
本文提出了一种针对欧氏空间的新的 “低质量” 嵌入定义,并应用随机投影将问题降低到与目标空间中近似最近邻的 $k$ 个近似最近邻象限所对应的原像空间的维度成反比的空间中;通过 BBD 树等数据结构,可有效检索这 $k$ 个近似最近邻点。在计算近似近邻问题时,此方法可以获得所需的线性空间和时间复杂度为 $O (d n^{ ho})$ 的查询时间,并可直接解决 approximate nearest neighbor problem 问题,具有比基于 BBD 树的方法更好的查询时间指数。
Dec, 2014
我们介绍了 DS-FD 算法,它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制,证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论,从理论和实证两方面证实了我们算法的正确性和有效性。
May, 2024
本研究探讨了分布式低秩逼近,其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明,在宽泛的函数 f 类别中,可以高效计算一个低秩映射矩阵 P,以满足通信成本为 d∙(sk/ε)^O (1),且算法成功概率高,并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。
Jan, 2016