1
$\begingroup$

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})$ ?

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.