更新 cholesky 分解以从矩阵中删除列的最有效方法是什么?
T = Chol(X' *X)
如果我从 X 中删除一列,如何有效地更新 cholesky。删除 X 的最后一列是微不足道的,因为新的 cholesky 将删除最后一行和最后一列形式 T。删除其他列怎么样?
更新 cholesky 分解以从矩阵中删除列的最有效方法是什么?
T = Chol(X' *X)
如果我从 X 中删除一列,如何有效地更新 cholesky。删除 X 的最后一列是微不足道的,因为新的 cholesky 将删除最后一行和最后一列形式 T。删除其他列怎么样?
通常的方法包括交换要删除的列和最后一个列的位置,并通过 Givens 旋转或 Householder 变换将 Cholesky 恢复为三角形,然后您可以简单地删除最后一个。
类似地,您可以通过添加到末尾然后交换到所需位置,然后通过 Givens/Householder 转换将其修复为三角形,将附加列更新到任何位置。
当你交换列时,你破坏了你需要它的三角形。然后,每个 Givens 旋转(或 Householder 变换)都会修复“突出”的值之一,直到它们全部修复。这比从头开始重新计算要快得多。
我将讨论旋转(但 Householder 变换做同样的工作,所以很多讨论直接延续)。对于每个“突出”的非零值,您应用一个 Givens 旋转(一个由和值组成的 2x2 矩阵,表示通过的旋转),以便它“归零”那个值。它更改其他值,但保留属性。通过从最突出的值开始并朝着三角形的对角线工作,您最终不会丢失您选择归零的值 - 也就是说,如果您以正确的顺序执行操作,那么您在一步仍然为零下一步。
Householder 方法更有效一些。
参考。唔。
矩阵计算(Golub 和 Van Loan)有一个关于更新计算的部分 - 12.5.2 “添加或删除列” - 它主要讨论 QR,但许多方法和想法仍然存在。
LINPACK 例程 SCHEX (*) 和其他一些例程的文档实际上是我第一次看到(并且最终理解,很多年前的现在)如何去做(如果你可以访问一个旧用户指南的库)可能可用)。我当时发现它的解释相对简单。
* 该函数只是置换 Cholesky 中变量的顺序;这使用(我认为)吉文斯旋转,这是相对容易找到的信息。
事实上,您可以在网上看到的代码中的文档** 提供了相当丰富的信息。我不确定文档说的远不止这些。描述清楚地使用了吉文斯旋转。
** 我的意思是顶部的评论区
我确定我在某处还有其他东西;我得看看我还有什么其他参考资料。