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$.

  • $\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$ – Omnomnomnom Dec 27 '14 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$ – Omnomnomnom Dec 27 '14 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 '14 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$ – Omnomnomnom Dec 28 '14 at 3:05
  • $\begingroup$ Ok, thank you! I have posted it. $\endgroup$ – Shine Dec 30 '14 at 15:50

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.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.