Singular values under perturbation

Proposition. (weak version of Weyl’s Inequality)

For two square $n\times n$ matrices $A,B$, the following inequality is true:

$$|{\sigma }_{\text{max}}(A+B)-{\sigma }_{max}(A)|\le {\sigma }_{max}(B).$$

Similarly,

$$|{\sigma }_{\min }(A+B)-{\sigma }_{\min }(A)|\le {\sigma }_{max}(B).$$

Proof.

Recall the well-known fact about spectral norm:

$$||A|{|}_2=\underset{||x||=1}{\max }||Ax|{|}_2={\sigma }_{\text{max}}(A).$$

Then, using the fact that spectral norm is a well-defined norm, we can simply leverage the triangle inequality:

$$\begin{array}{r}{\sigma }_{\max }(A+B)=||A+B|{|}_2\le ||A|{|}_2+||B|{|}_2={\sigma }_{\max }(A)+{\sigma }_{\max }(B).\end{array}$$

Let’s define some new matrices: $C\equiv A+B$, $D\equiv -B$ such that $C+D=A$. Plugging these new matrices into our inequality (1),

$$\begin{array}{rl}{\sigma }_{\max }(C+D)& \le {\sigma }_{\max }(C)+{\sigma }_{\max }(D)\\ ⟹{\sigma }_{\max }(A)& \le {\sigma }_{\max }(A+B)+{\sigma }_{\max }(-B)\\ ⟹-{\sigma }_{\max }(-B)& \le {\sigma }_{\max }(A+B)-{\sigma }_{max}(A).\end{array}$$

Then, we need only realize that $-{\sigma }_{\max }(-B)=-||-B|{|}_2=-||B|{|}_2=-{\sigma }_{\max }(B)$, which implies that

$$\begin{array}{r}-{\sigma }_{\max }(B)\le {\sigma }_{\max }(A+B)-{\sigma }_{max}(A).\end{array}$$

Putting inequalities (1) and (2) together, we get that

$$|{\sigma }_{\max }(A+B)-{\sigma }_{max}(A)|\le {\sigma }_{\max }(B).$$

The $\min$ case is similar, but we unfortunately can’t use the triangle inequality directly as ${\min }_{||x||=1}||Ax|{|}_2$ is not a norm. But, we can use the triangle inequality indirectly in the following way:

$$\underset{||x||=1}{\min }||(A+B)x|{|}_2\le \underset{||x||=1}{\min }(||Ax|{|}_2+||Bx|{|}_2).$$

This step is justified since $||(A+B)x|{|}_2\le ||Ax|{|}_2+||Bx|{|}_2$ for all $x$. Then,

$$\begin{array}{rl}\underset{||x||=1}{\min }(||Ax|{|}_2+||Bx|{|}_2)& \le \underset{||x||=1}{\min }||Ax|{|}_2+\underset{||x||=1}{\max }||Bx|{|}_2\\ ⟹{\sigma }_{\min }(A+B)& \le {\sigma }_{\min }(A)+{\sigma }_{\max }(B)\\ ⟹{\sigma }_{\min }(A+B)-{\sigma }_{\min }(A)& \le {\sigma }_{\max }(B).\end{array}$$

We can use some clever substitutions as we did earlier for the $\max$ case to show that $-{\sigma }_{\max }(B)$ is a lower bound for ${\sigma }_{\min }(A+B)-{\sigma }_{\min }(A)$. $■$

---

For Hermitian matrices $A$ and $B$, it is true that

$$|{\sigma }_k(A+B)-{\sigma }_k(A)|\le {\sigma }_{\max }(B),$$

for all $k$. This is Weyl’s Inequality.

A particularly interesting application of these inequalities is in matrix perturbation: if $B$ is some small perturbation matrix $\Delta$ (with small singular values), then the maximum and minimum singular values of $A+\Delta$ cannot deviate much from the singular values of the original matrix $A$. For Hermitian matrices, since the inequality applies for all the singular values, we know that the entire spectrum must stay stable under perturbation.

Resources: Terry Tao’s blog