# Eigen-decomposition perturbation

Let $A$, $B$ and $A_k + B$ be symmetric matrices with eigenvalues $\sigma_1 \geq \sigma_2 \ldots \geq \sigma_n$, $\rho_1 \geq \rho_2 \ldots \geq \rho_n$ and $\lambda_1 \geq \lambda_2 \ldots \geq \lambda_n$ respectively. Here $A$ is positive semidefinite, and the notation $A_k$ is the approximation of $A$ using the largest $k$ eigenvectors and eigenvalues, i.e. $A_k = \sum_{i=1}^k \sigma_i v_iv_i^T$ where $v_i$ is the eigenvector corresponding to $\sigma_i$. Given that $rank(A) \gg rank(B)$ is it possible to obtain a tight upper bound on $\|(A + B)_k - (A_k + B)\|_F^2$, where $\| \cdot \|_F$ is the Frobenius norm, knowing only the above (i.e. eigen-decompositions of $A$, $B$ and $A_k + B$ but not of $A + B$)?

So far, I managed to expand out the norm as follows: $\sum_{i=1}^k\gamma_i^2 + \sum_{i=1}^n \lambda_i^2 - 2 tr((A + B)_k(A_k + B))$ where $\gamma_s = \min_{i+j=s+1}(\sigma_i + \rho_j)$, $s=1, \ldots, n$ comes from the Weyl inequalities (https://terrytao.wordpress.com/2010/01/12/254a-notes-3a-eigenvalues-and-sums-of-hermitian-matrices/). I am not sure if I can lower bound the trace term in terms of the eigenvalues however. Is it possible to lower bound this trace knowing only the eigen-decompositions of $A$, $B$ and $A_k + B$ (not $A + B$)?

Any help is greatly appreciated.

-
I guess you meant $A_k=\sum_{i=1}^{k}\sigma_i v_i v_i^T$! –  Mercy Jun 14 '12 at 14:52
Yes, I did - thanks, and corrected. –  cdhanjal Jun 14 '12 at 15:32