在线行采样
本研究讨论了滑动窗口模型下的数值线性代数问题,提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题,同时通过与在线模型的联系,提出了正文算法,并应用于列 / 行选择、主成分分析等问题。此外,研究还提出了一种新的框架,包括了融合和减少范式和在线核的概念,并且通过行到达在线模型给出了在线核,最终得到了差不多最优空间的定向算法。
May, 2018
该研究论文介绍了一种基于矩阵素描的流式算法,可用于近似项目频率,具有确定性、易于实现和基本易于证明的优点,并在计算上具有竞争力,比目前广泛使用的方法能够得到更为精确的矩阵素描。
Jun, 2012
该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近,相较于之前基于随机投影的算法,该方法可适用于稀疏结构等场景,并在核矩阵逼近算法方面表现最优。
Nov, 2015
通过选择相应的行,并按照其自身以及原点形成的单形的体积进行概率比例采样,给出了有效的算法。这些算法解决了 Kannan 和 Vempala 的有关谱算法的专著中的一个问题,并且还对低秩矩阵逼近提供了几个有趣的结果。
Apr, 2010
通过研究矩阵的随机子矩阵,证明了用最小可能 O(rlogr)的随机子矩阵(其中 r 是矩阵的数值秩),可以近似计算其谱范数,并给出了在该领域中的最优保证,并使用概率论的方法。Banach 空间中的操作型随机变量的大数定律证明了其工作原理。
Mar, 2005
本文提出了一种新的随机算法,该算法采用特别偏向采样的方法,使误差最小化,可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近,并具有 better dependence on error ε,是一种高度可并行化的优化方法。此外,本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。
Oct, 2014
我们提出了一种动态半流模型下用于计算图形谱稀疏化的首个单趟算法,该算法使用线性素描将 G 的入射矩阵维护为 O ((1/epsilon^2) n*.polylog (n)) 维,可以输出高概率下 G 的 (1+/-epsilon) 谱稀疏化。该方法利用了 G 的粗略稀疏器和 G 的入射矩阵的线性素描,通过等效电阻抽样边缘以得到任意精度的谱稀疏化。
Jul, 2014
本研究探讨了分布式低秩逼近,其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明,在宽泛的函数 f 类别中,可以高效计算一个低秩映射矩阵 P,以满足通信成本为 d∙(sk/ε)^O (1),且算法成功概率高,并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。
Jan, 2016