Relating orthogonal column distances to basis distances I have two $d\times r$ matrices $X$ and $Y$, with $X^TX=Y^TY=I_r.$ It is also known that the columns $X_i$ and $Y_i$ for $i=1,\dots,r$ satisfy $$\underset{i}{\max}\Vert X_i-Y_i\Vert_2\le \varepsilon.$$ Can I then say that $\Vert XX^T-YY^T\Vert_2\le c\varepsilon,$ for some constant $c$ (free of $d$ and $r$)?
The last norm refers to the spectral norm, i.e., $\Vert A\Vert_2=\underset{v^Tv=1}{\sup}\Vert Av\Vert_2.$
 A: No, there is no such $c$ in general. Consider the case $d = r+1$ (though the following construction works in any $d > r$). Let $e_1, \dots, e_{r+1}$ be the the standard basis vectors of $\mathbb{R}^{r+1}$ (considered as column vectors), so they are orthonormal. Also define $u = \frac{1}{\sqrt{r}}e_{r+1} - \frac{1}{r}(e_1 + \cdots + e_r)$. Now consider the $(r+1) \times r$ matrices $X$ and $Y$ given by the column vectors $X_i = e_i$ and $Y_i = e_i + u$ for $i = 1, \dots, r$. The $X_i$'s are clearly orthonormal, and with a bit of work you can check that the $Y_i$'s are orthonormal as well, giving $X^TX = Y^TY = I_r$. Note also that $\|X_i - Y_i\|_2 = \|u\|_2 = \sqrt{\frac{2}{r}}$ for each $i$, so we can set $\varepsilon = \sqrt{\frac{2}{r}}$. However, for each $i$ we have $X_i^T e_{r+1} = 0$ and $Y_i^T e_{r+1} = \frac{1}{\sqrt{r}}$, hence $XX^T e_{r+1} = \sum_{i=1}^r X_i X_i^T e_{r+1} = 0$, while $YY^T e_{r+1} = \sum_{i=1}^r Y_i Y_i^T e_{r+1} = \frac{1}{\sqrt{r}} \sum_{i=1}^r Y_i = e_{r+1}$, so $(XX^T - YY^T)e_{r+1} = -e_{r+1}$, which means $\|XX^T - YY^T\|_2 \geq 1 = \varepsilon \sqrt{\frac{r}{2}}$. Since we can take $r \to \infty$, there is no $c$ such that $\|XX^T - YY^T\|_2 \leq c\varepsilon$ always holds.
