3
$\begingroup$

A rectangular, $A \in \mathbb{R}^{m \times n}$ matrix, where $m \ge n$, can be decomposed (QR factorization): $$A = \begin{bmatrix}Q_1 | Q_2 \end{bmatrix}\begin{bmatrix}R\\0\end{bmatrix}$$ where $Q_1$ and $Q_2$ has orthonormal columns, and $R$ is upper triangular.

I'm implementing a routine (based on Householder reflections) which calculates $Q_1$ and $R$ (so called thin/reduced QR decomposition).

My question is: is it possible to calculate $Q_1$ without calculating $Q_2$? The problem is that a Householder matrix is $\mathbb{R}^{m \times m}$, and $Q_1 \in \mathbb{R}^{m \times n}$, so I cannot multiply them. My routine currently calculates $Q=[Q_1|Q_2]$, and then throws away the $Q_2$ part.

$\endgroup$
  • $\begingroup$ $m \le n$? Would Gram-Schmidt suit what you need? (E.g. here) $\endgroup$ – Paul Aljabar Jan 27 at 11:47
  • 1
    $\begingroup$ @PaulAljabar: in the case of thin QR decomposition, $A$ has more rows than columns (for the other case, "wide'' matrices, thin QR factorization is not a thing). I'd like to keep using Householder reflection, as it is numerically more stable. $\endgroup$ – geza Jan 27 at 11:57
1
$\begingroup$

Yes, it is possible, and it is quite straightforward:$$R=H_nH_{n-1}\dots H_1A,$$ where $H_*$ are the Householder reflectors. So, $$Q = H_1^T\dots H_{n-1}^TH_n^T.$$

As $H_*$ are symmetric: $$Q = H_1\dots H_{n-1}H_n.$$

Now, to compute $Q_1$, we have:$$Q_1 = H_1\dots H_{n-1}H_nI^{m \times n},$$where $I^{m \times n} \in \mathrm{R}^{m \times n}$ is the rectangular identity matrix.

$Q_1$ can be calculated backwards: first calculate $H_nI^{m \times n}$, the result is a $m \times n$ matrix. Then multiply left this with $H_{n-1}$, then $H_{n-2}$, and so on.

This way, the full $Q$ doesn't have to be formulated.

$\endgroup$

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.