背景

我正在尝试对“瘦” QR 分解进行更新（$A = QR$， 在哪里$Q$是$\mathbf{R}^{m,n}$，正交矩阵的前几列（直到矩阵秩）和$R$是上三角形和正方形并且$\mathbf{R}^{n,n}$）。矩阵本身是一个全列秩“高”矩阵（$m \ge n$)，并且我会定期添加和删除列$A$作为更大的旋转优化算法的一部分。

我正在内部进行就地分解$A$使用 Householder 变换，Householder 向量存储在矩阵的下三角部分，$R$存储在上三角部分$A$. 我需要存储对角线$R$在另一个额外的数组中。所以我只需要$\mathcal{O}(n)$超出被分解的矩阵空间的更多内存。

要求

在旋转算法的每一步，我需要计算

这$Q^T f$无需存储即可计算两个方程中的项$Q$直接通过将每个 Householder 转换应用于$f$因为它们来自新添加的列。也就是说，在每一步$f_{n} := H_n f_{n-1}$对于一些户主转型$H_n$. 不幸的是，我没有看到更新的方法$Q Q^T f$以同样的方式，无需显式存储$Q$某处，所以我的猜测是我仍然需要坚持$Q$. ($Q Q^T f$基本上是投影$f$到的列空间$A$）。

更新

删除列时，我发现的所有文献都建议对“下游”列使用一系列 Givens 旋转，以将它们从 Hessenberg 形式推回三角形形式。但是，我没有地方可以存储这些，所以我可以计算$Q Q^T f$当我需要它的时候。对于要删除的列，我需要保留它以便将来重新添加，所以我不能将它用于暂存空间。理想情况下，我只想使用$\mathcal{O}(n)$超出提供的空间的额外内存$A$首先。

我的问题

是否有其他方法可以将下游列推回不使用更多内存的三角形格式？我试图想出一种方法来更新 Householder 转换，但我一直无法找到一种方法$\mathcal{O}(n^3)$. 我希望更新本身是$\mathcal{O}(n^2)$就像吉文斯轮换一样。

或者，有没有更新的方法$Q Q^T f$在透视算法的每个阶段添加或删除列时$A$没有明确存储$Q$?