# Calculating only the needed part of Q of thin QR decomposition

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.

• $m \le n$? Would Gram-Schmidt suit what you need? (E.g. here) – Paul Aljabar Jan 27 at 11:47
• @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. – geza Jan 27 at 11:57

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.