Let $A$ and $B$ be an $N\times n$ matrix with $n\le N$, and let $\sigma_1(X),\dots \sigma_n(X)$ denote the singular values of $X\in \{A,B\}$. Do we have upper and lower bounds for $$ \| \sigma_i(A)-\sigma_i(B) \| $$ as a function of $\|A-B\|$ (for some matrix norm $\|\cdot\|$)?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ No. $A=\begin{pmatrix} 3 \\ 4 \end{pmatrix}$ and $B=\begin{pmatrix} 5 \\ 0 \end{pmatrix}$ have the same singular value, but $\|A-B\|\not= 0$. $\endgroup$– Christian RemlingCommented Feb 9 at 15:44
-
$\begingroup$ Are there reasonable conditions on the involved matrices for which such bounds would be possible? $\endgroup$– ABIMCommented Feb 9 at 16:38
-
1$\begingroup$ The singular values of $A$ are the eigenvalues of $A^*A$. Findung a bound on those eigenvalues will probably be easier. $\endgroup$– Martin CleverCommented Feb 9 at 18:00
-
$\begingroup$ @ABIM Upper bounds in terms of $\|A - B\|$ can be obtained, but as Christian's comment demonstrates lower bounds don't typically apply. One situation where a lower bound could be obtained is if it is known a priori that the highest singular value of $A$ is smaller than the smallest singular value of $B$ (or vice versa). $\endgroup$– Ben GrossmannCommented Feb 13 at 17:34
-
2$\begingroup$ The singular values can also be obtained as the non-negative eigenvalues of the matrix $$ \pmatrix{0 & A\\A^* & 0}. $$ Often, this matrix is more convenient to use than $A^*A$ or $AA^*$. $\endgroup$– Ben GrossmannCommented Feb 13 at 17:35
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Weyl's inequalities for singular values give you the desired upper bound and, in some cases, a lower bound.
For the upper bound, we have $$ |\sigma_i(A) - \sigma_i(B)| \leq \sigma_1(B - A) = \|B - A\|, $$ where $\|\cdot\|$ denotes the spectral norm. This can easily be extended to other unitarily invariant norms.
For the lower bound, one situation where a lower bound is guaranteed is where $\sigma_1(A) \leq \sigma_n(B)$. In this case, we note using the variational characterization of singular values that $$ \sigma_1(A) = \max_{\|x\| = 1}\|Ax\| \leq \min_{\|x\| = 1}\|Bx\| = \sigma_n(B) $$ and that $$ \begin{align} \|B - A\| &= \sigma_1(B-A) = \max_{\|x\| = 1}(B - A)x \\ & \geq \max_{\|x\| = 1} (\|Bx\| - \|Ax\|) \\ & \geq \min_{\|x\| = 1}\|Bx\| - \max_{\|x\| = 1}\|Ax\| = \sigma_n(B) - \sigma_1(A), \end{align} $$ so that $\sigma_n(B) - \sigma_1(A) \geq \|B - A\|$. From there, it follows that for all $i$ $\sigma_n(B) \leq \sigma_i(B)$ and $\sigma_1(A) \geq \sigma_i(A)$, so that $$ \sigma_i(B) - \sigma_i(A) \geq \sigma_n(B) - \sigma_1(A) \geq \|B - A\|. $$
I suspect that this can be extended to other unitarily invariant norms without too much trouble.
