Low‐rank updates of matrix square roots
Low‐rank updates of matrix square roots
复制标题
矩阵平方根的低阶更新
DOI：
10.1002/nla.2528
复制
发表时间：
2023
影响因子：
4.3
通讯作者：
Avron, Haim
中科院分区：
文献类型：
--
作者：
Shmueli, Shany;Drineas, Petros;Avron, Haim
协方差矩阵具有稀疏矩阵加低秩扰动结构的模型在数据科学应用中普遍存在。通常希望算法能够利用此类结构，避免通常需要三次时间和二次存储的昂贵矩阵计算。这通常是通过执行维持此类结构的操作来完成的，例如通过谢尔曼-莫里森-伍德伯里公式进行矩阵求逆。在本文中，我们考虑矩阵平方根和逆平方根运算。给定矩阵的低秩扰动，我们认为存在对（逆）平方根的低秩近似校正。我们通过在真实校正的特征值上建立几何衰减界限来实现这一点。然后，我们继续将修正构建为代数 Riccati 方程的解，并讨论如何计算该方程的低秩解。我们分析了近似求解代数 Riccati 方程时产生的近似误差，提供了谱和 Frobenius 范数的前向和后向误差界限。最后，我们描述了我们的算法的几种应用，并展示了它们在数值实验中的实用性。
Models in which the covariance matrix has the structure of a sparse matrix plus a low rank perturbation are ubiquitous in data science applications. It is often desirable for algorithms to take advantage of such structures, avoiding costly matrix computations that often require cubic time and quadratic storage. This is often accomplished by performing operations that maintain such structures, for example, matrix inversion via the Sherman–Morrison–Woodbury formula. In this article, we consider the matrix square root and inverse square root operations. Given a low rank perturbation to a matrix, we argue that a low‐rank approximate correction to the (inverse) square root exists. We do so by establishing a geometric decay bound on the true correction's eigenvalues. We then proceed to frame the correction as the solution of an algebraic Riccati equation, and discuss how a low‐rank solution to that equation can be computed. We analyze the approximation error incurred when approximately solving the algebraic Riccati equation, providing spectral and Frobenius norm forward and backward error bounds. Finally, we describe several applications of our algorithms, and demonstrate their utility in numerical experiments.
登录
查看更多内容
矩阵函数的低秩更新 II：Rational Krylov 方法
影响因子：
2.9
作者：
B. Beckermann;Alice Cortinovis;D. Kressner;M. Schweitzer
通讯作者：
M. Schweitzer
低阶代数 Riccati 方程的黎曼方法
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
Bamdev Mishra;Bart Vandereycken
通讯作者：
Bart Vandereycken
计算缩放单位矩阵的低阶扰动的平方根
影响因子：
1.5
作者：
M. Fasi;N. Higham;Xiaobo Liu
通讯作者：
Xiaobo Liu
矩阵函数的低秩更新
影响因子：
1.5
作者：
B. Beckermann;D. Kressner;M. Schweitzer
通讯作者：
M. Schweitzer
有理矩阵函数和 Rank-1 更新
影响因子：
1.5
作者：
D. Bernstein;C. Loan
通讯作者：
C. Loan