.png){kind=icon}
返回
Accelerating Randomized Algorithms for Low-Rank Matrix Approximation
.png){kind=icon}
PRE
AI
DOI：10.1007/s10915-026-03403-8.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
随机算法是低秩逼近中占主导地位的方法，相比确定性算法，它们能够以极高的可靠性缓解计算开销。一个关键思路是生成标准高斯矩阵 $${\textbf{G}}$$，并随后获取给定矩阵 $${\textbf{A}}$$ 的 $${\textbf{AG}}$$ 范围的正交基。最近，farPCA 算法为随机算法提供了一种框架，但密集高斯矩阵的计算仍然昂贵。受此启发，我们引入标准化伯努利矩阵、稀疏符号矩阵和稀疏高斯矩阵，用于替代 farPCA 中的标准高斯矩阵以加速计算。这三种矩阵在矩阵-矩阵乘法中具有低计算开销，并且在乘以正交矩阵时，在温和条件下按元素收敛于标准高斯矩阵。因此，三种相应的算法可以成为 farPCA 的更优替代方案。最后，我们利用随机矩阵理论（RMT）推导出无需移位技术的 farPCA 更紧致误差界。此外，我们将此改进的误差界扩展到我们三种快速算法的误差分析中，确保所提出的方法能为大规模矩阵提供更精确的逼近。数值实验验证了这三种算法在渐近性能上与 farPCA 相同，但成本更低，为低秩矩阵逼近提供了一种更高效的方法。
Keyword:
Low-rank matrix approximation
SVD decomposition
Randomized algorithm
Bernoulli matrix
Random matrix theory
期刊
IF:
3.3
论文数:
750
被引数:
9.6K
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏A RANDOMIZED BLOCKED ALGORITHM FOR EFFICIENTLY COMPUTING RANK-REVEALING FACTORIZATIONS OF MATRICES
OAAI
OAAI分享收藏
查看更多内容