# A packing ball problem: verify lower bound on Gaussian width of sparse ball

Note: This should be a geometry problem about packing balls. All the necessary probability pre-requisite is given below.

Consider a set of sparse vectors: $$T_{n,s}:=\{x\in \mathbb{R}^n:\|x\|_0 \le s, \|x\|_2\le1\}$$ where $$\|x\|_0 \le s$$ simply means there can be at most $$s$$ non-zero coordinates. Gaussian width of a set of vectors is defined as $$w(T)=\sup_{x\in T}\langle x, g\rangle$$ where $$g\sim \mathcal{N}(0,I_n)$$.

The claim is that $$w(T_{n,s})\ge c\sqrt{s\log{(2n/s)}}.$$

The author suggests that we can use so-called Sudakov inequality which states that $$w(T)\ge \epsilon\sqrt{\log P(T,d,\epsilon)}$$ where $$P(T,d,\epsilon)$$ is ANY valid $$\epsilon-$$packing of $$T_{n,s}$$. A $$\epsilon-$$packing is a subset of $$T$$ such that for any pair of points in the packing has distance larger than $$\epsilon>0$$.

A partial result of mine: I considered packing $$T_{n,s}$$ with the following: there are $$\binom{n}{s}\ge (n/s)^s$$ ways to choose the k nonzero coordinates out of n coordinates. For each choice, we consider assigning all s non-zero coordinates as $$\sqrt{1/s}.$$ This way any pair of points has distance at least $$\epsilon=\sqrt{2}/\sqrt{s}$$ (because they have at least two non-overlapping coordinates). This packing gives $$w(T)\ge \frac{\sqrt{2}}{\sqrt{s}}\sqrt{s \log (2n/s)}$$. I'm still missing $$\sqrt{s}$$ factor.

How can I choose the packing more optimally to recover this $$\sqrt{s}$$ factor?

Thank you!

• The usual trick: you have ${n\choose s}$ vectors of your type and for each vector there are at most ${s\choose s/2}{n\choose s/2}$ vectors of your type that overlap with a given vector in at least $s/2$ coordinates. Thus, doing the greedy algorithm, you can choose at least ${n\choose s}/[{n\choose s/2}{s\choose s/2}]\ge 2^{-s}[\frac{n-s}{s}]^{s/2}$ vectors at constant distance from each other, For $s<n/10$ this crude bound gives the desired result and then you just use the monotonicity of the width. Aug 24, 2020 at 20:36
• Thank you for the insight. Aug 24, 2020 at 20:49