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!

  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Aug 24, 2020 at 20:36
  • $\begingroup$ Thank you for the insight. $\endgroup$
    – Daniel Li
    Aug 24, 2020 at 20:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.