A friend asked me the following interesting question:


$$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$

where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm I}$ is an identity matrix, both of order $n$, and $\xi \in \mathbb{R}$ is a scalar.

Is there an efficient way to compute a QR factorization of $A$?

I have found this question with a very nice answer, but I'd like to avoid doing the SVD because it is computationally expensive and my $R$ is not a constant like $W$ in that other question. Also, my $R$ is already triangular, which I hope can somehow be used.

Edit: There was a comment (turned into an answer while I was writing this edit) on using Givens rotations. Since this is a logical first idea, I'd like to explain why I don't like it.

We could use Givens rotations to cancel out the elements of $\xi{\rm I}$, but each Givens rotation is computing two linear combinations of two rows. That means that if I cancel out the first element of $\xi{\rm I}$, I will also introduce a bunch of non-zeros to the rest of that row.

This means that I would need to go through the whole upper triangle of the bottom block, same as I'd have to do if $\xi{\rm I}$ was a general upper triangular matrix. Given that it is a diagonal matrix (with all its diagonal elements being the same, although I suspect this doesn't help much), I am hoping to get more efficient than that.

  • $\begingroup$ You are right, Givens rotations do not help much. I delete the answer. $\endgroup$ – Jean-Claude Arbaut Nov 29 '13 at 15:08
  • 3
    $\begingroup$ If $A=Q\pmatrix{L^\top\\ 0}$, then $L$ is the matrix for Cholesky decomposition of $R^\top R + \xi^2I$. I don't recall any method to do a diagonal update to Cholesky decomposition in less than $O(n^3)$ time. $\endgroup$ – user1551 Nov 29 '13 at 15:29
  • $\begingroup$ @user1551 Good point. How about making it into an answer, so I have something to accept in case no one comes up with such an updating method? $\endgroup$ – Vedran Šego Nov 29 '13 at 15:38
  • $\begingroup$ Indeed, some savings are possible, e.g., if $R$ is banded. Otherwise the update can be quite costly. $\endgroup$ – Algebraic Pavel Nov 29 '13 at 18:13
  • $\begingroup$ @AlgebraicPavel Unfortunately, $R$ is just a general triangular matrix, with no extra "nicer" structure. $\endgroup$ – Vedran Šego Nov 29 '13 at 19:13

For sake of having an answer ... if $A=Q\pmatrix{L^\top\\ 0}$, then $L$ is the matrix for Cholesky decomposition of $R^\top R+\xi^2I$. As a Cholesky rank-one update already consumes $O(n^2)$ time, I find it hard to believe that a diagonal update can be done in $O(n^2)$ time. However, since this is not a general diagonal update, but a correction by scalar multiple of $I$, perhaps someone could really beat $O(n^3)$ time, although I wouldn't bet on it.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.