3
$\begingroup$

If $A,B\in \mathbb{R}^{m\times n}$ with $m\geq n$, assume singular values of $A$ are $\sigma_1\ge \sigma_2\ge \cdots\sigma_n;$ the singular values of $A+B$ are $\hat{\sigma}_1\ge \hat{\sigma}_2\ge \cdots\hat{\sigma}_n$.

Show that $|\sigma_i-\hat{\sigma}_i|\leq ||B||_2$, where $||B||_2=\sqrt{\rho(B^TB)}$.

I only know that if $A,B$ are symmetric and $\sigma_i,\hat{\sigma}_i$ are defined as eigenvalues of $A$ and $A+B$, it can be done. Here I tried to compute the eigenvalue of $(A+B)^T(A+B)$ and $A^TA$, I don't know how to deal with the term $A^TB+B^TA$.

$\endgroup$
5
  • $\begingroup$ At a quick glance, I would think that the Courant-Fischer characterization of singular values gives the nicest approach to this problem. Also, note that $$ \|B\|_2^2 = \sum_{i=1}^n [\sigma_i(B)]^2 $$ If I find the time and attention span, I may leave an answer to this effect, assuming it really is possible. $\endgroup$
    – Ben Grossmann
    Dec 27, 2014 at 17:19
  • $\begingroup$ To clarify what I mean: we can say that $$ [\sigma_k(A)]^2 = \max_{\dim(S) = k} \min_{x \in S, \|x\| = 1} x^*A^*Ax =\\ \max_{\dim(S) = k} \min_{x \in S, \|x\| = 1} \|Ax\|^2 = \\ \max_{\dim(S) = k} \min_{x \in S\setminus \{0\}} \frac{\|Ax\|^2}{\|x\|^2} $$ $\endgroup$
    – Ben Grossmann
    Dec 27, 2014 at 17:26
  • $\begingroup$ Good, thank you a lot. I got what you mean, now I can work it out by Courant Fisher Theorem and notice $||B||_2=\max\{Bx: ||x||_2=1\}$. $\endgroup$
    – Shine
    Dec 28, 2014 at 2:17
  • $\begingroup$ Oh, my first comment was a mistake; that's $\rho$ not trace. So yes, $$ \|B\|_2 = \sigma_1(B) = \max_{\|x\|_2 = 1} \|Bx\| $$ I'm glad you're able to figure it out! If you do end up writing an answer, it may be helpful to future visitors if you post an answer to your own question outlining the approach you decide on. If you end up getting stuck, feel free to ping me. $\endgroup$
    – Ben Grossmann
    Dec 28, 2014 at 3:05
  • $\begingroup$ Ok, thank you! I have posted it. $\endgroup$
    – Shine
    Dec 30, 2014 at 15:50

1 Answer 1

Reset to default
2
$\begingroup$

By Courant Fisher Theorem: $$\sigma_i=\sqrt{\max_{\mathbb{R}^i}\min_{v\in\mathbb{R}^i} \frac{v^TA^TAv}{v^Tv}}=\max_{\mathbb{R}^i}\min_{v\in\mathbb{R}^i} \sqrt{\frac{||Av||_2^2}{||v||_2^2}}=\max_{\mathbb{R}^i}\min_{v\in\mathbb{R}^i}\frac{||Av||_2}{||v||_2} $$

$$\sigma_i=\sqrt{\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}} \frac{v^TA^TAv}{v^Tv}}=\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}}\sqrt{\frac{||Av||_2^2}{||v||_2^2}}=\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}}\frac{||Av||_2}{||v||_2} $$

$$\hat{\sigma}_i=\sqrt{\max_{\mathbb{R}^i}\min_{v\in\mathbb{R}^i} \frac{v^T(A+B)^T(A+B)v}{v^Tv}}=\max_{\mathbb{R}^i}\min_{v\in\mathbb{R}^i} \frac{||(A+B)v||_2}{||v||_2}$$

$$\hat{\sigma}_i=\sqrt{\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}} \frac{v^T(A+B)^T(A+B)v}{v^Tv}}=\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}} \frac{||(A+B)v||_2}{||v||_2}$$

Because $$\min_{v\in\mathbb{R}^i}\frac{||(A+B)v||_2}{||v||_2}\ge \min_{v\in\mathbb{R}^i}\frac{||Av||_2}{||v||_2} -\max_{v\in \mathbb{R}^i}\frac{||Bv||_2}{v^Tv}\ge\min_{v\in\mathbb{R}^i}\frac{||Av||_2}{||v||_2} -||B||_2$$

$$\max_{v\in\mathbb{R}^{n+1-i}}\frac{||(A+B)v||_2}{||v||_2}\leq \max_{v\in\mathbb{R}^{n+1-i}}\frac{||Av||_2}{||v||_2} +\max_{v\in\mathbb{R}^{n+1-i}}\frac{||Bv||_2}{v^Tv}\leq\max_{v\in\mathbb{R}^{n+1-i}}\frac{||Av||_2}{||v||_2} +||B||_2$$ So we get $$\hat{\sigma}_i=\max_{\mathbb{R}^{i}}\min_{v\in\mathbb{R}^i}\frac{||(A+B)v||_2}{||v||_2}\ge \max_{\mathbb{R}^{i}}\min_{v\in\mathbb{R}^i}\frac{||Av||_2}{||v||_2} -||B||_2=\sigma_i-||B||_2$$

$$\hat{\sigma}_i=\min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}}\frac{||(A+B)v||_2}{||v||_2}\leq \min_{\mathbb{R}^{n+1-i}}\max_{v\in\mathbb{R}^{n+1-i}}\frac{||Av||_2}{||v||_2} +||B||_2=\sigma_i+||B||_2$$

Then we conlude that $|\hat{\sigma}_i-\sigma_i|\leq ||B||_2,\quad i=1,2,\cdots,n.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .