Bounding the Frobenius norm of orthogonalised matrices

Question

Context: I am trying to show the convergence of an optimization method which includes orthogonalization in the update step.

Problem: Let's say I have real matrices $A, B \in \mathcal{R}^{n xm}$. If important, $n \gg m$ and I also know that the rank of the matrices is $m$. I can also assume that the norm of each column of $A$ and $B$ is 1. I orthogonalize both matrices using Gram-Schmidt. Let's say the resulting matrices are $Q_A$ and $Q_B$. I need to bound the square of the Frobenius norm of the difference of the matrices ($\|Q_A - Q_B\|_F^2$). Since there might be multiple orthogonalization, I am interested in the upper bound on the minimum of this quantity.

Question: Is there anyway I can bound $\|Q_A - Q_B\|_F^2$ using $\|A-B\|_F^2$ or any function of $A, B$.

Answer 1

There is no such bound. Let $u,v,w$ be orthonormal vectors. The matrices $A=[u,u+\varepsilon v]$ and $B=[u,u+\varepsilon w]$ have Q-factors $Q_A=[u,v]$ and $Q_B = [u,w]$ respectively, so $\|Q_A-Q_B\|$ is constant, but $\|A-B\|$ can be made arbitrarily small. You need to involve the condition number of $A$ and $B$ somehow.

There is a bound involving $\kappa(A)$; check Section 19.9 of Higham's book Accuracy and Stability of Numerical Algorithms.