spectral norm of 2 matrices compared to spectral norm of the difference matrix

Question

In one paper I read, there is a notion that for matrix A and B of the same size (B is the sparsified version of A through random sparsification), the difference between the spectral norm is no greater than the spectral norm of the diff matrix, i.e : $| ||A|| - ||B|| | \leq || A - B ||$ where $||A|| = \sqrt{\lambda_{max}}$ (spectral norm). Can anyone help to explain this inequality ? any help is greatly appreciated. Thank you.

Answer 1

It's just a consequence of the triangle inequality, which is true for every norm.

$$ \|A\| = \|B + (A-B)\| \le \|B\| + \|A-B\|$$ so $$ \|A\| - \|B\| \le \|A-B\|$$ and interchanging $A$ and $B$, $$\|B\| - \|A\| \le \|B - A\| = \|A - B\|$$ so $$ \left| \|A\| - \|B\| \right| = \max(\|A\|-\|B\|, \|B\|-\|A\|)\le \|A - B \|$$

Answer 2

Well, this is true for any norm. By the triangle inequality, $\|x+y\|\leqslant\|x\|+\|y\|$ for and $x,y$ in a normed space. Substituting $x=A-B$ and $y=B$, we'll get $$\|A-B+B\|\leqslant\|A-B\|+\|B\| \implies \|A\|\leqslant\|A-B\|+\|B\| \implies \|A\|-\|B\|\leqslant\|A-B\|.$$

Similarly, by switching $A$ and $B$ with each other, we can prove that $\|B\|-\|A\|\leqslant\|A-B\|$.

Combined together, these two inequalities show that $\left|\|A\|-\|B\|\right|\leqslant\|A-B\|$.