How to compute QR decomposition of a product of matrices

Question

Suppose I have $A=A_nA_{n-1}\cdots A_2A_1$

How can I compute the $QR$ factorization of $A$ without explicitly multiplying $A_1, A_2, \ldots, A_n$ together?

The suggestion I got is that, suppose $n=3$ and $Q_3^T A =R$

The write $$Q_3^T A =Q_3^T A_3Q_2Q_2^T A_2Q_1Q_1^T A_1Q_0, Q_0=I$$

Then find orthogonal $Q_i$ such that $Q_i^T A_iQ_{i-1}$ is upper triangular.

Answer 1

The main reason to compute the QR factorization of the product rather than multiplying them all together is to keep the condition numbers in check. It is not more efficient (nor is it substantially less efficient computationally due to good cache utilization in modern QR implementations).

You compute $A_1 = QR$, then apply $Q^T$ from the right to $A_2$, then repeat until you get to $A_n$. In summary:

tmp = A_1
for i = 1 to n
    [Q,R_i] = qr(tmp);
    tmp = A_{i+1} * Q^T
end
R = R_n * R_{n-1} * ... * R_1

The last $Q$ computed is the $Q$ of the product, and the product of all the intermediate $R$ matrices is the $R$ of the product.