用于删除行的 Cholesky 更新

机器算法验证 贝叶斯 最小二乘 算法 线性代数
2022-04-21 01:56:31

更新 cholesky 分解以从矩阵中删除列的最有效方法是什么?

T = Chol(X' *X)

如果我从 X 中删除一列,如何有效地更新 cholesky。删除 X 的最后一列是微不足道的,因为新的 cholesky 将删除最后一行和最后一列形式 T。删除其他列怎么样?

1个回答

通常的方法包括交换要删除的列和最后一个列的位置,并通过 Givens 旋转或 Householder 变换将 Cholesky 恢复为三角形,然后您可以简单地删除最后一个。

类似地,您可以通过添加到末尾然后交换到所需位置,然后通过 Givens/Householder 转换将其修复为三角形,将附加列更新到任何位置。

当你交换列时,你破坏了你需要它的三角形。然后,每个 Givens 旋转(或 Householder 变换)都会修复“突出”的值之一,直到它们全部修复。这比从头开始重新计算要快得多。

我将讨论旋转(但 Householder 变换做同样的工作,所以很多讨论直接延续)。对于每个“突出”的非零值,您应用一个 Givens 旋转(一个由值组成的 2x2 矩阵,表示通过的旋转),以便它“归零”那个值。它更改其他值,但保留属性。通过从最突出的值开始并朝着三角形的对角线工作,您最终不会丢失您选择归零的值 - 也就是说,如果您以正确的顺序执行操作,那么您在一步仍然为零下一步。sinθcosθθA=RR

Householder 方法更有效一些。


参考。唔。

矩阵计算(Golub 和 Van Loan)有一个关于更新计算的部分 - 12.5.2 “添加或删除列” - 它主要讨论 QR,但许多方法和想法仍然存在。

LINPACK 例程 SCHEX (*) 和其他一些例程的文档实际上是我第一次看到(并且最终理解,很多年前的现在)如何去做(如果你可以访问一个旧用户指南的库)可能可用)。我当时发现它的解释相对简单。

* 该函数只是置换 Cholesky 中变量的顺序;这使用(我认为)吉文斯旋转,这是相对容易找到的信息。

事实上,您可以在网上看到的代码中的文档** 提供了相当丰富的信息。我不确定文档说的远不止这些。描述清楚地使用了吉文斯旋转。

** 我的意思是顶部的评论区

我确定我在某处还有其他东西;我得看看我还有什么其他参考资料。