5.1: Additive Perturbation

Theorem 5.1

Suppose \(A \in C^{m \times n}\) has full column \(rank (= n)\). Then

\[\min _{\Delta \in \mathbb{C}^{m \times n}}\left\{\|\Delta\|_{2} \mid A+\Delta \text { has rank }<n\right\}=\sigma_{n}(A)\ \tag{5.1}\]

Proof

Suppose \(A + \Delta\) has rank \(< n\). Then there exists \(x \neq 0\) such that \(\|x\|_{2}=1\) and

\[(A+ \Delta)x=0\nonumber\]

Since \(\Delta x = -Ax\),

\[\begin{aligned}
\|\Delta x\|_{2} &=\|A x\|_{2} \\
& \geq \sigma_{n}(A)
\end{aligned} \ \tag{5.2}\]

From the properties of induced norms (see Section 3.1), we also know that

\[\|\Delta\|_{2}\|x\|_{2} \geq\|\Delta x\|_{2}\nonumber\]

Using Equation (24.3) and the fact that \(\|x\|_{2}=1\), we arrive at the following:

\[\begin{aligned}
\|\Delta\|_{2} &=\|\Delta x\|_{2} \\
& \geq \sigma_{n}(A)
\end{aligned} \ \tag{5.3}\]

To complete the proof, we must show that the lower bound from Equation (5.3) can be achieved. Thus, we must construct a \(\Delta\) so that \(A + \Delta\) has rank \(<n\) and \(\|\Delta\|_{2}=\sigma_{n}(A)\); such a \(\Delta\) will be a minimizing solution. For this, choose

\[\Delta=-\sigma_{n} u_{n} v_{n}^{\prime}\nonumber\]

where \(u_{n}\), \(v_{n}\) are the left and right singular vectors associated with the smallest singular value \(\sigma_{n}\) of \(A\). Notice that \(<n\) and \(\|\Delta\|_{2}=\sigma_{n}(A)\). This choice yields

\[\begin{aligned}
(A+\Delta) v_{n} &=\sigma_{n} u_{n}-\sigma_{n} u_{n} v_{n}^{*} v_{n} \\
&=\sigma_{n} u_{n}-\sigma_{n} u_{n} \\
&=0
\end{aligned}\nonumber\]

That is, \(A + \Delta\) has rank \(< n\). This completes the proof.