
× This section is under development!

# Perturbation bounds

Symmetric $\Sigma, \widehat{\Sigma} \in \mathbb{R}^{p\times p}$ w/ descending $\{\lambda\}_{i=1}^p$, $\{\widehat{\lambda}\}_{i=1}^p$ and $\{\mathrm{v}\}_{i=1}^p$, $\{\widehat{\mathrm{v}}\}_{i=1}^p$:

### Davis-Kahan Thm (1970):

$\norm{\widehat{\mathrm{v}}_i - \mathrm{v}_i} \le \dfrac{\sqrt{2}\norm{\widehat{\Sigma} - \Sigma}}{\min\{|\widehat{\lambda}_{i-1} - \lambda_i|,|\lambda_i - \widehat{\lambda}_{i+1}|\}},$

### Weyl’s Thm:

$|\widehat{\lambda}_i - \lambda_i| \le \norm{\widehat{\Sigma} - \Sigma}, \quad \forall i=1,\ldots,p.$

### Dual Weyl

Symmetric $A, B \in \mathbb{R}^{p\times p}$, then $\forall j = 1, . . . , p$,

$\begin{Bmatrix} \lambda_j(A) & + & \lambda_p(B)\\ \lambda_{j+1}(A) & + & \lambda_{p-1}(B) \\ & \vdots & \\ \lambda_p(A) & + & \lambda_j(B) \end{Bmatrix} \le \lambda_j(A+B) \le \begin{Bmatrix} \lambda_j(A) & + & \lambda_1(B)\\ \lambda_{j-1}(A) & + & \lambda_2(B) \\ & \vdots & \\ \lambda_1(A) & + & \lambda_j(B) \end{Bmatrix}.$

(From TAO 254A Note 3a) Weyl:

$\lambda_{i+j-1}(A+B) \le \lambda_{i}(A) + \lambda_{j}(B), \quad i,j\ge 1, \; i+j-1\le n.$

### Ky Fan inequality

$\lambda_{1}(A+B) + \cdots + \lambda_{k}(A+B) \le \lambda_{1}(A) + \cdots +\lambda_{k}(A) + \lambda_{1}(B) + \cdots +\lambda_{k}(B)$

### Eigenvalue stability inequality

$\abs{\lambda_{i}(A+B) -\lambda_{i}(A)}\le \norm{B}_{op}$

that is, the spectrum of $A+B$ is close to that of $A$ if $\norm{B}_{op}$ is small.

### Lindskii inequality

$\lambda_{i_1}(A+B) + \cdots + \lambda_{i_k}(A+B) \le \lambda_{i_1}(A) + \cdots +\lambda_{i_k}(A) + \lambda_{1}(B) + \cdots +\lambda_{k}(B),$

for all $1\le i_1 \le \cdots i_k \le n.$

### Dual Lindskii inequality

$\lambda_{i_1}(A+B) + \cdots + \lambda_{i_k}(A+B) \ge \lambda_{i_1}(A) + \cdots +\lambda_{i_k}(A) + \lambda_{n-k+1}(B) + \cdots +\lambda_{n}(B),$

for all $1\le i_1 \le \cdots i_k \le n.$

### Dual Weyl inequality

$\lambda_{i+j-n}(A+B) \ge \lambda_{i}(A) + \lambda_{j}(B), \quad 1\le i, j, i+j-n \le n.$

### Cauchy’s Eigenvalue Interlacing

$A \in \mathbb{R}^{n\times n}$ is symmetric, $B \in \mathbb{R}^{m\times m},\; m< n$ is a principal submatrix of $A$ (or a projection of $A$ onto $m$ coordinates). Then, their eigenvalues are interlaced,

$\lambda_{i}(A) \ge \lambda_i(B) \ge \lambda_{i+n-m}(A), \quad i=1,\ldots,m.$

E.g. if $m=n-1$

$\lambda_{1}(A) \ge \lambda_1(B) \ge \ldots \ge \lambda_{n-1}(B) \ge \lambda_{n}(A).$

### Weilandt-Hoffmann inequality:

$\sum_{i=1}^n \abs{\lambda_i(A+B) -\lambda_i(A)}^2 \le \norm{B}_F^2$

### Curvature lemma

$(\lambda_d - \lambda_{d+1}) \norm{\widehat{\Pi}_d - \Pi_d}_F^2 \le 2 \mathrm{Tr}(\Sigma(\Pi_d - \widehat{\Pi}_d))$

### ~Random fact

For matrix $\mathrm{M}\in\mathbb{R}^{n\times p}$ and a unit vector $\mathrm{u}\in\mathbb{R}^{p}$:

$\lambda_1(\mathrm{M'M}) \ge \norm{\mathrm{Mu}}_2^2 \ge \lambda_p(\mathrm{M'M})$