# $\epsilon$-covering number of a set of rank-2 matrices

Suppose that two unit-norm vectors $\boldsymbol{a}\in \mathbb{R}^m$ and $\boldsymbol{b}\in\mathbb{R}^n$ are given with $m\leq n$. Furthermore, let $\boldsymbol{F}_{m,n}$ denote the first $m$ rows of the $n$-point DFT matrix. To bound the tail-probability of some random process, I need to upper bound $N\left(\mathcal{S},\left\Vert\cdot\right\Vert,\epsilon\right)$, the $\epsilon$-covering number of the set \begin{align*} \mathcal{S} =\left\{\boldsymbol{F}_{m,n}\odot\left(\boldsymbol{a}\boldsymbol{x}^\mathrm{T}+\boldsymbol{y}\boldsymbol{b}^\mathrm{T}\right)\mid \boldsymbol{x}\in\mathbb{R}^n,\boldsymbol{y}\in\mathbb{R}^m,\left\Vert \boldsymbol{a}\boldsymbol{x}^\mathrm{T}+\boldsymbol{y}\boldsymbol{b}^\mathrm{T}\right\Vert_{\mathrm{F}}\leq 1\right\}, \end{align*} where $\odot$ denotes the Hadamard product.

The upper bound that I managed to achieve is $\left(1+\frac{2}{\epsilon}\right)^{m+n-1}$. Is there any way that I can verify whether my naive bound is sharp or not?

To achieve the above bound I simply bounded the spectral norm of $\boldsymbol{F}_{m,n}\odot\boldsymbol{X}$ by the Frobenius-norm and reduced the covering to covering of a unit ball in $\mathbb{R}^{m+n-1}$. I asked here if there is any better bound for the spectral norm I mentioned, but I didn't get any response that is obviously better than the Frobenius norm.

• You could use $\|F\circ X\| \le \|F\| \cdot \|X\|$, and since $\|F\| \le 1$, we have the bound $\|F\circ X\| \le \|X\|$, the operator norm of $X$ instead of the Frobenius norm. Mar 9, 2015 at 21:50
• @Suvrit Could you elaborate on how you get the first inequality?
– S.B.
Mar 10, 2015 at 0:19
• $F\circ X$ is a principal submatrix of the Kronecker product $F \otimes X$, hence $\|F\circ X\| \le \|F \otimes X\| = \|F\| \cdot \|X\|$ Mar 10, 2015 at 1:17