6
$\begingroup$

So I am running an iterative algorithm. I have matrix $W$ of dimensions $n\times p$ which is fixed for every iteration and matrix $\sqrt{3\rho} \boldsymbol{I}$ of dimension $p\times p$ where the $\rho$ parameter changes at every iteration. And for every iteration I need to evaluate the QR decomposition of the matrix: $$\widetilde{W} = \left[\begin{array}{c} W \\ \sqrt{3\rho} \boldsymbol{I} \end{array} \right] $$ which is a matrix of dimension $(n+p)\times p$. Since $W$ is fixed I wondering if there is any easy way to evaluate the QR decomposition of the matrix $\widetilde{W}$ by just looking at the QR decomposition of $W$? I hope to avoid evaluating the QR decomposition wach time for each different $\rho$.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

EDIT: in the following treat $\mathbf{W}$ as a square matrix. It is thus zero padded with extra rows of zero and singular values also and otherwise unchanged.

For simplicity I drop the $\sqrt{3\rho}$ and use $\alpha$ instead.

Using the SVD of the matrix $\mathbf{W}$, the problem can be transformed into one of doing QR with a fixed unitary matrix $\mathbf{V}^*$ and a parameter diagonal matrix $\mathbf{D}$. Here I show the transform.

Given the SVD of $\mathbf{W} = \mathbf{U}\mathbf{S}\mathbf{V}^*$: $$\pmatrix{\mathbf{W} \\ \alpha \mathbf{I}} = \pmatrix{\mathbf{U}\mathbf{S}\mathbf{V}^* \\ \alpha \mathbf{I}} = \pmatrix{\mathbf{U} & \mathbf{0} \\ \mathbf{0} & \mathbf{V} }\pmatrix{\mathbf{S} \\ \alpha \mathbf{I}}\mathbf{V}^*$$

Since $\mathbf{S}$ is diagonal, $\mathbf{S} = \operatorname{diag}(s_0 , s_1 , s_2, \dots)$, it is easy to do Givens rotations on pairs of rows of the matrix $\pmatrix{\mathbf{S} \\ \alpha\mathbf{I}}$ for a single block diagonal matrix $\pmatrix{\mathbf{D} \\ \mathbf{0}}$ so that we have

$$\pmatrix{\mathbf{W} \\ \alpha \mathbf{I}} = \pmatrix{\mathbf{U} & \mathbf{0} \\ \mathbf{0} & \mathbf{V} }\pmatrix{\mathbf{G}_s & \mathbf{G}_{\alpha} \\ \mathbf{G}_{\alpha} & -\mathbf{G}_s } \pmatrix{\mathbf{D} \\ \mathbf{0}}\mathbf{V}^*$$

Where $$\mathbf{G}_s = \operatorname{diag}\left(\frac{s_0}{\sqrt{s_0^2 + \alpha^2}} , \frac{s_1}{\sqrt{s_1^2 + \alpha^2}}, \frac{s_2}{\sqrt{s_2^2 + \alpha^2}}, \dots\right)$$ And $$\mathbf{G}_{\alpha} = \operatorname{diag}\left(\frac{\alpha}{\sqrt{s_0^2 + \alpha^2}} , \frac{\alpha}{\sqrt{s_1^2 + \alpha^2}}, \frac{\alpha}{\sqrt{s_2^2 + \alpha^2}}, \dots\right)$$ And $$\mathbf{D} = \operatorname{diag}\left(\sqrt{s_0^2 + \alpha^2} , \sqrt{s_1^2 + \alpha^2}, \sqrt{s_2^2 + \alpha^2}, \dots\right)$$

Thus we have an easy parametrization of the SVD. Let $$\mathbf{Q} = \pmatrix{\mathbf{U} & \mathbf{0} \\ \mathbf{0} & \mathbf{V} }\pmatrix{\mathbf{G}_s & \mathbf{G}_{\alpha} \\ \mathbf{G}_{\alpha} & -\mathbf{G}_s } = \pmatrix{\mathbf{U}\mathbf{G}_s & \mathbf{U}\mathbf{G}_{\alpha} \\ \mathbf{V}\mathbf{G}_{\alpha} & -\mathbf{V}\mathbf{G}_s}$$

where $\mathbf{Q}$ can relatively easily be checked as unitary. This then gives the SVD with parameter $\alpha$ as $$\pmatrix{\mathbf{W} \\ \alpha \mathbf{I}} = \mathbf{Q}\pmatrix{\mathbf{D} \\ \mathbf{0}}\mathbf{V}^*$$

Since this just might suit your problem's needs I will end my response here. I did however post the followup question here.

$\endgroup$
4
  • $\begingroup$ Great answer! have a sneaky feeling I'll end up needing it someday.. $\endgroup$ Commented Nov 11, 2013 at 5:30
  • 1
    $\begingroup$ @nbubis Glad to share it. And maybe the SVD should stand for sneaky value decomposition since it seems to sneak up and appear so many places! $\endgroup$
    – adam W
    Commented Nov 11, 2013 at 6:07
  • $\begingroup$ A bit late to the party but you can do away with the SVD here. If you compute the QR factorization of $W$ once and for all (using Householder reflections), you can eliminate the diagonal block $\alpha I$ using a product of $p (p+1) / 2$ Givens rotations, starting from the last column and working you way up, provided there are no zeros on the diagonal of $R$. Typically QR is cheaper to compute than SVD, especially if $W$ is large and sparse. $\endgroup$
    – Dominique
    Commented May 4, 2020 at 19:36
  • $\begingroup$ @Dominique I was thinking that the best benefit would come from the iterative portion having fewer steps, which here are only $p$ Givens rotations. But I like your way in the sense of exactness. $\endgroup$
    – adam W
    Commented May 20, 2020 at 3:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .