Covering numbers of the set of sparse unit vectors

ProofAdvanced⏱ 1 hourHigh-Dim Probabilitysparsitycovering numbercompressed sensing

Problem

Let $\mathcal S_{s} = \{x\in\R^p : \|x\|_2\le1,\ \|x\|_0\le s\}$ be the set of $s$ -sparse vectors in the unit ball. Prove that

\log N\big(\mathcal S_s, \|\cdot\|_2, \eps\big) \le s\log\frac{ep}{s} + s\log\frac3\eps .

Compare with $\log N(B^p,\|\cdot\|_2,\eps) \approx p\log(3/\eps)$ and explain the consequence for sample complexity.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 3 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
The geometry of l1 versus l2 constraints	High-Dim Statistics	Proof	Intermediate	30 min
The operator norm on a net	High-Dim Probability	Proof	Intermediate	30 min
The volumetric lower bound on covering numbers	High-Dim Probability	Proof	Intermediate	30 min
Gaussian width of the sphere and of the sparse set	High-Dim Probability	Proof	Advanced	30 min
Union bound over supports for the restricted isometry property	High-Dim Statistics	Proof	Advanced	1 hour