Sublinear Cost Low Rank Approximation via Subspace Sampling
Sublinear Cost Low Rank Approximation via Subspace Sampling
复制标题
通过子空间采样的次线性成本低阶近似
DOI：
10.1007/978-3-030-43120-4_9
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhao, L
中科院分区：
文献类型：
--
作者：
Pan, V;Luan, Q;Svadlenka, J;Zhao, L
矩阵的低阶近似（LRA）是一个热门研究课题，是矩阵和张量计算以及大数据挖掘和分析的基础。 LRA 的计算可以以亚线性成本执行，即使用比输入矩阵条目少得多的存储单元和算术运算。尽管 LRA 的每个次线性成本算法都无法逼近最坏情况的输入，但我们证明了流行子空间采样算法的次线性成本变化可以输出一大类输入的准确 LRA。也就是说，对于承认其 LRA 的随机输入矩阵，它们以高概率 (whp) 执行此操作。在其他论文中，我们提出并分析了 LRA 和线性最小二乘回归的其他次线性成本算法。我们的数值测试与我们的正式结果非常一致。
Low Rank Approximation (LRA) of a matrix is a hot research subject, fundamental for Matrix and Tensor Computations and Big Data Mining and Analysis. Computations with LRA can be performed atsublinear cost, that is, by using much fewer memory cells and arithmetic operations than an input matrix has entries. Although every sublinear cost algorithm for LRA fails to approximate the worst case inputs, we prove that our sublinear cost variations of a popular subspace sampling algorithm output accurate LRA of a large class of inputs.Namely, they do so with a high probability (whp) for a random input matrix that admits its LRA. In other papers we propose and analyze other sublinear cost algorithms for LRA and Linear Least Sqaures Regression. Our numerical tests are in good accordance with our formal results.
登录
查看更多内容
无旋转的数值安全高斯消去法
DOI：
10.1016/j.laa.2017.04.007
发表时间：
2015
期刊：
arXiv: Symbolic Computation
影响因子：
--
作者：
V. Pan;Liang Zhao
通讯作者：
Liang Zhao
DOI：
10.1016/j.laa.2016.09.035
发表时间：
2014
期刊：
arXiv: Numerical Analysis
影响因子：
--
作者：
V. Pan;Liang Zhao
通讯作者：
Liang Zhao
基于体积最大化的次线性成本 CUR LRA
DOI：
--
发表时间：
2019
期刊：
Mathematical Aspects of Computer and Information Sciences (MACIS 2019
影响因子：
--
作者：
Luan, Q;Pan, V
通讯作者：
Pan, V
随机乘法器在数值上稳定高斯和块高斯消除：证明和低阶近似的扩展☆
影响因子：
1.1
作者：
V. Pan;G. Qian;Xiaodong Yan
通讯作者：
Xiaodong Yan