NLA MT25, Weyl's inequality
Flashcards
@State Weyl’s inequality.
Suppose:
- $A$ is a matrix
- $E$ is another matrix (a perturbation)
Then for all $i$, $ \vert \sigma _ i(A + E) - \sigma _ i(A) \vert \le \|E\| _ 2$. As other cases,
- $ \vert \vert A \vert \vert _ 2 - \vert \vert E \vert \vert _ 2 \le \vert \vert A + E \vert \vert _ 2 \le \vert \vert A \vert \vert _ 2 + \vert \vert E \vert \vert _ 2$,
- For the eigenvalues of a symmetric matrix $A$, for all $i$, $ \vert \lambda _ i (A + E) - \lambda _ i (A) \vert \le \|E\| _ 2$.
@Prove ∆weyls-inequality, i.e. that if
- $A$ is a matrix
- $E$ is another matrix (a perturbation)
Then for all $i$, $ \vert \sigma _ i(A + E) - \sigma _ i(A) \vert \le \|E\| _ 2$. As other cases,
- $ \vert \vert A \vert \vert _ 2 - \vert \vert E \vert \vert _ 2 \le \vert \vert A + E \vert \vert _ 2 \le \vert \vert A \vert \vert _ 2 + \vert \vert E \vert \vert _ 2$
- For the eigenvalues of a symmetric matrix $A$, for all $i$, $\lambda _ i (A + E) \in \lambda _ i (A) + [- \vert \vert E \vert \vert _ 2, \vert \vert E \vert \vert _ 2]$
We apply ∆courant-fischer-minmax-theorem to $A + E$. For every fixed subspace $\mathcal S$ with $\dim \mathcal S = i$ and every $x \in \mathcal S \setminus \{0\}$, the reverse triangle inequality gives the bound
\[\frac{\|(A + E)x\| _ 2}{\|x\| _ 2} \le \frac{\|Ax\| _ 2}{\|x\| _ 2} + \frac{\|Ex\| _ 2}{\|x\| _ 2} \le \frac{\|Ax\| _ 2}{\|x\| _ 2} + \|E\| _ 2\]Then, taking $\min _ {x \in \mathcal S}$ on both sides,
\[\min _ {x \in \mathcal S \setminus \{0\}} \frac{\|(A + E)x\| _ 2}{\|x\| _ 2} \le \min _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2}{\|x\| _ 2} + \|E\| _ 2\]This holds for every $\mathcal S$, so we may take $\max _ {\dim \mathcal S = i}$ on both sides to yield
\[\begin{aligned} \sigma _ i(A + E) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{\|(A + E)x\| _ 2}{\|x\| _ 2} \\ &\le \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2}{\|x\| _ 2} + \|E\| _ 2 \\ &= \sigma _ i(A) + \|E\| _ 2. \end{aligned}\]Swapping the roles of $A$ and $A + E$, we have the matching lower bound
\[\sigma _ i(A + E) \ge \sigma _ i(A) - \|E\| _ 2,\]so
\[ \vert \sigma _ i(A + E) - \sigma _ i(A) \vert \le \|E\| _ 2\]For the first special case, take $i = 1$. Then $\sigma _ 1(M) = \|M\| _ 2$, so
\[\big \vert \|A + E\| _ 2 - \|A\| _ 2\big \vert \le \|E\| _ 2\]which rearranges to
\[\|A\| _ 2 - \|E\| _ 2 \le \|A + E\| _ 2 \le \|A\| _ 2 + \|E\| _ 2.\]For the second special case, we replace the singular value Courant-Fischer bound with the eigenvalue one, to yield
\[\frac{x^\top (A + E) x}{x^\top x} \le \frac{x^\top A x}{x^\top x} + \frac{ \vert x^\top E x \vert }{x^\top x} \le \frac{x^\top A x}{x^\top x} + \|E\| _ 2\]and then follow the rest of the proof.
Bite-sized
What does Weyl’s inequality tell us about conditioning?
Singular values of any matrix and eigenvalues of symmetric matrices are well-conditioned under perturbations: a perturbation of size $\|E\| _ 2$ moves each $\sigma _ i$ or symmetric $\lambda _ i$ by at most $\|E\| _ 2$ — additive, not multiplicative. So a backward-stable algorithm can compute these quantities to essentially working precision $O(u)$, with no $\kappa$-amplification.
Weyl’s inequality follows directly from the Courant-Fischer minimax characterisation combined with the reverse triangle inequality $\ \vert (A+E)x\ \vert _ 2 \le \ \vert Ax\ \vert _ 2 + \ \vert Ex\ \vert _ 2$, applied inside the min-over-subspace.
Contrast Weyl’s bound (additive in $\ \vert E\ \vert _ 2$ for symmetric eigenvalues and singular values) with what happens for non-symmetric eigenvalues: the latter can be sensitive by a factor of $\epsilon^{1/n}$ for the worst Jordan-block case, demonstrating that non-symmetric eigenvalues are not well-conditioned in general.