7
$\begingroup$

Let $A_p$ and $B_p$ be a sequence of symmetric positive-definite $p\times p$ matrices such that $$\|A_p - B_p\|_2 \le 1/p.$$ Suppose further that the spectra of $A_p$ and $B_p$, for all $p$, is contained in a compact interval in $(0,\infty)$. And finally suppose that for all $p$, $\operatorname{tr}(B_p) = p.$

Intuitively, it seems that it should follow from this that $$\|pA_p/\operatorname{tr}(A_p) - B_p\|_2 \le const./p.$$

Does this in fact hold?

$\endgroup$
  • $\begingroup$ I think in this case you have that all eigenvalues of $A_p$ are within $1/p$ of those of $B_p$, but I'm not entirely certain because they will typically not be simultaneously diagonalizable. Given that it is easy, since $pA_p/tr(A_p)$ will be equal to $A_p+O(1/p^2)$. I'm just not sure how to get that. $\endgroup$ – Ian Dec 29 '16 at 21:02
  • 1
    $\begingroup$ I managed to solve it. The trick is to use your observation, Ian, and note that in general we have by the Weyl inequalities $\lambda_k(A)\le \lambda_k(B)+\|A-B\|_2$. $\endgroup$ – Lepidopterist Jan 2 '17 at 21:55
4
+100
$\begingroup$

Yes, it does, and you don't need Weyl's inequality. Note that $$ |\operatorname{tr}(A_p-B_p)|\le\sum_i|\lambda_i(A_p-B_p)|\le p\|A_p-B_p\|_2\le1. $$ Therefore $\operatorname{tr}(A_p)= p+\operatorname{tr}(A_p-B_p) \in [p-1,p+1]$ and $$ \frac{-1}{p+1}=\frac{p}{p+1}-1\le\frac{p}{\operatorname{tr}(A_p)}-1\le\frac{p}{p-1}-1=\frac{1}{p-1}. $$ In turn, $\left|\frac{p}{\operatorname{tr}(A_p)}-1\right|=O(\frac1p)$. Since we have assumed that the spectrum of $B_p$ is confined inside a compact interval, we also have $\|B_p\|_2=O(1)$. Thus \begin{align*} \left\|\frac{p}{\operatorname{tr}(A_p)}A_p-B_p\right\|_2 &\le\frac{p}{\operatorname{tr}(A_p)}\|A_p-B_p\|_2 + \left|\frac{p}{\operatorname{tr}(A_p)}-1\right| \|B_p\|_2\\ &=O(1)O(\frac1p) + O(\frac1p)O(1) = O(\frac1p). \end{align*}

$\endgroup$
  • $\begingroup$ Doesn't this equivalence of norms only hold for finite $p$? Does the big-oh constant in the second last equality not depend on $p$? $\endgroup$ – Lepidopterist Jan 2 '17 at 2:59
  • $\begingroup$ I think the misunderstanding is that I didn't specify that p is the dimensionality of the matrices. $\endgroup$ – Lepidopterist Jan 2 '17 at 3:14
1
$\begingroup$

To make a very slight generalisation: I'll prove this for Hermitian, positive-semidefinite matrices.


Preliminaries:

From the inequality you give, and the fact that the spectra are contained in some compact interval $[\lambda_{min},\lambda_{max}]$, we can state:

$A_p$ and $B_p$ are positive-semidefinite Hermitian matrices, where $A_p$ has eigenvalues $\alpha_i$: $$\lambda_{max} \geq \alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_p \geq \lambda_{min} \geq 0,$$ and $B_p$ has eigenvalues $\beta_i$: $$\lambda_{max} \geq \beta_1 \geq \beta_2 \geq \cdots \geq \beta_p\geq \lambda_{min} \geq 0,$$ then by the Weyl matrix inequalities: $\forall i = 1,\dots,p$: $$|\alpha_i - \beta_i| \leq \|A_p-B_p\|_2 \leq 1/p.$$

Let us also note that the spectral norm $\|A_p\|_2$ of $A_p$ satisfies: $$\|A_p\|_2 = \max_{i = 1,\,\dots\,,\,p}|\alpha_i| = \alpha_1 \leq \lambda_{max}.$$

Finally, note that for $p \geq 2$ we have that $$\frac{1}{p-1} \leq \frac{2}{p}.$$


Claim:

For all $p = 1, 2, \dots$ , we have that $$ \left\|\frac{p}{\operatorname{tr}(A_p)}A_p-B_p\right\|_2 \leq \frac{1+2\lambda_{max}}{p} $$

First of all, note that for $p=1$ the proof is quite trivial: $$\frac{p}{\operatorname{tr}(A_p)}A_p = \frac{A_p}{A_p} = 1$$ and $$B_p = \operatorname{tr}(B_p) = p = 1,$$ hence $$ \left\|\frac{p}{\operatorname{tr}(A_p)}A_p-B_p\right\|_2 = \| 1 - 1 \|_2 = 0 \leq 1+2\lambda_{max}. $$

We will assume $p \geq 2$ from now on. Since $\operatorname{tr}(B_p) = p$ and $|\alpha_i - \beta_i| < 1/p$, we have that $$|\operatorname{tr}(A_p)-\operatorname{tr}(B_p)| = \left|\sum_{i=1}^p \alpha_i - \sum_{i=1}^p\beta_i\right|=\left|\sum_{i=1}^p (\alpha_i - \beta_i)\right| \leq \sum_{i=1}^p |\alpha_i - \beta_i| \leq \sum_{i=1}^p \frac{1}{p} = 1.$$ Define $\varepsilon = \operatorname{tr}(A_p) - \operatorname{tr}(B_p) \in [-1,1]$, such that $\operatorname{tr}(A_p) = \operatorname{tr}(B_p) + \varepsilon = p+\varepsilon > 0$.

Using our preliminaries, we get: \begin{align} \left\|\frac{p}{\operatorname{tr}(A_p)}A_p-B_p\right\|_2 &=\left\|\frac{p}{p+\varepsilon}A_p-B_p\right\|_2 \\ &=\left\|\frac{p + \varepsilon-\varepsilon}{p+\varepsilon}A_p-B_p\right\|_2 \\ &=\left\|A_p - B_p - \frac{\varepsilon}{p+\varepsilon}A_p\right\|_2 \\ &\leq \left\|A_p - B_p\right\|_2 + \left\|\frac{\varepsilon}{p+\varepsilon}A_p\right\|_2 \\ &\leq \frac{1}{p} + \frac{|\varepsilon|}{p+\varepsilon}\left\|A_p\right\|_2 \\ &\leq \frac{1}{p} + \frac{1}{p-1}\lambda_{max} \\ &\leq \frac{1}{p} + \frac{2}{p}\lambda_{max} \\ &= \frac{1+2\lambda_{max}}{p}. \end{align}

$\endgroup$

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.