Nets, Covering Numbers and Metric Entropy

Definitions

DefinitionNets, covering and packing numbers

Let $(T,\rho)$ be a metric space and $\eps>0$.

• $\Ncal \subseteq T$ is an $\eps$-net of $T$ if every $x \in T$ has some $y \in \Ncal$ with $\rho(x,y)\le\eps$.
• The covering number $N(T,\rho,\eps)$ is the smallest cardinality of an $\eps$-net.
• $\mathcal{P}\subseteq T$ is $\eps$-separated if $\rho(x,y) > \eps$ for all distinct $x,y\in\mathcal{P}$; the packing number $P(T,\rho,\eps)$ is the largest cardinality of an $\eps$-separated set.
• $\log N(T,\rho,\eps)$ is the metric entropy of $T$ at scale $\eps$.

LemmaPacking and covering numbers are equivalent

For every $\eps>0$,

$$P(T,\rho,2\eps) \le N(T,\rho,\eps) \le P(T,\rho,\eps).$$

ProofReveal

So the two notions are interchangeable up to a factor of $2$ in the scale, and since every bound we prove is stated up to constants and logarithms, they may be used interchangeably. The practical consequence: to upper bound a covering number, exhibit a net; to lower bound it, exhibit a separated set.

The volumetric argument

TheoremVolumetric bound on covering numbers

Let $B^d$ be the unit Euclidean ball in $\R^d$ and $\eps \in (0,1)$. Then

$$\left(\frac1\eps\right)^d \;\le\; N(B^d, \norm{\cdot}_2, \eps) \;\le\; \left(\frac{3}{\eps}\right)^d .$$

The same bounds, with the same proof, hold for the sphere $S^{d-1}$.

ProofReveal

Using a net: the operator norm

LemmaOperator norm from a net

Let $A \in \R^{m\times d}$, let $\eps \in [0,1/2)$ and let $\Ncal$ be an $\eps$-net of $S^{d-1}$. Then

$$\sup_{x \in \Ncal}\norm{Ax}_2 \;\le\; \norm{A} \;\le\; \frac{1}{1-\eps}\,\sup_{x\in\Ncal}\norm{Ax}_2 .$$

In particular a $\tfrac12$-net gives $\norm{A} \le 2\max_{x\in\Ncal}\norm{Ax}_2$.

ProofReveal

Chaining and Dudley's integral

The net argument above is lossy. It approximates every point of $S^{d-1}$ at a single scale $\eps$, paying the full union-bound price at that scale. Chaining approximates at a sequence of geometrically decreasing scales, paying a smaller price at each.

DefinitionSub-Gaussian process

A stochastic process $(Z_t)_{t\in T}$ indexed by a metric space $(T,\rho)$ is sub-Gaussian if

$$\norm{Z_t - Z_s}_{\psi_2} \le C\rho(t,s) \qquad\text{for all } s,t \in T.$$

TheoremDudley's entropy integral

For a mean-zero sub-Gaussian process $(Z_t)_{t\in T}$,

$$\E\sup_{t\in T} Z_t \;\le\; C\int_0^\infty \sqrt{\log N(T,\rho,\eps)}\;d\eps .$$

The proof is the chaining argument: write $Z_t - Z_{t_0}$ as a telescoping sum along a sequence of nets at scales $2^{-k}$, apply a union bound at each scale, and sum the resulting geometric series. It is a beautiful argument and it is given in full in the references; it is stated here because the shape of the conclusion is what gets used.

DefinitionGaussian width

For a bounded set $T \subseteq \R^d$ and $g \sim \Ncal(0,I_d)$, the Gaussian width is

$$w(T) = \E\sup_{x\in T}\ip{g}{x}.$$

Gaussian width is the single scalar that governs a remarkable range of high-dimensional estimates: the operator norm of a random matrix restricted to $T$, the number of measurements needed for compressed sensing of signals in $T$, the error of an estimator constrained to $T$. Two reference values worth memorising:

$$w(S^{d-1}) = \E\norm{g}_2 \approx \sqrt d, \qquad w\big(\{x : \norm{x}_2 \le 1, \norm{x}_0 \le s\}\big) \lesssim \sqrt{s\log(d/s)} .$$

The second is the reason sparse recovery needs $O(s\log(d/s))$ measurements rather than $O(d)$: the complexity of the set of $s$-sparse unit vectors, measured by Gaussian width, is $\sqrt{s\log(d/s)}$, not $\sqrt d$. The sparse recovery page makes this quantitative.

Problems

The volumetric lower bound on covering numbersProof · Intermediate · 30 min The operator norm on a netProof · Intermediate · 30 min Covering numbers of the set of sparse unit vectorsProof · Advanced · 1 hour Gaussian width of the sphere and of the sparse setProof · Advanced · 30 min