2
$\begingroup$

Background

I'm trying to do an update to a "thin" QR decomposition ($A = QR$, where $Q$ is $\mathbf{R}^{m,n}$, the first few columns (up to the matrix rank) of an orthogonal matrix and $R$ is upper triangular and square and $\mathbf{R}^{n,n}$). The matrix itself is a full column rank "tall" matrix ($m \ge n$), and I'm periodically adding and removing columns from $A$ as part of a larger pivoting optimization algorithm.

I'm doing the decomposition in-place inside $A$ using Householder transformations, with the Householder vectors stored in the lower triangular portion of the matrix and $R$ stored in the upper triangular portion of $A$. I need to store the diagonals for $R$ in another extra array. So I only need $\mathcal{O}(n)$ more memory beyond the space of the matrix being decomposed itself.

Requirements

At each step of the pivoting algorithm, I need to calculate

$$R^T(Rx - Q^T f)$$ $$Q Q^T f $$

The $Q^T f$ term in both equations can be calculated without needing to store $Q$ directly just by applying each Householder transformation to $f$ as they come in from newly added columns. That is, at each step $f_{n} := H_n f_{n-1}$ for some Householder transformation $H_n$. Unfortunately I don't see a way to update $Q Q^T f$ in the same way without explicitly storing $Q$ somewhere, so my guess is I still need to hold on to $Q$. ($Q Q^T f$ is basically the projection of $f$ on to the column space of $A$).

Updating

When deleting a column, all the literature I've found recommends using a series of Givens rotations for the "downstream" columns to push them from Hessenberg form back to triangular form. However, I don't have anywhere to store these so I can calculate $Q Q^T f$ when I need it. For the column being removed I need to keep it available to be re-added in the future, so I can't use it for scratch space. Ideally I'd like to do the decomposition using only $\mathcal{O}(n)$ additional memory beyond the space provided by $A$ in the first place.

My question

Is there some other way to push the downstream columns back to triangular format that wouldn't use more memory? I've tried to think of a way to update the Householder transformations, but I haven't been able to figure out a way that isn't $\mathcal{O}(n^3)$. I'd like the update itself to be $\mathcal{O}(n^2)$ as it is with the Givens rotations.

Alternatively, is there a way of updating $Q Q^T f$ at each stage in the pivoting algorithm when a column is added or removed from $A$ without explicitly storing $Q$?

$\endgroup$
  • $\begingroup$ You certainly can't compute $QQ^Tf$ incrementally, but couldn't you just compute it completely at the end? You never need to construct $Q$, just use the Householder reflectors as you are doing now. $\endgroup$ – David Ketcheson Dec 3 '14 at 2:44
  • $\begingroup$ Yes, if Q was just made from Householder reflectors I could do that. The problem is the Givens rotations to push the R matrix back to triangular form when a column is deleted: they're also part of the final Q matrix. So if I wait to calculate $Q Q^T f$ until the very end, I need to hold on to the Givens matrices in some for or another. It's just not clear where to store them in the mean time. Worst case there could be $\mathcal{O}(n^2)$ of them. $\endgroup$ – Jay Lemmon Dec 4 '14 at 4:45
  • $\begingroup$ I don't understand where you get a Hessenberg matrix. But this isn't really my field. $\endgroup$ – David Ketcheson Dec 4 '14 at 6:16
  • $\begingroup$ If you take a triangular matrix and remove a column in the middle of it, all the columns to the right of the removed one are basically in Hessenberg form. $\endgroup$ – Jay Lemmon Dec 4 '14 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.