= Maximum of finitely many Rademacher linear forms
{title2=$\Pr(\max_i|u_i^T\xi|\le\alpha)>1-2me^{-\alpha^2/2}$}
For <independent> <Rademacher random variables> and $\|u_i\|_2\le1$, this bound holds for $\alpha>0$. The <moment-generating function> satisfies $\prod_j\cosh(tu_{ij})\le e^{t^2/2}$, with strict inequality for a nonzero <vector> and $t>0$. Applying the exponential Markov bound to both tails and then the <union bound> proves a strict failure bound; a zero <vector> has failure <probability> zero. At $\alpha=\sqrt{2\log(2m)}$, the success <probability> is strictly positive, ensuring a sign <vector> with all linear forms below that threshold.
Back to article page
