Bound on difference of eigen projections of positive definite matrices

Question

Suppose I have two positive semidefinite matrices (and their eigendecompositions) $A = U \Lambda_A U'$ and $B = V \Lambda_B V'$. I was wondering if $$ ||U_jU_j' - V_jV_j' || \leq C || A - B || $$ for some $C$. Here, $U_j$ is the $j$th column of $U$. Hence, I'm asking if the eigenprojections are Lipschitz continuous with respect to the original matrices. I've went through Kato's praised book on perturbation theory, which is great by the way, but the theory there is mostly about when the matrices depend on a single parameter. Any help would be greatly appreciated.

Answer 1

This is in fact related to the perturbation theory for sub-eigenspace.

Intuition: Suppose $\lambda_j(A)$ is the $j$-th largest eigenvalues of $A$. If $\lambda_j(A)$ is in the range $(\lambda_{j+1}(B), \lambda_{j-1}(B))$, then there is a hope to obtain such an upper bound. Otherwise, the eigenvector associated with $\lambda_j(A)$ in $A$ can have no relation with the eigenvector associated with $\lambda_{j}(B)$ in $B$.

Results: Suppose $\lambda_{j+1}(B)\leq \lambda_j(A) \leq \lambda_{j-1}(B)$, we have $$ \|U_jU_j' - V_jV_j'\|_2 \leq \frac{\sqrt{2}\|B-A\|_2}{\min(\lambda_{j}(A)-\lambda_{j+1}(B), \lambda_{j-1}(B) - \lambda_j(A))}. $$

Before showing the proof, let us introduce the following famous Davis-Kahan theorem:

Theorem: (Davis-Kahan sin(Θ) theorem) Let $A = E_0A_0E_0'+E_1A_1E_1'$ be the two complementary parts of the eigen-decomposition of $A$. In particular, $E_0 \in R^{n\times r}, E_1 \in R^{n\times (n-r)}, A_0 \in R^{r\times r}, A_1 \in R^{(n-r)\times (n-r)}$ where $E_0'E_0 = I_r, E_1'E_1 = I_{n-r}, E_0'E_1 = 0$ and $A_0, A_1$ are diagonal. Similarly, let $B = F_0B_0F_0' + F_1B_1F_1'$ be the two complementary parts of eigen-decomposition of $B$. If the eigenvalues of $A_0$ are contained in an interval $(a, b)$, and the eigenvalues of $B_1$ are excluded from the interval $(a−\delta, b+\delta)$ for some $\delta > 0$, then $$ \|F_1'E_0\| \leq \frac{\|F_1'(B-A)E_0\|}{\delta} $$ for any unitarily invariant norm $\|\cdot\|$.

Corollary: Apply the above theorem to Frobenious norm, we have $$ \|F_1'E_0\|_{F} \leq \frac{\|F_1'(B-A)E_0\|_{F}}{\delta} \leq \frac{\|F_1'\|_{2} \|B-A\|_{2} \|E_0\|_{F}}{\delta} \leq \frac{\|B-A\|_2 \|E_0\|_2 \sqrt{r}}{\delta} \leq \frac{\sqrt{r} \|B-A\|_2}{\delta} $$ where $|A|_2$ is the spectral norm and $|A|_{F}$ is the Frobenious norm, and we use the fact that $|E_0|_2 \leq 1, |F_1|_2 \leq 1$ and $|AB|_{F} \leq |A|_2 |B|_F, |A|_{F} \leq \sqrt{min(n,m)}|A|_{2}$ if $A \in n\times m.$ On the other hand, suppose $F_0 \in R^{n\times r}$. Notice that \begin{align} \|E_0E_0' - F_0 F_0'\|_{F}^2 &= tr(E_0E_0'E_0E_0' + F_0F_0'F_0F_0') - 2 tr(E_0E_0'F_0F_0')\\ &= tr(E_0E_0') + tr(F_0 F_0') - 2tr(E_0E_0'F_0F_0')\\ &= 2r - 2tr(E_0E_0'F_0F_0')\\ &= 2tr(E_0E_0') - 2tr(E_0E_0'F_0F_0')\\ &= 2tr(E_0E_0'(I - F_0F_0'))\\ &= 2tr(E_0E_0'F_1F_1')\\ &= 2\|F_1'E_0\|_{F}^2. \end{align} Therefore, $$ \|E_0E_0' - F_0F_0'\|_{F} \leq \frac{\sqrt{2r}\|B-A\|_2}{\delta}. $$ This provides an upper bound for the subspace distance between $E_0E_0'$ and $F_0F_0'$ based on the perturbation $\|B-A\|_2.$

Application: Now we apply this theorem (corollary) to your problem. Here $E_0 = U_j, E_1 = U_{-j}$ where $U_{-j}$ removes the $j$-th column from $U$ and $A_0 = \lambda_{j}(A)$, $A_1$ is the diagonal matrix consists of eigenvalues $\lambda_1(A), \dotsc, \lambda_{j-1}(A), \lambda_{j+1}(A), \dotsc, \lambda_{n}(A)$ where we assume $\lambda_1(A) \geq \lambda_2(A) \geq \dotsc \geq \lambda_n(A).$ Similarly, $F_0 = V_j, F_1 = V_{-j}$ and $B_1$ consists of eigenvalues $\lambda_1(B), \dotsc, \lambda_{j-1}(B), \lambda_{j+1}(B), \dotsc, \lambda_n(B).$ Therefore, $r = 1$ in your problem.

In a typical case, we shall assume $\lambda_{j+1}(B) \leq \lambda_j(A) \leq \lambda_{j-1}(B)$ otherwise there is no hope to have some continuity from the eigenvector $U_j$ to $V_j$.

Then this corollary implies that $$ \|U_jU_j' - V_jV_j'\|_{F} \leq \frac{\sqrt{2}\|B-A\|_2}{\delta} $$ where $\delta = \min(\lambda_{j}(A)-\lambda_{j+1}(B), \lambda_{j-1}(B) - \lambda_j(A)).$ Note that $$ \frac{1}{\sqrt{2}}\|U_jU_j' - V_jV_j'\|_{F} \leq \|U_jU_j' - V_jV_j'\|_2 \leq \|U_jU_j' - V_jV_j'\|_{F} $$ since $U_jU_j'-V_jV_j'$ is at most rank 2. This provides (almost tight) bound for your question: $$ \|U_jU_j' - V_jV_j'\|_2 \leq \frac{\sqrt{2}\|B-A\|_2}{\min(\lambda_{j}(A)-\lambda_{j+1}(B), \lambda_{j-1}(B) - \lambda_j(A))}. $$

See further references on the proof of Davis-Kahan theorem (the proof is in fact very neat. Highly recommend this!) and the user-friendly variant of Davis-Kahan theorem.