High-Dimensional Probability · Study tools

InteractiveVershynin, Ch. 1: A Quick Refresher on Analysis and Probability

Tail bounds from moments

Almost every estimate in high-dimensional probability starts from a few blunt tools: Jensen, Markov, Chebyshev and the union bound. They are crude, but in a way you can control. Here you can see how much each one gives away, and why the next chapter wants exponential moments.

The idea

$L^p$ norms. For a random variable

X

and

p\ge1

,

\|X\|_{L^p}=(\mathbb E|X|^p)^{1/p}

, and

\|X\|_{L^\infty}

is the essential supremum of

|X|

. These norms increase with

p

.

Jensen. If

\varphi

is convex, then

\varphi(\mathbb E X)\le\mathbb E\,\varphi(X)

.

Markov and its relatives. If

X\ge0

and

t>0

, then

\mathbb P(X\ge t)\le \mathbb E X/t

. Applying this to

|X|^p

or to

(X-\mathbb E X)^2

gives

\mathbb P(|X|\ge t)\le\frac{\mathbb E|X|^p}{t^p}, \qquad \mathbb P\big(|X-\mathbb E X|\ge t\big)\le\frac{\operatorname{Var}X}{t^2}\ \ \text{(Chebyshev)}.

Union bound.

\mathbb P(A_1\cup\dots\cup A_N)\le\sum_i\mathbb P(A_i)

. It needs no independence, and it costs a factor

N

, which is cheap whenever each

\mathbb P(A_i)

is exponentially small.

Limit theorems. For i.i.d.

X_i

with mean

\mu

and variance

\sigma^2

, the sample mean

\bar X_N\to\mu

(law of large numbers) and

\sqrt N(\bar X_N-\mu)/\sigma\to N(0,1)

in distribution (central limit theorem).

Asymptotic is not a bound. The CLT says nothing about a fixed

N

. Its error at finite

N

(Berry–Esseen) is of order

1/\sqrt N

, which is far larger than the tiny tail probabilities we usually care about.

Explore

true tail Markov Chebyshev

p

-th moment bound

Distribution of X

Threshold t Moment order p

Worked example

You average $N$ i.i.d. measurements with unknown mean $\mu$ and variance $\sigma^2=1$ . How large must $N$ be for $|\bar X_N-\mu|<0.1$ with probability at least $0.99$ ? And what if you run 1000 such experiments and want all of them to succeed at once?

What does Chebyshev guarantee for one experiment?

$\operatorname{Var}\bar X_N=1/N$ , so $\mathbb P(|\bar X_N-\mu|\ge0.1)\le 1/(0.01N)$ . This is at most $0.01$ once $N\ge 10\,000$ .
What does the CLT suggest instead?

Treat $\sqrt N(\bar X_N-\mu)$ as standard normal. A two-sided normal tail of $0.01$ needs $z\approx2.576$ , so $0.1\sqrt N\ge 2.576$ , i.e. $N\ge 664$ . That is 15 times fewer, but it is a heuristic, not a guarantee.
Now 1000 experiments must all succeed with total failure probability $0.01$ . Use the union bound. What failure probability can each experiment have, and what $N$ does each method ask for?

Each may fail with probability $10^{-5}$ . Chebyshev needs $1/(0.01N)\le10^{-5}$ , so $N\ge10^7$ : a thousand times more. The normal heuristic needs $z\approx4.417$ , so $N\ge(44.17)^2\approx1952$ : only three times more.
Can you trust the 1952?

Not from the CLT alone. The normal approximation to the distribution function has error of order $1/\sqrt N\approx0.02$ here, two thousand times bigger than the $10^{-5}$ we are estimating. Chebyshev is rigorous but only polynomial in $1/\delta$ . What we want is a rigorous bound with Gaussian-like decay at every finite $N$ . That is the next module.

Check your understanding

All you know about $X$ is that $X\ge0$ and $\mathbb E X=1$ . What is the best upper bound on $\mathbb P(X\ge10)$ that holds for every such $X$ ?

$1/10$
$1/100$ A $1/t^2$ bound needs a second moment, and you don't know $\mathbb E X^2$ . It could be huge.
$e^{-10}$ Exponential decay needs exponential moments. A nonnegative variable with mean 1 can have a heavy tail.
There is no bound without more information.Markov's inequality uses exactly these two facts.

Markov gives

1/10

, and nothing better is possible:

X=10

with probability

1/10

and

X=0

otherwise has mean 1 and

\mathbb P(X\ge10)=1/10

.

Which inequality holds for every random variable (with the expectations finite)?

$\mathbb E|X|\le(\mathbb E X^2)^{1/2}$
$\mathbb E\,e^X\le e^{\mathbb E X}$ $e^x$ is convex, so Jensen goes the other way.
$\mathbb E\log X\ge\log\mathbb E X$ for $X>0$ $\log$ is concave, so Jensen gives $\le$ .
$\mathbb E\sqrt{X}\ge\sqrt{\mathbb E X}$ for $X\ge0$ $\sqrt{x}$ is concave; try $X\in\{0,4\}$ with equal probability.

Apply Jensen to the convex function

x\mapsto x^2

and the variable

|X|

:

(\mathbb E|X|)^2\le\mathbb E X^2

. It is the case

p=1\le q=2

of the monotonicity of

L^p

norms.

You have $10^6$ events, each of probability at most $e^{-t^2/2}$ . Roughly how large must $t$ be for the union bound to give $\mathbb P(\text{any event})\le0.01$ ?

$t\approx6.1$
$t\approx2.6$ That makes a single event unlikely. With a million of them you need each to have probability $10^{-8}$ .
$t\approx1000$ The number of events enters only through a logarithm, not through $t$ itself.
The union bound is useless for a million events.It loses a factor $10^6$ , but a Gaussian tail absorbs that easily.

Need

10^6e^{-t^2/2}\le10^{-2}

, i.e.

t^2\ge2\ln10^8\approx36.8

, so

t\approx6.07

. With Gaussian tails, a union bound over

N

events costs only a factor

\sqrt{2\ln N}

in the threshold. This is used again and again in the later chapters.

Practice

Markov is sharp at every thresholdExtremal examples

Fix $0<a\le t$ . Find a nonnegative $X$ with $\mathbb E X=a$ and $\mathbb P(X\ge t)=a/t$ . Then show that if equality holds in Markov's inequality, $X$ must take only the values $0$ and $t$ .

Hint

Write $X\ge t\cdot\mathbf 1\{X\ge t\}$ and ask when this is an equality.

Solution

Take $X=t$ with probability $a/t$ and $X=0$ otherwise. In general $X\ge t\,\mathbf 1\{X\ge t\}$ pointwise, so $\mathbb E X\ge t\,\mathbb P(X\ge t)$ . Equality forces $X=t\,\mathbf 1\{X\ge t\}$ almost surely, so $X\in\{0,t\}$ .

When is the union bound nearly exact?Independent rare events

Let $A_1,\dots,A_N$ be independent with $\mathbb P(A_i)=\delta$ . Show that $N\delta\big(1-\tfrac{N\delta}{2}\big)\le\mathbb P(\bigcup A_i)\le N\delta$ . What does this say when $N\delta=0.01$ ?

Hint

$\mathbb P(\bigcup A_i)=1-(1-\delta)^N$ . Use $1-x\le e^{-x}$ and $e^{-y}\le1-y+y^2/2$ for $y\ge0$ .

Solution

The upper bound is the union bound. For the lower, $(1-\delta)^N\le e^{-N\delta}\le1-N\delta+(N\delta)^2/2$ , so $1-(1-\delta)^N\ge N\delta-(N\delta)^2/2$ . With $N\delta=0.01$ , the union bound is off by at most half a percent of its value. It is wasteful only when the events overlap heavily.

More practice: Vershynin, Exercises 1.11 and 1.16.

SimulationVershynin, Ch. 2: Concentration of Sums of Independent Random Variables

Concentration of sums

A sum of $n$ independent terms with values in $[0,1]$ exceeds its mean by $s$ with probability at most $e^{-2s^2/n}$ , for every $n$ , not just in the limit. Hoeffding, Chernoff and Bernstein are three versions of this, and the differences between them matter exactly when some terms are rare.

The idea

Hoeffding. If

\varepsilon_1,\dots,\varepsilon_N

are independent random signs and

a\in\R^N

, then

\mathbb P\big(\sum a_i\varepsilon_i\ge t\big)\le\exp\!\big(-t^2/2\|a\|_2^2\big)

. If instead

X_i\in[m_i,M_i]

are independent,

\mathbb P\Big(\sum_{i=1}^N(X_i-\mathbb E X_i)\ge t\Big)\le\exp\Big(-\frac{2t^2}{\sum_i(M_i-m_i)^2}\Big).

Chernoff. If

X_i

are independent Bernoulli

(p_i)

,

S=\sum X_i

and

\mu=\mathbb E S

, then for

t>\mu

,

\ \mathbb P(S\ge t)\le e^{-\mu}(e\mu/t)^t

. For small

\mu

this behaves like a Poisson tail and is far smaller than Hoeffding's bound.

All of these come from one move: apply Markov to $e^{\lambda S}$ , factor $\mathbb E e^{\lambda S}$ using independence, and optimise over $\lambda$ .

Subgaussian.

\|X\|_{\psi_2}=\inf\{K>0:\mathbb E\exp(X^2/K^2)\le2\}

. Finite

\psi_2

norm is equivalent, up to absolute constants, to tails

\mathbb P(|X|\ge t)\le2e^{-t^2/K^2}

, to moments

\|X\|_{L^p}\lesssim K\sqrt p

, and (for mean zero) to

\mathbb E e^{\lambda X}\le e^{CK^2\lambda^2}

.

General Hoeffding. For independent mean-zero subgaussian

X_i

,

\ \mathbb P\big(|\sum X_i|\ge t\big)\le2\exp\big(-ct^2/\sum\|X_i\|_{\psi_2}^2\big)

.

Bernstein. For independent mean-zero subexponential

X_i

(

\|X\|_{\psi_1}=\inf\{K:\mathbb E e^{|X|/K}\le2\}

finite), with

K=\max\|X_i\|_{\psi_1}

,

\mathbb P\Big(\Big|\sum_{i=1}^N X_i\Big|\ge t\Big)\le2\exp\Big(-c\min\Big(\frac{t^2}{\sum_i\|X_i\|_{\psi_1}^2},\ \frac tK\Big)\Big):

a Gaussian tail for moderate $t$ , an exponential one far out.

Explore

Number of trials n Success probability p Threshold k

exact

\mathbb P(S\ge k)

,

S\sim\mathrm{Bin}(n,p)

simulated Chebyshev Hoeffding Chernoff

Worked example

An A/B test estimates a click rate $p$ by the fraction $\hat p$ of $N$ independent users who click. We want $|\hat p-p|<0.01$ with probability at least $0.999$ . How many users are needed?

Use Chebyshev, knowing only $p(1-p)\le1/4$ .

$\mathbb P(|\hat p-p|\ge0.01)\le\dfrac{p(1-p)}{N\cdot 10^{-4}}\le\dfrac{1}{4N\cdot10^{-4}}$ . Setting this to $10^{-3}$ gives $N\ge2\,500\,000$ .
Use Hoeffding (each click indicator lies in $[0,1]$ ).

Two-sided: $\mathbb P(|\hat p-p|\ge\varepsilon)\le2e^{-2N\varepsilon^2}$ . We need $2e^{-2N\cdot10^{-4}}\le10^{-3}$ , i.e. $N\ge\ln(2000)/(2\cdot10^{-4})\approx38\,005$ . Sixty-five times fewer users.
Suppose you also know $p\le0.02$ . Bernstein's inequality for variables with $|X_i-p|\le1$ reads $\mathbb P(|\sum(X_i-p)|\ge t)\le2\exp\big(-\tfrac{t^2/2}{N\sigma^2+t/3}\big)$ . What $N$ does it give?

Here $\sigma^2=p(1-p)\le0.02\cdot0.98=0.0196$ and $t=N\varepsilon$ , so the exponent is $N\varepsilon^2/\big(2(\sigma^2+\varepsilon/3)\big)$ . We need it to be at least $\ln2000\approx7.60$ :

$N\ \ge\ \frac{2\,(0.0196+0.00333)\cdot7.60}{10^{-4}}\ \approx\ 3487.$

Another factor of 11. Hoeffding pays for the worst-case variance $1/4$ ; Bernstein pays only for the actual variance.
How does each answer scale with the failure probability $\delta$ ?

Chebyshev needs $N\propto1/\delta$ ; Hoeffding and Bernstein need $N\propto\log(1/\delta)$ . Asking for $\delta=10^{-6}$ instead of $10^{-3}$ multiplies the Chebyshev answer by 1000, but the Hoeffding answer by less than 2.

Check your understanding

Which of these random variables is not subgaussian?

A random variable with $|X|\le 5$ almost surelyBounded variables are subgaussian: $\mathbb E e^{X^2/K^2}\le e^{25/K^2}$ , which is at most 2 for large $K$ .
$N(0,\sigma^2)$ The Gaussian is the model subgaussian variable, with $\|X\|_{\psi_2}$ a constant times $\sigma$ .
An exponential random variable
A sum of 100 independent random signsThat sum is bounded by 100, and better, it has $\psi_2$ norm of order $\sqrt{100}$ .

\mathbb P(X\ge t)=e^{-t}

decays only exponentially, so

\mathbb E e^{X^2/K^2}=\infty

for every

K

. The exponential is the model subexponential variable, which is where Bernstein's inequality takes over.

$S\sim\mathrm{Bin}(10^4,10^{-4})$ , so $\mathbb E S=1$ . Hoeffding bounds $\mathbb P(S\ge10)$ by about $0.98$ ; Chernoff by about $8\times10^{-7}$ . Why is Hoeffding so weak here?

It only uses that each term lies in $[0,1]$ , not that each term is almost always 0.
Hoeffding needs identically distributed terms.It doesn't, and these terms are identically distributed anyway.
Hoeffding needs symmetric terms.The version for bounded variables needs only independence and the ranges.
Hoeffding only holds for large $n$ .It holds for every $n$ . It is a true bound here, just a useless one.

Hoeffding's exponent

2t^2/n

is what you'd get if every term had the largest variance a

[0,1]

variable can have, namely

1/4

. Here the variance is

10^{-4}

. Chernoff (or Bernstein) sees the true variance. Try

p=0.005

in the explorer.

Let $X_i=g_i^2-1$ with $g_i$ i.i.d. standard normal, so the $X_i$ are mean-zero subexponential. For which deviations $t$ does Bernstein give a Gaussian-type bound $e^{-ct^2/N}$ for $\mathbb P(|\sum_{i\le N}X_i|\ge t)$ ?

For $t\lesssim N$
For $t\gtrsim N$ Compare $t^2/N$ with $t$ : which is smaller when $t$ is large?
For all $t$ Then $\sum X_i$ would be subgaussian, but $\mathbb P(X_1\ge t)$ alone already decays like $e^{-t/2}$ .
Only for $t\lesssim\sqrt N$ $\sqrt N$ is the typical size of the sum, but the Gaussian regime extends much further.

The minimum of

t^2/N

and

t

is

t^2/N

exactly when

t\le N

. So the sum looks Gaussian (scale

\sqrt N

) well into its tail, and only beyond

t\approx N

does the exponential tail of a single term take over.

Practice

Two subgaussian normsComputing ψ₂ from the definition

(a) Show that if $|X|\le M$ , then $\|X\|_{\psi_2}\le M/\sqrt{\ln2}$ , with equality for $X=\pm M$ with equal probability. (b) Compute $\|g\|_{\psi_2}$ for $g\sim N(0,1)$ .

Hint

For (b), $\mathbb E e^{sg^2}=(1-2s)^{-1/2}$ for $s<1/2$ .

Solution

(a) $\mathbb E e^{X^2/K^2}\le e^{M^2/K^2}\le2$ once $K^2\ge M^2/\ln2$ ; for $X=\pm M$ the first inequality is an equality, so this $K$ is the smallest. (b) Set $(1-2/K^2)^{-1/2}=2$ : then $1-2/K^2=1/4$ , $K^2=8/3$ , $\|g\|_{\psi_2}=\sqrt{8/3}\approx1.633$ .

From MGFs to a tail boundThe exponential moment method

Suppose $X_1,\dots,X_N$ are independent and $\mathbb E e^{\lambda X_i}\le e^{\lambda^2\sigma_i^2/2}$ for all $\lambda\in\R$ . Prove $\mathbb P(\sum X_i\ge t)\le\exp\big(-t^2/2\sum\sigma_i^2\big)$ for $t\ge0$ .

Solution

For $\lambda>0$ , Markov and independence give $\mathbb P(S\ge t)\le e^{-\lambda t}\prod\mathbb E e^{\lambda X_i}\le\exp(-\lambda t+\lambda^2V/2)$ with $V=\sum\sigma_i^2$ . The exponent is smallest at $\lambda=t/V$ , where it equals $-t^2/2V$ . Random signs satisfy the hypothesis with $\sigma_i=|a_i|$ , because $\cosh x\le e^{x^2/2}$ ; this recovers Hoeffding.

More practice: Vershynin, Exercises 2.13 and 2.25.

SimulationVershynin, Ch. 3: Random Vectors in High Dimensions

Random vectors in high dimensions

A standard Gaussian vector in $\R^n$ has length $\sqrt n\pm O(1)$ , and two independent ones are almost perpendicular. Both facts are concentration of a sum, and together they make high-dimensional space behave very differently from the plane.

The idea

Concentration of the norm. If

X=(X_1,\dots,X_n)

has independent coordinates with

\mathbb E X_i^2=1

and

\|X_i\|_{\psi_2}\le K

, then

\big\|\,\|X\|_2-\sqrt n\,\big\|_{\psi_2}\le CK^2

. The length is

\sqrt n

up to a fluctuation that does not grow with

n

.

Isotropic. A random vector is isotropic if

\mathbb E XX^{\mathsf T}=I_n

, i.e.

\mathbb E\langle X,x\rangle^2=\|x\|_2^2

for every

x

. Then

\mathbb E\|X\|_2^2=n

, and for an independent isotropic

Y

,

\mathbb E\langle X,Y\rangle^2=n

.

So $\cos\angle(X,Y)\approx\langle X,Y\rangle/n$ is typically of size $1/\sqrt n$ : independent random directions are nearly orthogonal. Examples of isotropic distributions: $N(0,I_n)$ , the uniform distribution on the sphere of radius $\sqrt n$ , random sign vectors, and the coordinate distribution $\sqrt n\,e_i$ with $i$ uniform.

Covariance and PCA.

\Sigma=\mathbb E(X-\mu)(X-\mu)^{\mathsf T}

. The top eigenvector of

\Sigma

is the direction

u

that maximises

\operatorname{Var}\langle X,u\rangle

; the next ones maximise it orthogonally to the previous.

Grothendieck and max-cut. Relaxing

\pm1

labels to unit vectors turns hard quadratic optimisation into a semidefinite program. Grothendieck's inequality says the relaxation loses only a constant factor. For max-cut, rounding the SDP vectors with a random hyperplane (Goemans–Williamson) gives, in expectation, at least

0.878

times the SDP value, hence at least

0.878

times the maximum cut.

Explore

Dimension

Coordinates

Left plot shows

Lengths of 1000 random vectors with independent unit-variance coordinates. normal approximation

Angles between 500 independent pairs. normal with sd 57.3°/√n

Worked example

Run Goemans–Williamson by hand on the 5-cycle $C_5$ (vertices $0,\dots,4$ , edges $\{k,k+1\}$ mod 5). The SDP is: maximise $\sum_{\{i,j\}\in E}\tfrac12(1-\langle u_i,u_j\rangle)$ over unit vectors $u_i$ .

What is the maximum cut of $C_5$ ?

4. A cut of all 5 edges would 2-colour an odd cycle, which is impossible; alternating labels around the cycle cut 4 edges.
Try planar vectors $u_k=(\cos\tfrac{4\pi k}5,\sin\tfrac{4\pi k}5)$ . What SDP value do they give?

Neighbours are at angle $4\pi/5$ , so each edge contributes $\tfrac12(1-\cos\tfrac{4\pi}5)=\tfrac12(1+\cos\tfrac\pi5)\approx0.9045$ , and the total is $\tfrac52(1+\cos\tfrac\pi5)\approx4.523$ . The relaxation beats every actual cut.
Show no unit vectors do better. (Write the objective with the graph Laplacian $L$ and the Gram matrix $G=(\langle u_i,u_j\rangle)$ .)

$\sum_{E}\tfrac12(1-\langle u_i,u_j\rangle)=\tfrac14\sum_E\|u_i-u_j\|^2=\tfrac14\operatorname{tr}(LG)\le\tfrac14\lambda_{\max}(L)\operatorname{tr}G=\tfrac n4\lambda_{\max}(L)$ , since $G\succeq0$ with unit diagonal. For $C_5$ , $\lambda_{\max}(L)=2-2\cos\tfrac{4\pi}5$ , so the bound is $\tfrac54\big(2+2\cos\tfrac\pi5\big)\approx4.523$ . The planar vectors are optimal.
Round with a random hyperplane through the origin: vertex $i$ goes to the side given by the sign of $\langle g,u_i\rangle$ . What is the expected cut, and how does it compare with the guarantee?

An edge is cut when the hyperplane separates its two vectors, which happens with probability (angle) $/\pi=4/5$ . So the expected cut is $5\cdot\tfrac45=4$ : the rounding finds a maximum cut on average. The ratio to the SDP value is $4/4.523\approx0.884$ , just above the $0.878$ guarantee; $C_5$ is close to the worst case.

Check your understanding

$X\sim N(0,I_n)$ with $n=10^4$ . Which description of $\|X\|_2$ is right?

About $100$ , give or take about $1$
About $100$ , give or take about $10$ $\|X\|^2$ fluctuates by about $\sqrt{2n}\approx141$ around $10^4$ , but taking a square root divides that by $2\sqrt n=200$ .
About $10^4$ , give or take about $100$ That describes $\|X\|_2^2$ , not $\|X\|_2$ .
Anywhere between $0$ and $200$ with comparable probabilityThe density of $X$ peaks at the origin, but the volume near the origin is tiny. Look at the left histogram.

\|X\|=\sqrt{n+(\|X\|^2-n)}\approx\sqrt n+\frac{\|X\|^2-n}{2\sqrt n}

, and

\|X\|^2-n

has standard deviation

\sqrt{2n}

. So the fluctuation is about

\sqrt{2n}/(2\sqrt n)=1/\sqrt2

, whatever

n

is.

$u,v$ are independent and uniform on the unit sphere $S^{n-1}$ . What is the typical size of $\langle u,v\rangle$ ?

Of order $1/\sqrt n$
Of order $1/n$ That is the size of $\mathbb E\langle u,v\rangle^2$ , not of $|\langle u,v\rangle|$ .
Of order 1In the plane, yes. In high dimension, almost all of the sphere is near the "equator" orthogonal to $u$ .
Exactly 0Orthogonality is approximate; $\langle u,v\rangle$ has a continuous distribution.

Condition on

u

; by rotation invariance

\langle u,v\rangle

has the law of one coordinate of

v

, and

\mathbb E v_1^2=1/n

. In the explorer this is the shrinking spread of the angle histogram around 90°.

In $\R^n$ you want unit vectors that are pairwise almost orthogonal: $|\langle u_i,u_j\rangle|\le0.1$ for $i\ne j$ . How many can you have?

Exponentially many in $n$
At most $n$ That is the limit for exactly orthogonal vectors. A little slack changes everything.
At most $n^2$ Count with random vectors and the union bound: the failure probability per pair is exponentially small.
At most $10n$ Try the union bound on $N$ random vectors: for which $N$ does it still work?

For random unit vectors,

\mathbb P(|\langle u_i,u_j\rangle|>0.1)\le2e^{-cn}

. A union bound over

N^2

pairs succeeds as long as

N^2e^{-cn}<1

, so

N=e^{cn/2}

vectors work. This is one reason high-dimensional data can hold so many "independent" directions.

Practice

Volume lives near the surfaceThe uniform distribution on a ball

$X$ is uniform in the unit ball of $\R^n$ . Show $\mathbb P(\|X\|_2\le1-\varepsilon)\le e^{-\varepsilon n}$ . For $n=1000$ , how thin is the outer shell that holds 99% of the volume?

Solution

By scaling, $\mathbb P(\|X\|\le r)=r^n$ , so $\mathbb P(\|X\|\le1-\varepsilon)=(1-\varepsilon)^n\le e^{-\varepsilon n}$ . For 99% in the shell, solve $(1-\varepsilon)^{1000}=0.01$ : $\varepsilon=1-0.01^{1/1000}\approx0.0046$ .

Norm concentration with only two momentsA Chebyshev version

For $X\sim N(0,I_n)$ , use $\operatorname{Var}\|X\|^2=2n$ and the inequality $|a-b|\le|a^2-b^2|/b$ (for $a\ge0$ , $b>0$ ) to show $\mathbb P\big(|\|X\|_2-\sqrt n|\ge t\big)\le2/t^2$ . What does the theorem above add?

Solution

$|\|X\|-\sqrt n|\le|\|X\|^2-n|/\sqrt n$ , so $\mathbb P(|\|X\|-\sqrt n|\ge t)\le\mathbb P(|\|X\|^2-n|\ge t\sqrt n)\le 2n/(t^2n)=2/t^2$ . This already shows fluctuations are $O(1)$ . The theorem upgrades the $1/t^2$ tail to a subgaussian $2e^{-ct^2}$ , which is what union bounds over many vectors need.

More practice: Vershynin, Exercises 3.12 and 3.41.

SimulationVershynin, Ch. 4: Random Matrices

Singular values of random matrices

A tall $m\times n$ random matrix stretches every direction by almost the same factor $\sqrt m$ : its singular values all lie in $[\sqrt m-C\sqrt n,\ \sqrt m+C\sqrt n]$ . The proof combines one-direction concentration with a union bound over an $\varepsilon$ -net of the sphere.

The idea

Singular values.

s_1(A)\ge\dots\ge s_n(A)\ge0

are the square roots of the eigenvalues of

A^{\mathsf T}A

.

\ s_1=\|A\|=\max_{x\in S^{n-1}}\|Ax\|_2

and, for

m\ge n

,

s_n=\min_{x\in S^{n-1}}\|Ax\|_2

. All singular values lie in

[a,b]

exactly when

a\|x\|\le\|Ax\|\le b\|x\|

for every

x

.

Nets and covering numbers.

\mathcal N\subseteq K

is an

\varepsilon

-net of

K

if every point of

K

is within

\varepsilon

of

\mathcal N

. The smallest size is the covering number

N(K,\varepsilon)

. By a volume argument,

N(S^{n-1},\varepsilon)\le(1+2/\varepsilon)^n

.

Two-sided bound. If

A

is

m\times n

with independent, mean-zero, isotropic, subgaussian rows,

\|A_i\|_{\psi_2}\le K

, then for every

t\ge0

, with probability at least

1-2e^{-t^2}

,

\sqrt m-CK^2(\sqrt n+t)\ \le\ s_n(A)\ \le\ s_1(A)\ \le\ \sqrt m+CK^2(\sqrt n+t).

For Gaussian entries the constant is sharp: $\mathbb E s_1\le\sqrt m+\sqrt n$ and $\mathbb E s_n\ge\sqrt m-\sqrt n$ (proved in Chapter 7). Equivalently, $\|\tfrac1mA^{\mathsf T}A-I_n\|\lesssim\sqrt{n/m}+n/m$ .

Covariance estimation. For

m

i.i.d. subgaussian samples in

\R^n

with covariance

\Sigma

, the sample covariance satisfies

\mathbb E\|\Sigma_m-\Sigma\|\lesssim\big(\sqrt{n/m}+n/m\big)\|\Sigma\|

. So

m\approx n/\varepsilon^2

samples give relative error

\varepsilon

: linear in the dimension.

Explore

Rows m Columns n

Singular values of

m\times n

matrices with i.i.d.

N(0,1)

entries, divided by

\sqrt m

.

[\sqrt m-\sqrt n,\ \sqrt m+\sqrt n]/\sqrt m

Marchenko–Pastur limit latest draw

Worked example

Bound the number of points needed for an $\varepsilon$ -net of the sphere $S^{n-1}$ , and see why that number decides how many rows a random matrix needs.

Take a maximal $\varepsilon$ -separated subset $\mathcal N$ of $S^{n-1}$ (pairwise distances $>\varepsilon$ , and no point can be added). Why is it an $\varepsilon$ -net?

If some $x\in S^{n-1}$ were at distance $>\varepsilon$ from all of $\mathcal N$ , we could add it and stay separated, contradicting maximality.
Bound $|\mathcal N|$ by comparing volumes.

Balls of radius $\varepsilon/2$ around the points of $\mathcal N$ are disjoint and all lie in the ball of radius $1+\varepsilon/2$ . Comparing volumes,

$|\mathcal N|\Big(\frac\varepsilon2\Big)^n\le\Big(1+\frac\varepsilon2\Big)^n \quad\Longrightarrow\quad |\mathcal N|\le\Big(1+\frac2\varepsilon\Big)^n.$

For $\varepsilon=1/2$ , at most $5^n$ points.
For a fixed unit $x$ , $\|Ax\|^2=\sum_i\langle A_i,x\rangle^2$ is a sum of $m$ independent terms with mean 1. What does Bernstein give?

Each $\langle A_i,x\rangle^2-1$ is mean-zero subexponential with norm $\lesssim K^2$ . Bernstein gives $\mathbb P\big(|\tfrac1m\|Ax\|^2-1|\ge\tfrac12\big)\le2e^{-cm}$ , with $c$ depending only on $K$ .
Union bound over a $\tfrac12$ -net. When does it work?

The probability that some net point fails is at most $2\cdot5^ne^{-cm}$ , which is small once $m\ge Cn$ . Then $\|Ax\|\approx\sqrt m$ on the whole net, and an approximation argument (any $x$ is within $\tfrac12$ of a net point) extends the bounds to the whole sphere. The net has exponentially many points, but exponential concentration pays for them. That is why the number of rows needs to be only proportional to $n$ .

Check your understanding

$A$ is a $1000\times10$ matrix with i.i.d. $N(0,1)$ entries. Where do you expect its singular values?

Roughly in $[28.5,\ 34.8]$
Roughly in $[0,\ 31.6]$ The matrix is very tall, so it is far from singular: $s_{10}$ is close to $\sqrt m$ , not to 0.
Roughly in $[990,\ 1010]$ Those would be eigenvalues of $A^{\mathsf T}A$ if they concentrated to within $\pm10$ ; singular values are their square roots.
All within $\pm0.1$ of $31.6$ The spread is of order $\sqrt n\approx3.2$ , not $o(1)$ .

\sqrt{1000}\approx31.62

and

\sqrt{10}\approx3.16

, so

[\sqrt m-\sqrt n,\sqrt m+\sqrt n]\approx[28.5,34.8]

. Set

m=400

,

n=4

in the explorer for a similar ratio.

For a square $n\times n$ Gaussian matrix, $\sqrt m-\sqrt n=0$ . What is true of its smallest singular value?

It is typically of order $1/\sqrt n$ : much smaller than the rest, but not zero.
It is typically of order $\sqrt n$ , like the others.Take $n=m$ in the explorer and look at the left end of the histogram.
It is 0 with positive probability.The set of singular matrices has measure zero, so a Gaussian matrix is invertible almost surely.

The bound

s_n\ge\sqrt m-C\sqrt n

becomes trivial when

m=n

. Finer arguments show

s_n(A)\approx1/\sqrt n

, while

s_1\approx2\sqrt n

, so the condition number is of order

n

.

To show $\|A\|\le C\sqrt m$ by a union bound over a $\tfrac12$ -net of $S^{n-1}$ , roughly how small must $\mathbb P(\|Ax\|>C'\sqrt m)$ be for a single fixed $x$ ?

Much smaller than $5^{-n}$
Smaller than $1/n$ The net has about $5^n$ points, not $n$ .
Smaller than $1/2$ That controls one direction. The norm is a maximum over all directions at once.
It doesn't matter, the net handles it.The net only makes the set of directions finite. The union bound still costs its size.

The union bound multiplies the single-direction failure probability by

|\mathcal N|\le5^n

. Exponential tails

e^{-cm}

beat this once

m\gtrsim n

. Polynomial (Chebyshev) tails would not.

Practice

All 2×2 sign matricesAn exact computation

Let $A$ be a $2\times2$ matrix with independent $\pm1$ entries. Find the distribution of $\|A\|$ and $s_2(A)$ , and compute $\mathbb E\|A\|$ and $\mathbb E s_2(A)$ . Compare with $\sqrt m\pm\sqrt n$ .

Hint

The second row is either $\pm$ the first row, or orthogonal to it.

Solution

With probability $1/2$ the rows are $\pm$ each other: $A$ has rank 1, $\|A\|=2$ , $s_2=0$ . Otherwise the rows are orthogonal of length $\sqrt2$ , so $A/\sqrt2$ is orthogonal and $s_1=s_2=\sqrt2$ . Hence $\mathbb E\|A\|=(2+\sqrt2)/2\approx1.71$ and $\mathbb E s_2=\sqrt2/2\approx0.71$ , inside $[\sqrt2-\sqrt2,\sqrt2+\sqrt2]=[0,2.83]$ . For tiny matrices the bounds are true but say little.

Approximate isometriesFrom AᵀA to singular values

Show that if $\big\|\tfrac1mA^{\mathsf T}A-I_n\big\|\le\delta$ with $\delta<1$ , then every singular value of $A$ lies in $[\sqrt{m(1-\delta)},\ \sqrt{m(1+\delta)}]$ , and hence in $[\sqrt m(1-\delta),\sqrt m(1+\delta)]$ .

Solution

$\tfrac1mA^{\mathsf T}A-I$ is symmetric with eigenvalues $s_i^2/m-1$ , and its norm is the largest of their absolute values. So $|s_i^2/m-1|\le\delta$ , i.e. $s_i^2\in[m(1-\delta),m(1+\delta)]$ . Finally $\sqrt{1-\delta}\ge1-\delta$ and $\sqrt{1+\delta}\le1+\delta$ .

More practice: Vershynin, Exercises 4.35 and 4.47.

SimulationVershynin, Ch. 5: Concentration Without Independence

Lipschitz concentration and Johnson–Lindenstrauss

Any Lipschitz function of a high-dimensional Gaussian (or of a uniform point on the sphere) is nearly constant, whether or not it is a sum. One consequence: $N$ points in any dimension can be projected to about $\log N/\varepsilon^2$ dimensions with every pairwise distance preserved up to $1\pm\varepsilon$ .

The idea

Gaussian concentration. If

X\sim N(0,I_n)

and

f:\R^n\to\R

is

L

-Lipschitz, then for all

t\ge0

\mathbb P\big(|f(X)-\mathbb E f(X)|\ge t\big)\le2e^{-t^2/2L^2}.

On the sphere. If

X

is uniform on

\sqrt n\,S^{n-1}

and

f

is

L

-Lipschitz, then

\|f(X)-\mathbb E f(X)\|_{\psi_2}\le CL

. The coordinates of

X

are not independent; the concentration comes from the geometry of the sphere (isoperimetry).

Johnson–Lindenstrauss. Let

x_1,\dots,x_N\in\R^n

and

\varepsilon\in(0,1)

. If

k\ge C\varepsilon^{-2}\log N

and

P

is a

k\times n

matrix with i.i.d.

N(0,1/k)

entries (or a suitably scaled random projection), then with high probability

(1-\varepsilon)\|x_i-x_j\|_2\le\|Px_i-Px_j\|_2\le(1+\varepsilon)\|x_i-x_j\|_2\quad\text{for all }i,j.

The target dimension depends on $N$ and $\varepsilon$ but not on $n$ , and $P$ is chosen without looking at the data. The proof: for one fixed vector $u$ , $\|Pu\|/\|u\|$ concentrates at 1 with subgaussian tails in $\sqrt k\,\varepsilon$ ; then union-bound over the $\binom N2$ differences.

Matrix Bernstein. For independent mean-zero symmetric

n\times n

random matrices

X_i

with

\|X_i\|\le K

and

\sigma^2=\|\sum\mathbb E X_i^2\|

,

\mathbb P\Big(\Big\|\sum_i X_i\Big\|\ge t\Big)\le2n\exp\Big(-\frac{t^2/2}{\sigma^2+Kt/3}\Big).

The dimension enters only as the factor $n$ in front, i.e. as a $\log n$ in the deviation. It handles covariance estimation for general (not subgaussian) distributions.

Explore

Points N Target dimension k

Data in ℝ³⁰⁰

How each pairwise distance changes.

[1-\varepsilon,1+\varepsilon]

,

\varepsilon

= worst pair

worst distortion for this projection, every

k

rough guide

\sqrt{2\ln N/k}

Worked example

Let $g\sim N(0,I_n)$ and $M=\max_{i\le n}g_i$ . How large is $M$ , and how much does it fluctuate?

Bound $\mathbb E M$ . (Hint: $e^{\lambda\mathbb E M}\le\mathbb E e^{\lambda M}$ .)

By Jensen, $e^{\lambda\mathbb E M}\le\mathbb E e^{\lambda M}\le\sum_i\mathbb E e^{\lambda g_i}=ne^{\lambda^2/2}$ . So $\mathbb E M\le\frac{\ln n}\lambda+\frac\lambda2$ , and $\lambda=\sqrt{2\ln n}$ gives $\mathbb E M\le\sqrt{2\ln n}$ . For $n=10^6$ that is about 5.26.
Show that $f(x)=\max_ix_i$ is 1-Lipschitz for the Euclidean norm.

If the max of $x$ is at $i$ , then $f(x)-f(y)\le x_i-y_i\le\|x-y\|_\infty\le\|x-y\|_2$ . Swap the roles of $x$ and $y$ for the other direction.
What does Gaussian concentration give?

$\mathbb P(|M-\mathbb E M|\ge t)\le2e^{-t^2/2}$ for every $n$ . The maximum of a million Gaussians grows like $\sqrt{2\ln n}$ , but it fluctuates by $O(1)$ regardless of $n$ . (Its true fluctuations are even smaller, but the theorem needs no work to give $O(1)$ .) Independence was never used in step 3; only the Lipschitz property was.
The same reasoning applies to $f(x)=\|Px-Py\|$ as a function of the Gaussian entries of $P$ . Compute its Lipschitz constant and explain why JL needs $k\gtrsim\log N/\varepsilon^2$ .

With $u=x-y$ a unit vector and $P=G/\sqrt k$ , $\|Pu\|=\|Gu\|/\sqrt k$ , and $G\mapsto\|Gu\|$ is 1-Lipschitz in the Frobenius norm of $G$ . So $\|Pu\|$ deviates from its mean (which is close to 1) by more than $\varepsilon$ with probability $\le2e^{-k\varepsilon^2/2}$ , roughly. For all $\binom N2$ pairs to succeed we need $N^2e^{-k\varepsilon^2/2}\ll1$ , i.e. $k\gtrsim4\ln N/\varepsilon^2$ .

Check your understanding

In the Johnson–Lindenstrauss lemma, what does the target dimension $k$ depend on?

Only on the number of points $N$ and the accuracy $\varepsilon$
On the ambient dimension $n$ The proof handles one difference vector at a time, and the law of $\|Pu\|/\|u\|$ is the same in every dimension.
On how the points are arrangedThe projection is chosen without looking at the data. Switch data sets in the explorer.
Only on $\varepsilon$ More points mean more pairs that could fail; the union bound charges $\log N$ .

k\approx C\varepsilon^{-2}\log N

. A million points can be embedded in a few thousand dimensions with 10% distortion, whether they started in

\R^{10^4}

or

\R^{10^9}

.

$X\sim N(0,I_n)$ and $f$ is 1-Lipschitz. Which statement is guaranteed for every $n$ ?

$f(X)$ stays within $O(1)$ of $\mathbb E f(X)$ with high probability.
$f(X)$ is approximately Gaussian.Concentration controls the size of fluctuations, not their shape. Think of $f(x)=|x_1|$ .
$\mathbb E f(X)$ is bounded independently of $n$ . $f(x)=\|x\|_2$ is 1-Lipschitz and $\mathbb E\|X\|\approx\sqrt n$ .
$\operatorname{Var} f(X)=1$ .The variance is at most of order 1 (in fact at most 1), but it can be much smaller, e.g. 0 for a constant $f$ .

The tail bound

2e^{-t^2/2}

does not depend on

n

at all, while

\mathbb E f(X)

can grow with

n

. So in relative terms, functions like

\|X\|

become nearly deterministic.

Fix the target dimension $k$ and add more and more points. How does the worst distortion over all pairs typically grow with $N$ ?

Like $\sqrt{\log N}$
It stays the same.Each new pair is another chance for an unlucky ratio.
Like $\sqrt N$ That would follow from Chebyshev-type tails. The per-pair tail is Gaussian.
Like $N^2$ The number of pairs grows like $N^2$ , but the distortion only like the square root of its logarithm.

The worst of

M\approx N^2/2

roughly Gaussian deviations of size

1/\sqrt{2k}

is about

\sqrt{2\ln M}/\sqrt{2k}\approx\sqrt{2\ln N/k}

. Slide

N

in the explorer: going from 10 to 150 points (fifteen times as many) raises the curve by less than half.

Practice

Sizing a projectionUnion bound arithmetic

Suppose that for each fixed difference vector, a random projection to $k$ dimensions distorts its length by more than $\varepsilon$ with probability at most $2e^{-k\varepsilon^2/8}$ . How large should $k$ be so that $N=10^4$ points keep all pairwise distances within 20%, with failure probability at most 1%?

Solution

There are fewer than $N^2/2$ pairs, so the failure probability is below $N^2e^{-k\varepsilon^2/8}$ . Require $N^2e^{-k\varepsilon^2/8}\le0.01$ : $k\ge8\ln(100N^2)/\varepsilon^2=8\ln(10^{10})/0.04\approx4605$ . The original dimension never entered.

The norm of a Gaussian imageLipschitz constant of x ↦ ‖Ax‖

Let $A$ be a fixed $m\times n$ matrix and $g\sim N(0,I_n)$ . Show that $\|Ag\|_2$ fluctuates around its mean by $O(\|A\|)$ , while $\mathbb E\|Ag\|_2\le\|A\|_F$ . When is the fluctuation small compared with the mean?

Hint

$|\|Ax\|-\|Ay\||\le\|A(x-y)\|$ . For the mean, use Jensen and $\mathbb E\|Ag\|^2=\|A\|_F^2$ .

Solution

$x\mapsto\|Ax\|$ is $\|A\|$ -Lipschitz, so $\mathbb P(|\|Ag\|-\mathbb E\|Ag\||\ge t)\le2e^{-t^2/2\|A\|^2}$ . Also $(\mathbb E\|Ag\|)^2\le\mathbb E\|Ag\|^2=\|A\|_F^2$ , and since the variance is $O(\|A\|^2)$ , $\mathbb E\|Ag\|\ge\|A\|_F-C\|A\|$ . The fluctuation is small relative to the mean when $\|A\|_F/\|A\|$ is large, i.e. when the stable rank $\|A\|_F^2/\|A\|^2$ is large.

More practice: Vershynin, Exercises 5.9 and 5.14.

SimulationVershynin, Ch. 6: Quadratic Forms, Symmetrization and Contraction

Quadratic forms and symmetrization

A quadratic form $X^{\mathsf T}AX$ of independent variables is a sum of dependent terms $a_{ij}X_iX_j$ . It still concentrates: its tail is Gaussian at scale $\|A\|_F$ and exponential at scale $\|A\|$ , and the ratio of the two decides which one you see.

The idea

Decoupling. Let

A

have zero diagonal,

X

have independent mean-zero coordinates, and

X'

be an independent copy of

X

. For every convex

F

,

\mathbb E\,F\Big(\sum_{i\ne j}a_{ij}X_iX_j\Big)\le\mathbb E\,F\Big(4\sum_{i,j}a_{ij}X_iX'_j\Big).

The right side is linear in $X$ once $X'$ is fixed, so tools for sums apply.

Hanson–Wright. If

X

has independent mean-zero coordinates with

\|X_i\|_{\psi_2}\le K

, then for every

n\times n

matrix

A

and

t\ge0

,

\mathbb P\big(|X^{\mathsf T}AX-\mathbb E X^{\mathsf T}AX|\ge t\big)\le2\exp\Big(-c\min\Big(\frac{t^2}{K^4\|A\|_F^2},\ \frac{t}{K^2\|A\|}\Big)\Big).

Symmetrization. For independent mean-zero random vectors

X_i

in a normed space and independent random signs

\varepsilon_i

,

\tfrac12\,\mathbb E\Big\|\sum\varepsilon_iX_i\Big\|\le\mathbb E\Big\|\sum X_i\Big\|\le2\,\mathbb E\Big\|\sum\varepsilon_iX_i\Big\|.

Contraction. For fixed vectors

x_i

and real

a_i

,

\ \mathbb E\|\sum a_i\varepsilon_ix_i\|\le\|a\|_\infty\,\mathbb E\|\sum\varepsilon_ix_i\|

. Together, these let you replace arbitrary summands by sign-weighted ones and then strip off bounded coefficients. One application in the chapter: completing a low-rank matrix from a few random entries.

Explore

Stable rank r Deviation t

20,000 draws of

X^{\mathsf T}AX

,

X\sim N(0,I_{200})

, standardised.

N(0,1)

exact tail simulated Laurent–Massart bound Gaussian guess

Worked example

Let $X\sim N(0,I_2)$ and $A=\begin{pmatrix}2&1\\1&0\end{pmatrix}$ , so $X^{\mathsf T}AX=2X_1^2+2X_1X_2$ . Find its mean and variance, and the two scales in Hanson–Wright.

Compute $\mathbb E X^{\mathsf T}AX$ for any isotropic $X$ .

$\mathbb E X^{\mathsf T}AX=\mathbb E\operatorname{tr}(AXX^{\mathsf T})=\operatorname{tr}(A\,\mathbb E XX^{\mathsf T})=\operatorname{tr}A=2$ .
For Gaussian $X$ and symmetric $A$ , show $\operatorname{Var}X^{\mathsf T}AX=2\|A\|_F^2$ .

Write $A=U\Lambda U^{\mathsf T}$ . Then $Z=U^{\mathsf T}X\sim N(0,I)$ by rotation invariance, and $X^{\mathsf T}AX=\sum\lambda_iZ_i^2$ , a sum of independent terms with $\operatorname{Var}(\lambda_iZ_i^2)=2\lambda_i^2$ . So the variance is $2\sum\lambda_i^2=2\|A\|_F^2$ .
Apply it to this $A$ , and check directly.

The eigenvalues are $1\pm\sqrt2$ , so $\|A\|_F^2=(1+\sqrt2)^2+(1-\sqrt2)^2=6$ (also $4+1+1+0$ ), and the variance is 12. Directly: $\operatorname{Var}(2X_1^2)=8$ , $\operatorname{Var}(2X_1X_2)=4$ , and $\operatorname{Cov}(X_1^2,X_1X_2)=\mathbb E X_1^3\,\mathbb E X_2=0$ . Total 12.
What are $\|A\|_F$ and $\|A\|$ , and where does the tail switch from Gaussian to exponential?

$\|A\|_F=\sqrt6\approx2.45$ and $\|A\|=1+\sqrt2\approx2.41$ . The two terms in the minimum cross at $t\approx\|A\|_F^2/\|A\|\approx2.49$ , less than one standard deviation ( $\sqrt{12}\approx3.46$ ). So this form has essentially no Gaussian regime: it is dominated by the single large eigenvalue, like $\lambda_1Z_1^2$ . In the explorer this is stable rank $r\approx1$ .

Check your understanding

$X$ has independent $\pm1$ coordinates and $A=I_n$ . Then $X^{\mathsf T}AX=n$ always, but Hanson–Wright allows fluctuations of order $\|A\|_F=\sqrt n$ . Is something wrong?

No: Hanson–Wright is an upper bound, and here the diagonal terms $X_i^2=1$ don't fluctuate at all.
Yes: Hanson–Wright requires Gaussian coordinates.It holds for any independent mean-zero subgaussian coordinates, signs included.
Yes: the fluctuation must be exactly of order $\|A\|_F$ .The theorem bounds the tail from above. Nothing forces the form to fluctuate that much.

For Gaussian

X

,

\|X\|^2

does fluctuate by

\sqrt{2n}

, so the bound is sharp in general. For signs the diagonal part is deterministic and only off-diagonal entries contribute: the variance is

2\sum_{i\ne j}a_{ij}^2

(for symmetric

A

).

$X\sim N(0,I_n)$ with $n$ large. For which $A$ is $X^{\mathsf T}AX$ , after standardising, closest to a normal distribution?

$A=I_n$
$A=uu^{\mathsf T}$ with $\|u\|=1$ Then $X^{\mathsf T}AX=\langle u,X\rangle^2$ is a single $\chi^2_1$ : stable rank 1, the most skewed case.
$A=\operatorname{diag}(n,1,1,\dots,1)$ One eigenvalue dominates: $\|A\|_F^2\approx n^2=\|A\|^2$ , so the stable rank is about 1.

The shape is governed by the stable rank

\|A\|_F^2/\|A\|^2

. For

I_n

it is

n

, so

X^{\mathsf T}AX=\chi^2_n

is a sum of many comparable independent terms and the CLT kicks in. Slide

r

in the explorer.

The symmetrization inequality $\mathbb E\|\sum X_i\|\le2\,\mathbb E\|\sum\varepsilon_iX_i\|$ requires the $X_i$ to be:

Independent with mean zero
SymmetricIf they were symmetric, $\sum X_i$ and $\sum\varepsilon_iX_i$ would have the same law. Symmetrization is how you avoid assuming that.
BoundedOnly integrability is needed.
Identically distributedThe proof treats each $X_i$ separately; no common distribution is needed.

Mean zero is essential: for

X_i\equiv1

in

\R

,

\mathbb E|\sum X_i|=N

while

\mathbb E|\sum\varepsilon_i|\approx\sqrt{2N/\pi}

. The proof subtracts an independent copy, which is harmless only when

\mathbb E X_i=0

.

Practice

Estimating a trace with random signsHutchinson's estimator

You can only access a symmetric matrix $A$ through products $x\mapsto Ax$ . Show that for $X$ with independent $\pm1$ entries, $\mathbb E X^{\mathsf T}AX=\operatorname{tr}A$ and $\operatorname{Var}X^{\mathsf T}AX=2\sum_{i\ne j}a_{ij}^2$ . Why are signs better than Gaussians here?

Solution

$X^{\mathsf T}AX=\sum_ia_{ii}+2\sum_{i<j}a_{ij}X_iX_j$ . The products $X_iX_j$ , $i<j$ , have mean 0, variance 1 and are pairwise uncorrelated, so the variance is $4\sum_{i<j}a_{ij}^2=2\sum_{i\ne j}a_{ij}^2$ . With Gaussian $X$ it is $2\|A\|_F^2$ , which also counts the diagonal. For a nearly diagonal $A$ , signs are far more accurate.

Symmetrization on the lineThe basic argument

Prove $\mathbb E|\sum X_i|\le2\,\mathbb E|\sum\varepsilon_iX_i|$ for independent mean-zero real $X_i$ .

Hint

Let $X'$ be an independent copy. Write $\sum X_i=\sum(X_i-\mathbb E X'_i)$ and use Jensen conditionally on $X$ .

Solution

More practice: Vershynin, Exercises 6.7 and 6.20.

SimulationVershynin, Ch. 7: Random Processes

Gaussian processes and Gaussian width

How big is a set in $\R^n$ ? Its Gaussian width, the expected maximum of a random linear function over it, is the answer that matters for random projections and for recovery problems. Some sets that look large, like the $\ell_1$ ball, turn out to be tiny.

The idea

Canonical Gaussian process. For

T\subseteq\R^n

and

g\sim N(0,I_n)

,

X_t=\langle g,t\rangle

. Its increments are

\big(\mathbb E(X_t-X_s)^2\big)^{1/2}=\|t-s\|_2

, so the geometry of

T

is the geometry of the process.

Gaussian width.

w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle

. It is translation invariant, unchanged by taking the convex hull, and

w(T)^2

behaves like an effective dimension: for a unit ball of a

k

-dimensional subspace,

w\approx\sqrt k

.

Sudakov–Fernique. If

(X_t)

and

(Y_t)

are mean-zero Gaussian processes with

\mathbb E(X_t-X_s)^2\le\mathbb E(Y_t-Y_s)^2

for all

t,s

, then

\mathbb E\sup X_t\le\mathbb E\sup Y_t

. Smaller increments mean a smaller supremum. This comparison gives

\mathbb E\|G\|\le\sqrt m+\sqrt n

for an

m\times n

Gaussian matrix, and Gordon's min–max version gives

\mathbb E s_n(G)\ge\sqrt m-\sqrt n

.

Sudakov's minoration.

\mathbb E\sup_{t\in T}X_t\ge c\,\varepsilon\sqrt{\log N(T,\varepsilon)}

for every

\varepsilon>0

: a set with many well-separated points has a large supremum.

Random projections of sets. If

P

is the orthogonal projection onto a random

k

-dimensional subspace of

\R^n

, then with high probability

\operatorname{diam}(PT)\lesssim w(T)/\sqrt n+\sqrt{k/n}\,\operatorname{diam}(T)

. The first term wins when

k\lesssim w(T)^2/\operatorname{diam}(T)^2

: below its effective dimension, a set shrinks to a size set by its width, not by

k

.

Explore

Set T (inside the unit ball)

Dimension

ball

\approx\sqrt n

cube

=\sqrt{2n/\pi}

5-sparse unit vectors

\ell_1

ball

\approx\sqrt{2\ln n}

Distribution of

\sup_{t\in T}\langle g,t\rangle

at the chosen dimension; the dashed line is its mean,

w(T)

.

Worked example

Compute, or bound, the Gaussian width of the cross-polytope $B_1^n=\{t:\sum|t_i|\le1\}$ , and compare it with the Euclidean ball.

Express $\sup_{t\in B_1^n}\langle g,t\rangle$ in terms of $g$ .

A linear function on a polytope is maximised at a vertex, and the vertices are $\pm e_i$ . So the sup is $\max_i|g_i|=\|g\|_\infty$ , and $w(B_1^n)=\mathbb E\|g\|_\infty$ .
Bound $\mathbb E\max_i|g_i|$ using the moment generating function.

The maximum is over the $2n$ variables $\pm g_i$ . For $\lambda>0$ , Jensen gives $e^{\lambda\mathbb E\max}\le\sum\mathbb E e^{\pm\lambda g_i}=2ne^{\lambda^2/2}$ , so $\mathbb E\max\le\frac{\ln2n}\lambda+\frac\lambda2$ . With $\lambda=\sqrt{2\ln 2n}$ : $w(B_1^n)\le\sqrt{2\ln(2n)}$ .
Put in $n=1000$ . How good is the bound?

The bound is $\sqrt{2\ln2000}\approx3.90$ . The exact value (an integral of the normal distribution function, which the explorer computes) is about 3.44. For comparison, $w(B_2^{1000})=\mathbb E\|g\|_2\approx31.6$ .
What does this mean for a random projection of $B_1^n$ ?

Its effective dimension is $w^2\approx2\ln n\approx14$ for $n=1000$ . A random projection to $k$ dimensions with $k$ well above 14 shrinks it to diameter about $\sqrt{k/n}$ times the original, and for smaller $k$ to about $w/\sqrt n\approx0.11$ . The ball, by contrast, has effective dimension $n$ . This gap is what makes sparse recovery possible in Chapter 9.

Check your understanding

$T\subseteq\R^n$ and $A$ is an $n\times n$ matrix with $\|A\|\le1$ . How do $w(AT)$ and $w(T)$ compare?

$w(AT)\le w(T)$
$w(AT)\ge w(T)$ A contraction can only shrink the increments $\|At-As\|$ .
They are equal.Take $A=0$ : then $w(AT)=0$ .
No general relation.Compare the increments of the two processes and use Sudakov–Fernique.

\langle g,At\rangle

is a Gaussian process with increments

\|A(t-s)\|\le\|t-s\|

, smaller than those of

\langle g,t\rangle

. Sudakov–Fernique gives

\mathbb E\sup_t\langle g,At\rangle\le\mathbb E\sup_t\langle g,t\rangle

.

How does the Gaussian width of $T$ compare with that of its convex hull?

They are equal.
$w(\operatorname{conv}T)$ can be much larger.For a fixed $g$ , a linear function's sup over the convex hull is attained at a point of $T$ .
$w(\operatorname{conv}T)$ is larger by a factor $\sqrt{\log|T|}$ for finite $T$ .That factor appears when you compare a finite set's width with its diameter, not with its hull.

\sup_{\operatorname{conv}T}\langle g,\cdot\rangle=\sup_T\langle g,\cdot\rangle

for every

g

. That is why the 2n vertices

\pm e_i

and the whole

\ell_1

ball have the same width.

$T$ is the unit Euclidean ball of a $k$ -dimensional subspace sitting in $\R^n$ , $k\ll n$ . What is $w(T)$ approximately?

$\sqrt k$
$\sqrt n$ Only the component of $g$ inside the subspace matters.
1That is the radius. The width also counts how many directions the set extends in.
$k$ The width is the expected length of a $k$ -dimensional Gaussian vector, not its squared length.

\sup_{t\in T}\langle g,t\rangle=\|P_Eg\|_2

, the length of the projection of

g

onto the subspace

E

, which is a standard Gaussian in

\R^k

. Its expected length is about

\sqrt k

, so

w(T)^2\approx k

: the effective dimension equals the true dimension.

Practice

Width of the cubeAn exact computation

Compute $w([-1,1]^n)$ exactly and compare it with the width of the Euclidean ball of the same diameter $2\sqrt n$ .

Solution

$\sup_{t\in[-1,1]^n}\langle g,t\rangle=\sum|g_i|$ , so $w=n\,\mathbb E|g_1|=n\sqrt{2/\pi}\approx0.80\,n$ . The ball of radius $\sqrt n$ has width $\sqrt n\,\mathbb E\|g\|\approx n$ . So the cube is almost as wide as its circumscribed ball: its corners stick out in nearly every direction.

Linear images and widthUsing Sudakov–Fernique

Show $w(AT)\le\|A\|\,w(T)$ for any $m\times n$ matrix $A$ and bounded $T\subseteq\R^n$ . Deduce that if $T\subseteq\R^n$ lies in the unit ball then $w(T)\le\sqrt n$ .

Solution

Compare $Y_t=\langle h,At\rangle$ ( $h\sim N(0,I_m)$ ) with $X_t=\|A\|\langle g,t\rangle$ : $\mathbb E(Y_t-Y_s)^2=\|A(t-s)\|^2\le\|A\|^2\|t-s\|^2=\mathbb E(X_t-X_s)^2$ , so Sudakov–Fernique gives the claim. For the second part, $w(T)\le w(B_2^n)=\mathbb E\|g\|_2\le(\mathbb E\|g\|_2^2)^{1/2}=\sqrt n$ .

More practice: Vershynin, Exercises 7.17 and 7.22.

Draw it yourselfVershynin, Ch. 8: Chaining

Chaining and VC dimension

To bound the supremum of a process, chaining runs a union bound at every scale and adds up the costs. For classes of sets the relevant size is combinatorial: how many points the class can label in every possible way. Place points below and try to beat the VC dimension.

The idea

Dudley's inequality. If

(X_t)_{t\in T}

is mean-zero with subgaussian increments,

\|X_t-X_s\|_{\psi_2}\le K\,d(t,s)

, then

\mathbb E\sup_{t\in T}X_t\le CK\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon.

Chaining: approximate each $t$ by points $\pi_k(t)$ of a $2^{-k}$ -net, write $X_t-X_{t_0}=\sum_k(X_{\pi_k(t)}-X_{\pi_{k-1}(t)})$ , and union-bound each level separately. A link at level $k$ has length about $2^{-k}$ , and there are about $N(T,2^{-k})^2$ of them; summing $2^{-k}\sqrt{\log N(T,2^{-k})}$ over $k$ gives the integral.

VC dimension. A class

\mathcal F

of subsets shatters a finite set

\Lambda

if every subset of

\Lambda

equals

F\cap\Lambda

for some

F\in\mathcal F

. The VC dimension is the largest size of a shattered set.

Sauer–Shelah. If

\operatorname{vc}(\mathcal F)=d

, then on any

k

points

\mathcal F

cuts out at most

\sum_{i=0}^d\binom ki\le(ek/d)^d

subsets: polynomially many, instead of

2^k

.

Uniform law of large numbers. For a class of Boolean functions of VC dimension

d

and i.i.d. samples

X_1,\dots,X_N

,

\mathbb E\sup_{f\in\mathcal F}\Big|\frac1N\sum_{i=1}^Nf(X_i)-\mathbb E f(X)\Big|\le C\sqrt{\frac dN}.

The proof symmetrizes, bounds covering numbers of $\mathcal F$ in terms of $d$ , and applies Dudley. In learning theory this says empirical risk minimisation over such a class has excess risk of order $\sqrt{d/N}$ .

Explore

Click to add a point (up to 6), drag to move it. Filled points are labelled "in". a set from the class that cuts out exactly the filled points

Class of sets

Start from

All labellings (click one; red ones are impossible)

Worked example

Find the VC dimension of the class of closed intervals $[a,b]\subseteq\R$ , and count exactly how many subsets it cuts out of $k$ points.

Show that two points $x_1<x_2$ are shattered.

$\varnothing$ : an interval far away. $\{x_1\}$ , $\{x_2\}$ : tiny intervals around each. $\{x_1,x_2\}$ : $[x_1,x_2]$ . All four subsets are cut out.
Why can no three points $x_1<x_2<x_3$ be shattered?

An interval containing $x_1$ and $x_3$ contains everything between them, including $x_2$ . So $\{x_1,x_3\}$ is never cut out. Hence $\operatorname{vc}=2$ .
How many subsets of $k$ points on the line do intervals cut out?

Exactly the empty set and the runs of consecutive points: $1+\binom{k+1}2=1+k+\binom k2$ . (A run is determined by its first and last point, possibly equal.)
Compare with the Sauer–Shelah bound for $d=2$ .

$\sum_{i=0}^2\binom ki=1+k+\binom k2$ : exactly equal. So the lemma cannot be improved in general. For $k=10$ , intervals realise 56 of the 1024 subsets.

Check your understanding

What is the VC dimension of half-planes in $\R^2$ ?

2Three points in a triangle are shattered: check it in the explorer.
3
4Try four points. In convex position, the two diagonals can't be separated; otherwise one point is inside the triangle of the others.
InfiniteHalf-planes are described by 3 parameters, and indeed no 4 points can be shattered.

Any three non-collinear points are shattered. For four points, either they are in convex position, and the labelling "opposite corners in" fails, or one lies in the triangle of the other three, and "the three outer points in, the inner one out" fails, since half-planes are convex.

A class has VC dimension 3. At most how many different subsets can it cut out of 10 points?

176
1024That is every subset, which would mean 10 points are shattered.
120That is $\binom{10}3$ alone. Add the subsets of size 0, 1 and 2 in the Sauer–Shelah sum.
$10^3=1000$ The $(ek/d)^d$ style bound is of this order, but the exact Sauer–Shelah sum is much smaller here.

\binom{10}0+\binom{10}1+\binom{10}2+\binom{10}3=1+10+45+120=176

. Half-planes on 10 points in general position realise even fewer.

Empirical risk minimisation over a class of VC dimension $d$ , from $N$ samples. With no further assumptions, how does the guaranteed excess risk scale?

$\sqrt{d/N}$
$d/N$ That faster rate needs extra assumptions (for example, a target in the class with no noise).
$\sqrt{\log N/N}$ , independent of $d$ The complexity of the class must enter: with infinite VC dimension, no rate is possible.
$2^d/N$ Sauer–Shelah replaces the exponential count by a polynomial, so only $d$ appears, not $2^d$ .

The excess risk is controlled by the uniform deviation

\sup_f|\frac1N\sum f(X_i)-\mathbb E f|

, which is

\lesssim\sqrt{d/N}

by the uniform law of large numbers. To halve the error you need four times the data.

Practice

Discs centred at the originA one-parameter class

Find the VC dimension of the class $\{\{x\in\R^2:\|x\|\le r\}: r\ge0\}$ .

Solution

One point $x\ne0$ is shattered (take $r<\|x\|$ or $r\ge\|x\|$ ). For two points with $\|x_1\|\le\|x_2\|$ , any disc containing $x_2$ contains $x_1$ , so $\{x_2\}$ is never cut out. The VC dimension is 1. Notice the class is a nested chain of sets; any such chain has VC dimension at most 1.

Finite classesA simple bound

Show that a finite class $\mathcal F$ has $\operatorname{vc}(\mathcal F)\le\log_2|\mathcal F|$ . Give a class with $|\mathcal F|=2^d$ and VC dimension exactly $d$ .

Solution

Shattering $k$ points needs $2^k$ different sets, so $2^k\le|\mathcal F|$ . For equality, take a $d$ -point set $\Lambda$ and let $\mathcal F$ be all its subsets.

More practice: Vershynin, Exercises 8.12 and 8.14.

SimulationVershynin, Ch. 9: Deviations of Random Matrices on Sets

Random matrices on sets and sparse recovery

A random $m\times n$ matrix with $m<n$ has a big kernel, so it cannot be injective. But it behaves like a scaled isometry on any set of small Gaussian width, and that is enough to recover an $s$ -sparse vector exactly from about $s\log(n/s)$ random measurements.

The idea

Matrix deviation inequality. Let

A

be

m\times n

with independent, mean-zero, isotropic, subgaussian rows,

\|A_i\|_{\psi_2}\le K

. For every bounded

T\subseteq\R^n

,

\mathbb E\sup_{x\in T}\Big|\,\|Ax\|_2-\sqrt m\,\|x\|_2\Big|\le CK^2\gamma(T),\qquad \gamma(T)=\mathbb E\sup_{x\in T}|\langle g,x\rangle|.

Taking $T$ to be the sphere gives the singular value bounds of Chapter 4; taking normalised differences of $N$ points gives Johnson–Lindenstrauss.

$M^*$ bound and escape.

\ker A

is a random subspace of codimension

m

. It meets

T

in a set of diameter

\mathbb E\operatorname{diam}(T\cap\ker A)\le CK^2w(T)/\sqrt m

. And if

T\subseteq S^{n-1}

and

m\ge CK^4w(T)^2

, then

T\cap\ker A=\varnothing

with high probability: the kernel escapes through the mesh.

Exact sparse recovery. Let

x_0

have at most

s

nonzero entries and

y=Ax_0

. If

m\ge CK^4s\log n

, then with high probability

x_0

is the unique solution of

\min\|x\|_1\quad\text{subject to}\quad Ax=y.

Why: $x_0+h$ is a competing solution exactly when $h\in\ker A$ and $\|x_0+h\|_1\le\|x_0\|_1$ , i.e. $h$ lies in the descent cone $D$ of the $\ell_1$ norm at $x_0$ . The cone $D\cap S^{n-1}$ has $w^2\lesssim s\log(n/s)$ , so by the escape theorem the kernel misses it.

Explore

Measurements m Sparsity s

n=40

unknowns,

A

Gaussian. hidden

x_0

\ell_1

solution minimum

\ell_2

-norm solution

Success rate of

\ell_1

recovery; click a cell to try it. success failure

m=\delta(s)

Worked example

The smallest case: $n=2$ , one measurement $y=a_1x_1+a_2x_2$ , and the 1-sparse vector $x_0=(1,0)$ . When does $\ell_1$ minimisation find $x_0$ ?

Take $a=(2,1)$ , so $y=2$ . Find the minimum $\ell_2$ -norm solution.

It is the point of the line $2x_1+x_2=2$ closest to the origin, $x=a\,y/\|a\|^2=(0.8,0.4)$ . Not sparse, and not $x_0$ .
Now minimise $|x_1|+|x_2|$ on the same line.

On the line $x_2=2-2x_1$ , so minimise $|x_1|+|2-2x_1|$ . This is piecewise linear with value 2 at $x_1=0$ and 1 at $x_1=1$ , and grows outside $[0,1]$ . The minimum is at $x=(1,0)=x_0$ : recovered. Geometrically, the smallest $\ell_1$ diamond that touches the line touches it at a corner.
Repeat with $a=(1,2)$ , so $y=1$ .

On $x_1+2x_2=1$ , minimise $|x_1|+|(1-x_1)/2|$ : value 1 at $x_1=1$ but $1/2$ at $x_1=0$ . The minimiser is $(0,\tfrac12)$ : sparse, but the wrong vector.
Explain both outcomes with the kernel and the descent cone $D=\{h:\|x_0+h\|_1\le\|x_0\|_1\}$ .

Near $x_0=(1,0)$ , $\|x_0+h\|_1=1+h_1+|h_2|$ , so $D=\{h:h_1\le-|h_2|\}$ , a cone of half-angle 45° around $-e_1$ . For $a=(2,1)$ the kernel is spanned by $(1,-2)$ , which is steeper than 45° and misses $D\setminus\{0\}$ : success. For $a=(1,2)$ it is spanned by $(2,-1)$ , and $-(2,-1)\in D$ : failure. In high dimension the descent cone is a small fraction of directions, and the escape theorem says a random kernel misses it once $m\gtrsim w(D\cap S^{n-1})^2$ .

Check your understanding

$E$ is a random subspace of $\R^n$ of codimension $m$ . By the $M^*$ bound, the Euclidean diameter of $B_1^n\cap E$ is at most about:

$\sqrt{\log n/m}$
1 $B_1^n$ has points of length 1 (the vertices), but a random subspace avoids those directions.
$\sqrt{n/m}$ That is what the bound gives for the Euclidean ball, whose width is about $\sqrt n$ . Use $w(B_1^n)$ instead.
0 $E$ is a subspace of dimension $n-m\ge1$ , so $B_1^n\cap E$ contains nonzero points.

\operatorname{diam}\lesssim w(B_1^n)/\sqrt m\approx\sqrt{2\ln n}/\sqrt m

(meaningful once this is below 2, the diameter of

B_1^n

). Points of a random subspace have small

\ell_2

norm relative to their

\ell_1

norm, i.e. they are spread out, never sparse. That is the reason

\ell_1

minimisation picks out sparse vectors.

How many Gaussian measurements suffice for $\ell_1$ minimisation to recover a given $s$ -sparse $x_0\in\R^n$ with high probability?

On the order of $s\log n$
On the order of $n$ $n$ measurements would let you invert $A$ , sparse or not. Sparsity is what saves you.
Exactly $s$ Even knowing the support you need $s$ ; not knowing it costs a logarithmic factor for $\ell_1$ .
On the order of $s^2$ Some deterministic constructions need that many; random matrices do much better.

The squared width of the descent cone is

\lesssim s\log(n/s)

, and the escape theorem needs

m

of that order. In the phase diagram the dashed boundary grows roughly linearly in

s

, with a slope set by the logarithm.

In the matrix deviation inequality, take $T=S^{n-1}$ , for which $\gamma(T)\approx\sqrt n$ . What does it say?

All singular values of $A$ lie in $\sqrt m\pm C\sqrt n$ , on average.
$\|Ax\|_2=\sqrt m$ for every unit vector $x$ .The inequality allows a deviation of order $\gamma(T)$ , not zero.
$A$ is invertible.If $m<n$ , $A$ has a kernel, and the bound $\sqrt m-C\sqrt n$ becomes negative, so it says nothing about $s_n$ .
$\|A\|\le C\sqrt n$ .The scale $\sqrt m$ of $\|Ax\|$ must appear; only the deviation is of order $\sqrt n$ .

\sup_{x\in S^{n-1}}|\|Ax\|-\sqrt m|\lesssim\sqrt n

is the two-sided bound of Chapter 4. Other sets

T

give other theorems: that is the point of stating it for every

T

.

Practice

ℓ₁ minimisation is a linear programWhat the explorer solves

Show that $\min\|x\|_1$ subject to $Ax=y$ has the same optimal value as the linear program $\min\sum_i(u_i+v_i)$ subject to $A(u-v)=y$ , $u,v\ge0$ , and that at any optimum $u_iv_i=0$ for each $i$ (so $x=u-v$ is optimal for the original problem).

Solution

Given feasible $x$ , $u=\max(x,0)$ , $v=\max(-x,0)$ is feasible with $\sum(u_i+v_i)=\|x\|_1$ . Conversely, feasible $(u,v)$ gives a feasible $x=u-v$ with $\|x\|_1\le\sum(u_i+v_i)$ . So the optimal values agree. If $u_i,v_i>0$ at an optimum, lowering both by $\min(u_i,v_i)$ keeps $u-v$ and feasibility but lowers the objective, a contradiction.

Too few measurementsA lower bound for any method

Show that if $m<2s$ , no method at all can recover every $s$ -sparse $x\in\R^n$ (with $n\ge2s$ ) from $Ax$ .

Hint

Look for two different $s$ -sparse vectors with the same image.

Solution

Any $2s$ columns of $A$ are $2s$ vectors in $\R^m$ with $m<2s$ , so they are linearly dependent: there is $h\ne0$ supported on those $2s$ coordinates with $Ah=0$ . Split $h=u-v$ with $u,v$ each supported on $s$ of the coordinates. Then $u\ne v$ are both $s$ -sparse and $Au=Av$ . So $m\ge2s$ is necessary, and the $\log$ factor in the theorem is the price of a computationally easy method.

More practice: Vershynin, Exercises 9.30 and 9.32.