May, 2018

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

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

    本研究提出了基于杠杆得分的矩阵逼近的简洁、直观的在线算法，允许比以前的工作更低的内存使用，并暴露了新的理论性质。

    Apr, 2016

  • 滑动窗口上的次模优化

    本文在数据流的上下文中，提供了一种基于滑动窗口模型的次模优化的近似算法，该算法维护了一个解决方案，考虑的仅是最后 $W$ 个元素，使用空间多项式对元素值的传播速度的对数级别，线性大小的解决方案，并保持高品质的解，实际表现远超理论界限。

    Oct, 2016

  • 通过 Ridge Leverage Score 抽样进行输入稀疏时间低秩逼近

    该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近，相较于之前基于随机投影的算法，该方法可适用于稀疏结构等场景，并在核矩阵逼近算法方面表现最优。

    Nov, 2015

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

    我们介绍了 DS-FD 算法，它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制，证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论，从理论和实证两方面证实了我们算法的正确性和有效性。

    May, 2024

  • 流式大数据矩阵和张量的子空间学习和插补

    论文提出了一种基于 rank minimization 算法的在线优化方法，通过追踪低维度子空间、揭示潜在结构以及使用核范数正则化来实现低维矩阵数据和低秩张量数据的缺失值插补，模拟测试显示该方法在数据明显含噪、不完整的情况下表现突出。

    Apr, 2014

  • 在线线性规划的动态近最优算法

    本文提出了一种基于学习的在线线性规划算法，可应用于许多在线资源分配和收入管理问题，具有良好的竞争优势。

    Nov, 2009

  • 关于矩阵完成和逼近中自适应能力的探讨

    本文介绍了一种自适应采样算法，可以高效地完成低秩近似和矩阵填充任务，并且消除了之前文献中存在的某些限制性假设，具有更好的采样复杂度。

    Jul, 2014

  • 量子启发的次线性经典算法求解低秩线性系统

    本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。

    Nov, 2018

  • 流式 PCA：匹配矩阵伯恩斯坦和 Oja 算法的几乎最优有限样本保证

    该研究提出了一个对流式主成分分析（PCA）有改进保证的线性时间算法，该算法可以在常数精度下估计协方差矩阵的前几个特征向量。该算法通过一种新颖的 Oja 算法分析方法实现。

    Feb, 2016

  • 迭代行采样

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

    Nov, 2012