Given a partial ordering of the form $(1-\epsilon) B \preceq A \preceq (1+ \epsilon) B$ (where $A \preceq B$ means that $B-A$ is positive semi definite) for symmetric psd matrices $A,B$, can I derive a bound for the operator norm of $||A-B||$ in terms of the norm of $B$? I was just using the fact that the largest eigenvalue is similar to the two norm and then I would obtain the bound $||A-B|| \leq \epsilon ||B||$. is there any stronger bound possible? Below I quickly describe how I achieve the bound. I hope this is correct: From the partial ordering we have $$B-A \preceq \epsilon\ A \leftrightarrow x^T(B-A)\ x \leq \epsilon\ x^TAx,$$ for all $x$, and this holds in particular for $x=s_{max}$ being the eigenvector corresponding to the largest eigenvalue of $\lambda_{max}(B-A)$. Hence we obtain (for orthonormal eigenvectors $s_i$, since $A,B$ symmetric) $$ \lambda_{max}(B-A) \leq \epsilon\ s_{max}^T A s_{max} = \epsilon \sum_i \lambda_i(A) s_{max}^T \hat s_i \hat s_i^T s_{max} \leq \epsilon\ \lambda_{max}(A) \sum_i s_{max}^T \hat s_i \hat s_i^T s_{max} .$$ Now since $\sum_i \hat s_i s_i^T = I$, $A,B$ symmetric, and since $s_{max}^T s_{max} = 1$ we have $$ \lambda_{max}(B-A) = ||B-A||_2 \leq \epsilon \lambda_{max}(A)\ \cdot 1 = \epsilon\ ||A||_2,$$ and the bound follows. Please correct me if I made a mistake there, in particular is there a way to improve this without using the assumption that the eigenvectors of $A$ form a complete basis?

  • $\begingroup$ If you take $A = (1-\epsilon)I$ and $B = I$ you have $\|A-B\| = \epsilon\|B\|$, so no stronger bound is possible, although i'd like to see in details how you get the inequality. $\endgroup$ – Gribouillis Dec 16 '17 at 16:52
  • $\begingroup$ Thanks, yes that makes sense. I hope my proof above is correct, but I added it to the description. Note that I deal with full rank, symmetric matrices above, since I guess otherwise this would not necessarily hold? $\endgroup$ – LeoW. Dec 17 '17 at 8:27
  • $\begingroup$ However I realize that this proof does not work if the eigenvectors don't form a basis, or is there a way to still do it? $\endgroup$ – LeoW. Dec 17 '17 at 9:13
  • $\begingroup$ It looks good, you are using that the spectral radius of a real symmetric matrix is equal to its norm. There is a small detail that worries me: the hypothesis $(B-A)\preceq \epsilon A$ does not imply that $B-A$ is psd, so its eigenvalue with maximum modulus could be negative, which would break the proof. Is there a solution to this issue? $\endgroup$ – Gribouillis Dec 17 '17 at 9:28
  • $\begingroup$ The eigenvectors do form a basis. There is an orthogonal matrix $Q$ and an diagonal matrix $\Lambda$ such that $A = Q \Lambda Q^\top$. The columns of $Q$ are the eigenvectors. $\endgroup$ – Gribouillis Dec 17 '17 at 9:34

The hypothesis $\left(1-{\epsilon}\right) B \preceq A \preceq \left(1+{\epsilon}\right) B$ implies that

$$B-A \preceq {\epsilon} B \qquad \ \text{and} \ \qquad A-B \preceq {\epsilon} B$$

The real symmetric matrices $B-A$ and $A-B$ have opposite eigenvalues, hence one of them has its largest eigenvalue equal to its spectral radius. Suppose without loss of generality that it is $B-A$. If ${s}_{\max }$ is a normed eigenvector of $B-A$ for the eigenvalue ${\rho} \left(B-A\right)$, one has

$${\rho} \left(B-A\right) = {s}_{\max }^{\top } \left(B-A\right) {s}_{\max } \leqslant {\epsilon} {s}_{\max }^{\top } B {s}_{\max } \leqslant \left|{\epsilon}\right| \left\|B\right\| {\left\|{s}_{\max }\right\|}^{2} = \left|{\epsilon}\right| \left\|B\right\|$$

For real symmetric matrices, the spectral radius is equal to the operator norm, hence

$$\left\|B-A\right\| \leqslant \left|{\epsilon}\right| \left\|B\right\|$$

This inequality is optimal, as the example $A = \left(1-{\epsilon}\right) I$ and $B = I$ shows, for ${\epsilon} > 0$.


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.