随机元素级矩阵稀疏化注释
本研究提出一种可以对一个 n x n 的矩阵进行零化处理和元素保留的稀疏化算法,并运用一种新型的非交换 Bernstein 不等式进行分析和比较。
Jun, 2010
该研究提出了一种元素稀疏化算法,基于张量的幂次进行,以及使用了一个用于较好的随机张量估计的不等式,旨在解决张量稀疏化问题并获得新的精度界限以改善算法性能。
May, 2010
本论文解决了计算矩阵多项式的谱稀疏矩阵的基本算法问题,在最近线性时间内构造了一个带有少量非零元的拉普拉斯矩阵,近似于给定的矩阵多项式;该算法可用于多步时间可逆马尔可夫模型的有效电阻的构建,以及网络分析中的其他任务。
Feb, 2015
通过压缩稀疏矩阵,考虑矩阵草图问题,提供针对矩阵非零元素的抽样分布,用最小信息计算以任意顺序呈现且高度可压缩的草图矩阵,且在渐进意义下可以与最优离线分布相竞争。
Nov, 2013
通过研究矩阵的随机子矩阵,证明了用最小可能 O(rlogr)的随机子矩阵(其中 r 是矩阵的数值秩),可以近似计算其谱范数,并给出了在该领域中的最优保证,并使用概率论的方法。Banach 空间中的操作型随机变量的大数定律证明了其工作原理。
Mar, 2005
该研究论文介绍了一种基于矩阵素描的流式算法,可用于近似项目频率,具有确定性、易于实现和基本易于证明的优点,并在计算上具有竞争力,比目前广泛使用的方法能够得到更为精确的矩阵素描。
Jun, 2012
本文介绍了一种计算部分秩相因分解的方法,该方法采用随机取样避免了列交换,从而使得计算速度得到了大幅提升,并且在各种矩阵上都表现出色,特别是在 GPU 结构上表现尤为突出。
Mar, 2015
本文研究了在多种范数下,通过稀疏随机矩阵 X 逼近实数矩阵 A 的问题,其中包括了图算法中更适用的 $(\infty,1)$ 范数和 $(\infty,2)$ 范数。文章提出的界限适用于大多数随机稀疏化模式,证明了 $(\infty,1)$ 和 $(\infty,2)$ 误差评估的最优性。文章还给出了当 X 的元素被均匀限制时三个范数的浓度结果。
Nov, 2009
本文提出了一种新的随机算法,该算法采用特别偏向采样的方法,使误差最小化,可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近,并具有 better dependence on error ε,是一种高度可并行化的优化方法。此外,本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。
Oct, 2014
本文提出了新技术,以加速机器学习中最近流行的张量算法,并通过一种新的随机方式仅选择可能 n^3 元素的 O (n ^ 1.5/ Epsilon ^ 2) 元素,以达到张量稀疏化,张量完成和张量因子化的三个目的。
Feb, 2015