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:
\begin{equation}
\mathcal{M}=\{\Theta \in S_n(\mathbb{R})| \ \|\Theta\|_{0}\leq K, \|\Theta\|_F \leq r\}
\end{equation}
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})$ ?
 A: One answer for the second case. We can see that we have to look at (for $k \in \mathbb{N}$):
\begin{equation}
\mathcal{M}=\{\Theta \in S_n^{++}(\mathbb{R})| \ \|\Theta\|_0 \leq n +2k, \|\Theta\|_F \leq r\}
\end{equation}
(indeed if $K<n$ 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:
\begin{equation}
\mathfrak{W}= \left\{\Theta \in S_{n}^{++}(\mathbb{R})| \ \ \|\Theta\|_{0} \leq n+2k, \|\Theta\|_{F} \leq 1\right\}
\end{equation}
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:
\begin{equation}
\|D+T+T^{\top}-(D_*+T_*+T_*^{\top})\|_F\leq \|D-D_*\|_F+2\|T-T_*\|_F\leq \varepsilon
\end{equation}
Hence:
\begin{equation}
\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}
\end{equation}
Thus:
\begin{equation}
\mathcal{N}(\mathcal{M},\|.\|_F,\varepsilon) \leq (\frac{en(n-1)}{2k})^{k}(\frac{9 r}{\varepsilon})^{n+k}
\end{equation}
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).
