If $U^T U = I_k$, $V^T V = I_{d-k}$, and $U^T V \approx 0$, is $U U^T + V V^T \approx I_d$?

Question

Let $k$ and $d$ be integers with $1 \le k \le d-1$. Let $U \in \mathbb{R}^{d \times k}$ satisfy $U^T U = I_k$. Let $V, \in \mathbb{R}^{d \times (d-k)}$ satisfy $V^T V = I_{d-k}$.

A basic fact from linear algebra is that, if $U^T V = 0$, then $U U^T + V V^T = I_d$. In other words, $U$ represents a set of $k$ orthonormal vectors and $V$ represents a set of $d-k$ orthonormal vectors; if $U$ is orthogonal to $V$, then together they give $d$ orthonormal vectors, which form an orthonormal basis.

I'm looking for a quantitative version of this: Suppose $\| U^T V \| \le \varepsilon$ and $\| V^T U \| \le \varepsilon$. What can we say about $\| U U^T + V V^T - I_d \|$ in terms of $\varepsilon$?

For concreteness, let $\|\cdot\|$ be the operator norm: For $M \in \mathbb{R}^{a \times b}$, $\|M\| := \sup \{ \|Mx\|_2 : x \in \mathbb{R}^b, \|x\|_2 \le 1 \}$. However, I am interested in other norms too.

Answer 1

We note two facts:

1. For any $A \in \mathbb{R}^{m \times n}$, the matrices $AA^T-I_m$ and $A^TA-I_n$ are both symmetric and have the same non-zero eigenvalues. Thus, $\|AA^T-I_m\| - \|A^TA-I_n\|$.
2. For any $B \in \mathbb{R}^{m \times n}$, the non-zero eigenvalues of the symmetric matrix $\begin{bmatrix}0 & B \\ B^T & 0\end{bmatrix}$ are $\pm\sigma_1,\ldots,\pm\sigma_{\min(m,n)}$ where $\sigma_1,\ldots,\sigma_{\min(m,n)}$ are the singular values of $B$. Therefore, $\left\|\begin{bmatrix}0 & B \\ B^T & 0\end{bmatrix}\right\| = \|B\|$.

Using these facts, we have \begin{align*} \|UU^T+VV^T-I_d\| &= \left\|\begin{bmatrix}U & V\end{bmatrix}\begin{bmatrix}U^T \\ V^T\end{bmatrix}-I_d\right\| \\ &= \left\|\begin{bmatrix}U^T \\ V^T\end{bmatrix}\begin{bmatrix}U & V\end{bmatrix}-I_d\right\| \\ &= \left\|\begin{bmatrix}U^TU & U^TV \\ V^TU & V^TV\end{bmatrix}-\begin{bmatrix}I_k & 0_{k,d-k} \\ 0_{d-k,k} & I_{d-k}\end{bmatrix}\right\| \\ &= \left\|\begin{bmatrix}0 & U^TV \\ V^TU & 0\end{bmatrix}\right\| \\ &= \|U^TV\| \\ &\le \epsilon. \end{align*}