Why don't small perturbations reduce rank

Question

Suppose $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_k$ are the nonzero singular values of a rank $k$ matrix $A$. How can I show that if $||E||_2 < \sigma_k$, then the rank($A + E$) is larger or equal than rank($A$)?

Answer 1

This can be proved with the variational characterization of singular values, i.e. if $M$ is an $m$-by-$n$ matrix of rank $q$ and $\mu_1(M) \ge \mu_2(M) \ge ... \ge \mu_q(M) > 0$ are the $q$ singular values of $M$, then

$$\mu_k(M) = \underset{w_1, ..., w_{k-1}\in \mathbb C^n}\min \underset{\substack{\|x\|=1,\\x\perp w_1, ..., w_{k-1}}}{\max} \|Mx\|,$$

for any $1\le k \le q$. Hence,

$$\mu_k(A+E) = \underset{w_1, ..., w_{k-1}\in \mathbb C^n}\min \underset{\substack{\|x\|=1,\\x\perp w_1, ..., w_{k-1}}}{\max} \|(A+E)x\|.$$

Since $\|(A+E)x\|\ge \|Ax\|-\|Ex\| \overset{(a)}\ge \|Ax\| - \|E\|_2,$ it follows that

$$\mu_k(A+E) \ge \underset{w_1, ..., w_{k-1}\in \mathbb C^n}\min \underset{\substack{\|x\|=1,\\x\perp w_1, ..., w_{k-1}}}{\max} \|Ax\| - \|E\|_2=\sigma_k -\|E\|_2>0,$$

where, suppose $E=U^*\Sigma V$ is an SVD of $E$, $(a)$ is due to $\|Ex\|^2=x^*E^*Ex=x^*V^*\Sigma^*\Sigma Vx=y^*\Sigma^*\Sigma y\le tr(\Sigma^*\Sigma)=tr(E^*E)=(\|E\|_2)^2$.

Therefore, $(A+E)$ has at least $k$ non-zero singular values, and hence $\mathrm{rank}(A+E) \ge k.$