Continuity of the thin QR factorization.

73 Views Asked by At

In section 5.2 of the book Matrix Computations by Golub & Van Loan we can find the following result:

Let $A\in\mathbb R^{m\times k}$ be a matrix with full column rank. Then we have the factorization $A=QR$ for some matrix $Q\in \mathbb R^{m\times k}$ with orthonormal columns and some upper triangular matrix $R \in \mathbb R^{k\times k}$ with positive diagonal entries. Moreover the factorization is unique and is called the thin QR factorization of $A$.

I want to show that the factorization is continuous with respect to $A$.

So let $(A_n)$ be a sequence of matrices in $\mathbb R^{m\times k}$, each with full column rank, and suppose that $A_n\to A$. For each $n$, let $Q_nR_n$ denote the thin factorization of $A_n$.

Suppose $Q_{n'}\to Q_0 \in \mathbb R^{m\times k}$ for some subsequence $n'$. Then $Q_0^\top Q_0=\lim Q_{n'}^\top Q_{n'} =I_k$ so $Q_0$ has orthonormal columns. Moreover we have $R_{n'}=Q^\top_{n'}Q_{n'}R_{n'}=Q^\top_{n'}A_{n'}\to R_0$ where $R_0=Q^\top_0A$. Since each $R_{n'}$ is upper triangular with nonnegative diagonal entries, so is $R_0$. Moreover we have

$$QR=\lim Q_{n'}R_{n'}=Q_0R_0$$

and so $\text{rank}(R_0)=\text{rank}(Q_0R_0)=\text{rank}(QR)=\text{rank}(R)=k$. Therefore the diagonal entries of $R_0$ are in fact positive. From the uniqueness of the thin factorization we conclude that $Q_0=Q$ and $R_0=R$.

We have shown that any convergent subsequence of $(Q_n)$ must converge to $Q$. We claim that this implies that $Q_n\to Q$. Otherwise we can construct a subsequence $(Q_{n'})$ which is bounded away from $Q$ by some distance greater than some $\epsilon>0$. Since $\|Q_n\|=\sqrt{k}$ for all $n$, the sequence $(Q_{n'})$ is bounded, and so we can extract a further subsequence converging to some matrix other than $Q$, a contradiction.

Hence $Q_n\to Q$, and repeating the first part of the proof we get $R_n\to R$ as well.

Is this proof correct?

Thanks a lot for your help.

1

There are 1 best solutions below

0
On BEST ANSWER

This looks correct to me. The subsequence argument is a standard one. It can be modified in many ways, e.g. by exploiting that the set of such $Q$ is compact and thus any subsequence $Q_{n'}$ must contain a convergent sub-subsequence which must then converge to $Q$.

You can also prove the continuity of the decomposition by observing that $Q$ is constructed column wise from left to right by means of the Gram-Schmidt process. Each step in the process is a continuous operation which turns a column of $A$ into the corresponding column of $Q$. Then use induction over $k$.

Yet another way is to show that the construction of $R$ via the Cholesky process is a finite sequence of continuous operations.