an introduction to epsilon-net argument and symmetrization

$epsilon$-net argument is always used to bound the norm of matrix. Combining with union bound, we can easily bound for a random matrix which has sub-gaussian distributions. Further, it is easy to derive RIP by this method for sub-gaussian matrix.

Lemma 1 Let $A$ be an $m times n$ matrix and $epsilon in [0,1)$. Then, for any $epsilon$-net $mathcal{N}$ of the sphere $S^{n-1}$, we have
$$
sup limits_{x in mathcal{N}} ||Ax||_2 le ||A|| le frac{1}{1-epsilon} sup limits_{x in mathcal{N}} ||Ax||_2
$$

Lemma 2 Let $A$ be an $m times n$ matrix and $epsilon in [0,1/2)$. Then, for any $epsilon$-net $mathcal{N}$ of the sphere $S^{n-1}$ and any $epsilon$-net $mathcal{M}$ of the sphere $S^{m-1}$, we have
$$
sup limits_{x in mathcal{N},y in mathcal{M}} (Ax,y) le ||A|| le frac{1}{1-2epsilon} sup limits_{x in mathcal{N},y in mathcal{M}} (Ax,y)
$$

• Step 1: Approximation. Choosing an $epsilon$ and using Lemma 1 or 2, we get, for example,
  $$
  ||A|| le frac{1}{1-2epsilon} sup limits_{x in mathcal{N},y in mathcal{M}} (Ax,y)
  $$with $|mathcal{N}|le (1+2/epsilon)^n, |mathcal{M}|le (1+2/epsilon)^m$
• Step 2: Concentration. Fix $x in mathcal{N}$ and $y in mathcal{M}$. Then use concentration inequality like Berstein’s Inequality or definition of distributions to give the probability of tail bound.
• Step 3: Union Bound. Unfix $x,y$ and take the union bound.

Lemma 3 Let $x_1,ldots,x_n$ be independent, mean zero random vectors in a normed space. Then

$$
frac{1}{2} mathbb{E} ||sum limits_{i=1}^{n}epsilon_i x_i|| le mathbb{E}||sum limits_{i=1}^{n} x_i|| le 2 mathbb{E}||sum limits_{i=1}^{n} epsilon_i x_i||
$$

A typical application of Symmetrization has two steps. First, general random variables $x_i$ are replaced by symmetric random variables $epsilon_i x_i$. Next, one conditions on $x_i$ and leaves the entire randomness within $epsilon_i$. This reduces the problem to symmetric Bernoulli random variables $epsilon_i$, which are often simpler to deal with.