May, 2024

滑动窗口下的最优矩阵草图

PDF
TL;DR我们介绍了 DS-FD 算法，它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制，证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论，从理论和实证两方面证实了我们算法的正确性和有效性。
matrix sketchingsliding windowsfrequent directions algorithmds-fd algorithmspace bound
发现论文，激发创造
  • Frequent Directions：简单和确定性的矩阵草图

    Frequent Directions 是一种新的确定性矩阵草图算法，适用于行更新模型。它在空间误差权衡中优于现有的流式算法的示例实现。

    Jan, 2015

  • 简单且确定的矩阵草图

    该研究论文介绍了一种基于矩阵素描的流式算法，可用于近似项目频率，具有确定性、易于实现和基本易于证明的优点，并在计算上具有竞争力，比目前广泛使用的方法能够得到更为精确的矩阵素描。

    Jun, 2012

  • Sketchy: 频率方向的内存高效自适应正则化

    通过使用 Frequent Directions sketch 低秩技术，可以减少维护矩阵预处理器的内存和计算量，并在多个大规模基准测试中展示出较好的内存 - 质量 Pareto 前沿。

    Feb, 2023

  • 在线和滑动窗口模型下的近似最优线性代数

    本研究讨论了滑动窗口模型下的数值线性代数问题，提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题，同时通过与在线模型的联系，提出了正文算法，并应用于列 / 行选择、主成分分析等问题。此外，研究还提出了一种新的框架，包括了融合和减少范式和在线核的概念，并且通过行到达在线模型给出了在线核，最终得到了差不多最优空间的定向算法。

    May, 2018

  • 具有保证的改进实用矩阵草图

    本研究对大规模数据分析中矩阵表示及其压缩方法进行了分类和比较，尝试通过优化压缩方法，在保证错误界限的同时实现大小和时间的双重优化。

    Jan, 2015

  • 确定性低秩矩阵逼近的相对误差

    使用 Frequent Directions 算法处理 n x d 矩阵，通过确定性地维护一个 l x d 矩阵 Q 来处理每一行，从而获得一个时间复杂度为 O (d l^2) 的方法，其中 l=k+k/eps 返回最佳秩 k 逼近，同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。

    Jul, 2013

  • 随机投影的精确表达式：低秩逼近与随机牛顿

    利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。

    Jun, 2020

  • 关于绘制二次形式的草图

    本研究对矩阵进行草图，着重探讨了矩阵的不同类型和查询所需的精度。特别地，我们尤其关注了具有特殊特性的正半定矩阵和图拉普拉斯矩阵，为其设计了更优秀的草图，并探讨了草图的实际应用。

    Nov, 2015

  • DPSW-Sketch: 隐私差分化滑动窗口频率估计的草图框架（技术报告）

    在滑动窗口模型中，提出了 DPSW-Sketch，一种基于计数最小化技术的算法，能够满足隐私性要求，并且在子线性时间和空间内近似估计任意项目的频率和重要项，实验结果显示其在效用和隐私权之间取得显著的权衡。

    Jun, 2024

  • 迭代行采样

    该研究提出新的算法解决回归问题中的稀疏数据，基于迭代法中计算行重要性（行杠杆力分数）的方法，达到比现有技术更好的理论保证。

    Nov, 2012