Spectral Norm of Random Matrices

The variational reduction

LemmaBilinear variational form of the spectral norm

For any $A \in \R^{n\times p}$,

$$\norm{A} = \max_{u \in S^{n-1}}\ \max_{v\in S^{p-1}}\ \ip{Au}{v} = \max_{u,v} u^\top A^\top v .$$

Moreover, if $\Ncal \subseteq S^{p-1}$ and $\mathcal{M}\subseteq S^{n-1}$ are $\eps$-nets with $\eps<1/2$, then

$$\norm{A} \le \frac{1}{1-2\eps}\max_{v\in\mathcal{M}}\max_{u\in\Ncal} \ip{Au}{v}.$$

ProofReveal

The main bound

TheoremSpectral norm of a matrix with sub-Gaussian entries

Let $A\in\R^{n\times p}$ have independent, mean-zero entries with $\norm{A_{ij}}_{\psi_2}\le K$. Then there is an absolute constant $C$ such that for every $t \ge 0$,

$$\P\Big(\norm{A} \ge CK\big(\sqrt n + \sqrt p + t\big)\Big) \le 2e^{-t^2}.$$

In particular $\E\norm{A} \le CK(\sqrt n + \sqrt p)$.

ProofReveal

Sharp constants: the Bai–Yin law

TheoremBai–Yin law

Let $A \in \R^{n\times p}$ have i.i.d. entries with mean $0$, variance $1$ and finite fourth moment, and let $n,p \to \infty$ with $p/n \to \lambda \in (0,1]$. Then almost surely

$$\sigma_{\max}(A) = \sqrt n + \sqrt p + o(\sqrt n), \qquad \sigma_{\min}(A) = \sqrt n - \sqrt p + o(\sqrt n) .$$

Quoted from the references. The point of comparison with the theorem above is instructive: the net argument gives the right order with an unspecified constant $C$, valid for every finite $n,p$ and with an exponential tail. Bai–Yin gives the exact constant $1$ in front of each square root, but only asymptotically and only almost surely. Both are useful, for different purposes — and the finite-sample statement is the one a statistician needs.

Run it: Marchenko–Pastur lawEigenvalues of a sample covariance matrix against the Marchenko–Pastur density for aspect ratio λ = p/n.

Wigner matrices and the semicircle law

DefinitionWigner matrix

A Wigner matrix is a symmetric $W \in \R^{d\times d}$ whose entries $\{W_{ij}\}_{i\le j}$ are independent with mean $0$ and variance $1$ (the diagonal may have a different variance). The normalisation of interest is $W/\sqrt d$, which keeps the spectrum $O(1)$.

TheoremWigner semicircle law

Let $W_d$ be Wigner matrices with uniformly bounded fourth moments and let $\mu_d = \frac1d\sum_{i=1}^d \delta_{\lambda_i(W_d/\sqrt d)}$ be the empirical spectral distribution. Then $\mu_d$ converges weakly, almost surely, to the semicircle law with density

$$\rho_{sc}(x) = \frac{1}{2\pi}\sqrt{4-x^2}\,\one\{|x|\le2\}.$$

The standard proofs are the moment method — show $\frac1d\E\tr\big((W/\sqrt d)^{2k}\big) \to \frac{1}{k+1}\binom{2k}{k}$, the Catalan numbers, which are the moments of the semicircle — and the Stieltjes transform method, which derives the self-consistent equation $s(z) = \frac{1}{-z - s(z)}$ for the limiting transform. Both are given in the references; neither is short, and neither is reproduced here.

Matrix concentration

The net argument above is specific to the operator norm of a matrix with independent entries. A more flexible tool handles sums of dependent-within-summand random matrices.

TheoremMatrix Bernstein inequality

Let $X_1,\dots,X_n$ be independent, mean-zero, symmetric random matrices in $\R^{d\times d}$ with $\norm{X_i}\le M$ almost surely, and set $\sigma^2 = \norm{\sum_i \E X_i^2}$. Then for all $t\ge0$,

$$\P\left(\norm{\sum_{i=1}^n X_i} \ge t\right) \le 2d\exp\left(-\frac{t^2}{2\sigma^2 + \tfrac23 Mt}\right).$$

Quoted from Tropp's survey. Compare with the scalar Bernstein inequality: the bound is identical except for the factor $2d$ in front, which is the price of passing from a number to a $d\times d$ matrix. Since it appears inside a logarithm after inversion, the practical cost is an extra $\log d$ in every sample-complexity statement — which is exactly the $\log d$ that appears in covariance-estimation rates on the next section.

Problems

The net argument for the spectral normProof · Graduate · 3 hours Frobenius versus operator norm for random matricesNumerical · Intermediate · 30 min Catalan numbers are the moments of the semicircle lawProof · Advanced · 1 hour Simulate Wigner and Wishart spectraCoding · Intermediate · 1 hour