Randomized numerical linear algebra: Foundations and algorithms
Randomized numerical linear algebra: Foundations and algorithms
复制标题
DOI：
10.1017/s0962492920000021
复制
发表时间：
2020-05-01
期刊：
影响因子：
14.2
通讯作者：
Tropp, Joel A.
中科院分区：
文献类型：
--
作者：
Martinsson, Per-Gunnar;Tropp, Joel A.
本文描述线性代数计算的概率算法，如分解矩阵和求解线性系统。它关注的是那些在解决实际问题方面有良好记录的技术。本文讨论了这门学科的理论基础和实际计算问题。主题包括范数估计、抽样矩阵逼近、结构化和非结构化随机嵌入、线性回归问题、低秩逼近、子空间迭代和Krylov方法、误差估计和自适应、插值和CUR分解、正半定矩阵的Nystrom近似、单视图（“流”）算法、全秩揭示分解、线性系统的求解器、以及在机器学习和科学计算中出现的核矩阵的近似。
This survey describes probabilistic algorithms for linear algebraic computations, such as factorizing matrices and solving linear systems. It focuses on techniques that have a proven track record for real-world problems. The paper treats both the theoretical foundations of the subject and practical computational issues.Topics include norm estimation, matrix approximation by sampling, structured and unstructured random embeddings, linear regression problems, low-rank approximation, subspace iteration and Krylov methods, error estimation and adaptivity, interpolatory and CUR factorizations, Nystrom approximation of positive semidefinite matrices, single-view ('streaming') algorithms, full rank-revealing factorizations, solvers for linear systems, and approximation of kernel matrices that arise in machine learning and in scientific computing.