# Covering number in the space of symmetric matrices

Let $$S_n(\mathbb{R})$$ be the set of symmetric matrices of size $$n \times n$$. Note $$\|\Theta\|_{0}$$ the number of nonzero elements of a matrix $$\Theta$$ and $$\|\cdot\|_F$$ the Froebenius norm. Consider the following set: $$$$\mathcal{M}=\{\Theta \in S_n(\mathbb{R})| \ \|\Theta\|_{0}\leq K, \|\Theta\|_F \leq r\}$$$$

I was wondering what was a good estimation of the covering number $$\mathcal{N}(\mathcal{M},\|\cdot\|_{F},\varepsilon)$$ of $$\mathcal{M}$$ with respect to $$\|\cdot\|_F$$ ?

Do we also have an estimation of it when $$\Theta \in S^{++}_n(\mathbb{R})$$ the space of positive definite matrices instead of $$\Theta \in S_n(\mathbb{R})$$ ?

One answer for the second case. We can see that we have to look at (for $$k \in \mathbb{N}$$): $$$$\mathcal{M}=\{\Theta \in S_n^{++}(\mathbb{R})| \ \|\Theta\|_0 \leq n +2k, \|\Theta\|_F \leq r\}$$$$ (indeed if $$K then the matrix can not be PD and then we can use the symmetry and the fact that $$\Theta$$ is PD so it has exactly $$n$$ coefficients $$>0$$ on the diagonal).
Now consider: $$$$\mathfrak{W}= \left\{\Theta \in S_{n}^{++}(\mathbb{R})| \ \ \|\Theta\|_{0} \leq n+2k, \|\Theta\|_{F} \leq 1\right\}$$$$ Take $$\Theta \in \mathfrak{W}$$, it can be written as $$\Theta= D+T+T^{\top}$$ where $$D$$ is diagonal with $$n$$ strictly positive elements, $$T$$ is strictly upper-triangular matrix with at most $$k$$ non zero elements. We have also that $$\|D\|_F \leq \|\Theta\|_{F} \leq 1$$ and same for $$T,T^{\top}$$.
Consider $$\overline{D}$$ a $$\varepsilon/2$$-net for the diagonal and $$\overline{D}$$ a $$\varepsilon/3$$-net for the upper triangular matrix, both with respect to the $$\|\cdot\|_{F}$$ norm. Then $$\#\overline{D} \leq (9/\varepsilon)^{n}$$ because this is a unit ball with respect to $$\|\cdot\|_F$$ and $$\#\overline{T} \leq \binom{\frac{n(n-1)}{2}}{k}(\frac{9}{\varepsilon})^{k}$$ because it is a unit ball in the space of $$k$$-sparse vectors in dimension $$\frac{n(n-1)}{2}$$.
Consider $$\overline{\mathfrak{W}}=\{D_*+T_*+T_*^{\top}, (D_*,T_*) \in \overline{D}\times \overline{T}\}$$. Then $$\#\overline{\mathfrak{W}} \leq \binom{\frac{n(n-1)}{2}}{k}(\frac{9}{\varepsilon})^{k}(9/\varepsilon)^{n}=\binom{\frac{n(n-1)}{2}}{k}(\frac{9}{\varepsilon})^{n+k}$$. And we have for any $$\Theta= D+T+T^{\top}$$ the existence of $$(D_*,T_*) \in \overline{D}\times \overline{T}$$ such that $$\|D-D_*\|_F\leq \varepsilon/3, \|T-T_*\|_F \leq \varepsilon/3$$. Hence: $$$$\|D+T+T^{\top}-(D_*+T_*+T_*^{\top})\|_F\leq \|D-D_*\|_F+2\|T-T_*\|_F\leq \varepsilon$$$$ Hence: $$$$\mathcal{N}(\mathfrak{W},\|.\|_F,\varepsilon) \leq \binom{\frac{n(n-1)}{2}}{k}(\frac{9}{\varepsilon})^{n+k}\leq (\frac{en(n-1)}{2k})^{k}(\frac{9}{\varepsilon})^{n+k}$$$$ Thus: $$$$\mathcal{N}(\mathcal{M},\|.\|_F,\varepsilon) \leq (\frac{en(n-1)}{2k})^{k}(\frac{9 r}{\varepsilon})^{n+k}$$$$
Maybe we can do better because I did not really used that $$\Theta$$ is PD (only for proving that it has necessarily $$n$$ nonzero coefficients on the diagonal).