I'm trying to upper bound the $\epsilon$-packing number of $\Theta=\{A\in\mathbb{S}^{d}:\; a\preceq A \preceq b\}$ (where $\mathbb{S}$ are symmetric $d\times d$ matrices) for some $a\leq b$ with respect to the spectral (operator) norm (actually I also have $a>0$, but I don't think that affects the answer).

One approach is with a volume argument, which goes something like this. Given any optimal $\epsilon$-packing $A_1,...,A_P$, defining $$S_i=\{A_i+B:\; B\in\mathbb{S}^d,\;\|B\|_2\leq\epsilon/2\}$$ and $$\Theta'=\{A+B:\;A\in\Theta,\;B\in\mathbb{S}^d,\;\|B\|_2\leq\epsilon/2\},$$ we have that $S_i \cap S_j=\emptyset$ for all $i\neq j$ and $\bigcup_i S_i \subseteq \Theta'$. So, given any measure $\mu$ on $\mathbb{S}^d$ (or even just on $\Theta'$), $$ \sum_{i=1}^P \mu(S_i)\leq \mu(\Theta') $$ which can be used to upper bound $P$, especially if $\mu(S_i)=\mu(S_j)$ in which case $P\leq \mu(\Theta')/\mu(S_1)$. Now the question is how to define and compute such a "uniform" measure.

After some google and mathoverflow searches, I learned a little bit about Haar measures, Weyl integration formulas, and other such wonderful things, but every answer I found seemed to be not directly applicable to my problem because of the fact that I am dealing with symmetric matrices.

The approach I'm considering now is to separately define a uniform measure on onthonormal matrices, and one on eigenvalue matrices (equivalently, vectors with non-increasing entries), and combine the two as eigenvalues and eigenvectors of my symmetric matrices to give a "marginal" measure. But I'm not really sure what the best way to go about this is (I'm not even sure the resulting measure would, for instance, be absolutely continuous w.r.t. Lebesgue on the upper triangle, though perhaps that doesn't matter).

It may be worth noting that in my original problem I actually need a bound on the covering number of this set, and I initially considered trying to separately cover orthonormal matrices and the eigenvalues, and then combine them. But the obstacle was that I couldn't get a good upper bound on $\|U_1\Lambda_1U_1^T-U_2\Lambda_2U_2^T\|_2$ in terms of (some norm of) $U_1-U_2$ and $\Lambda_1-\Lambda_2$.

Any help would be appreciated.

  • $\begingroup$ Martin, maybe the following similar question is sorta helpful (though it did not see much activity): mathoverflow.net/questions/122934/… --- also, by $a \preceq A$ do you mean $a I \preceq A$? Also, as for "good" upper bound on the last term you wrote, what does "good" mean? E.g., it can be bounded by $\|\Lambda_1 - \Lambda_2\|_2$, but that is not "good" enough I guess? $\endgroup$
    – Suvrit
    Nov 7, 2013 at 22:43
  • $\begingroup$ @Suvrit Thanks. Yes, $a\preceq A$ is shorthand for $aI\preceq A$, and good means that the resulting upper bound should scale correctly in terms of $\epsilon$. So for instance if it were true that $\|U_1\Lambda_1 U_1^T-U_2\Lambda_2 U_2^T\|_2\leq\|U_1-U_2\|_2+\|\Lambda_1-\Lambda_2\|_2$, that would probably be good enough. On the other hand, $\|U_1\Lambda_1 U_1^T-U_2\Lambda_2 U_2^T\|_2\leq d \|U_1-U_2\|_{\infty,\infty}+d \|\Lambda_1-\Lambda_2\|_{\infty,\infty}$ (I'm just making that up, as an example) probably would be too loose. $\endgroup$
    – martin
    Nov 8, 2013 at 8:30
  • $\begingroup$ what I meant was that $\|\Lambda_1^\downarrow-\Lambda_2^\uparrow\|$ is an upper bound (the arrows denote sorting)---this might be too loose, but with suitable choice of matrices, equality can be achieved in this....hence.... $\endgroup$
    – Suvrit
    Nov 8, 2013 at 13:59
  • $\begingroup$ @Suvrit oh I see, yes that would be an upper bound, unfortunately in this example I think it's too loose because $a$ and $b$ are fixed, hence for small enough $\epsilon$ I can't guarantee $\|\Lambda_1^{\downarrow}-\Lambda_2^{\uparrow}\|\leq \epsilon$.. $\endgroup$
    – martin
    Nov 8, 2013 at 18:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.