Matrix Concentration

Let $X_1, \ldots, X_n$ be independent, centered, symmetric random matrices in $\mathbb{R}^{d \times d}$ with $\|X_i\|_{\text{op}} \leq R$ almost surely. Then:

$\mathbb{P}\!\Bigl(\Bigl\|\sum_{i=1}^n X_i\Bigr\|_{\text{op}} \geq t\Bigr) \leq 2d \cdot \exp\!\Bigl(-\frac{t^2/2}{\sigma^2 + Rt/3}\Bigr)$

Equivalently, with probability at least $1 - \delta$:

$\Bigl\|\sum_{i=1}^n X_i\Bigr\|_{\text{op}} \leq \sigma\sqrt{2\log(2d/\delta)} + \frac{2R}{3}\log(2d/\delta)$

This is the matrix version of the scalar Bernstein inequality. The bound has two regimes:

• Sub-Gaussian regime ($t \lesssim \sigma^2/R$): the bound is $\approx 2d \exp(-t^2/(2\sigma^2))$, dominated by variance. This gives the $\sigma\sqrt{\log d}$ term.

• Sub-exponential regime ($t \gtrsim \sigma^2/R$): the bound is $\approx 2d \exp(-t/(2R/3))$, dominated by the maximum norm. This gives the $R\log d$ term.

The factor $2d$ in front (from a union bound over $d$ eigenvalues) explains the $\log d$ in the final bound. The intrinsic dimension version replaces $\log d$ with $\log(\mathrm{intdim})$. which can be much smaller.

Matrix Bernstein is the single most-used matrix concentration inequality. Applications include:

• Covariance estimation: bounding $\|\hat{\Sigma} - \Sigma\|_{\text{op}}$
• Random projections: proving Johnson-Lindenstrauss via random matrices
• Spectral clustering: controlling perturbations of graph Laplacians
• Matrix completion: bounding the error of low-rank recovery

Any time you need operator-norm control of a matrix sum, this is your tool.

The $\log d$ factor can be loose. If the random matrices have low effective rank (small intrinsic dimension), the intrinsic-dimension version gives $\log(\mathrm{intdim})$ instead of $\log d$, which can be dramatically better when $d$ is large but the variance is concentrated in a few directions.

Let $X_1, \ldots, X_n$ be independent, centered, symmetric random matrices with $X_i^2 \preceq A_i^2$ almost surely (in the Loewner order). Define $\sigma^2 = \|\sum_i A_i^2\|_{\text{op}}$. Then:

$\mathbb{P}\!\Bigl(\Bigl\|\sum_{i=1}^n X_i\Bigr\|_{\text{op}} \geq t\Bigr) \leq 2d \cdot \exp\!\Bigl(-\frac{t^2}{8\sigma^2}\Bigr)$

This is the matrix analog of Hoeffding's inequality. The condition $X_i^2 \preceq A_i^2$ is the matrix version of "bounded." The bound is purely sub-Gaussian (no sub-exponential tail) because boundedness prevents large deviations. The factor of $8$ (rather than $2$) reflects the looser constant in the matrix setting.

Matrix Hoeffding is simpler than Matrix Bernstein and often sufficient for applications where the summands are naturally bounded (e.g., adjacency matrices of random graphs, indicator matrices).

Looser than Matrix Bernstein when the variance $\sigma^2$ is much smaller than the worst-case bound $R^2$. Matrix Bernstein gives a tighter bound in the sub-Gaussian regime.

For symmetric matrices $A, B \in \mathbb{R}^{d \times d}$ with eigenvalues $\lambda_1(A) \geq \cdots \geq \lambda_d(A)$ and similarly for $B$:

$|\lambda_i(A+B) - \lambda_i(A)| \leq \|B\|_{\text{op}} \quad \text{for all } i$

Adding a perturbation $B$ to a matrix $A$ shifts each eigenvalue by at most $\|B\|_{\text{op}}$. This is the eigenvalue analog of the triangle inequality. Combined with matrix concentration (which bounds $\|B\|_{\text{op}}$ when $B = \hat{A} - A$), it gives concentration of individual eigenvalues.

Weyl + Matrix Bernstein gives: if $\hat{\Sigma} = \frac{1}{n}\sum_i x_i x_i^\top$ and $\|\hat{\Sigma} - \Sigma\|_{\text{op}} \leq \epsilon$, then every eigenvalue of $\hat{\Sigma}$ is within $\epsilon$ of the corresponding eigenvalue of $\Sigma$. This is fundamental for PCA consistency.

Weyl controls eigenvalue locations but says nothing about eigenvector directions. For eigenvectors, you need Davis-Kahan.

Let $A$ and $\hat{A}$ be symmetric matrices. Let $v$ be a unit eigenvector of $A$ with eigenvalue $\lambda$, and suppose $\lambda$ is separated from the rest of the spectrum of $A$ by a gap $\delta > 0$ (i.e., $|\lambda - \lambda_j(A)| \geq \delta$ for all other eigenvalues $\lambda_j$). Let $\hat{v}$ be the corresponding eigenvector of $\hat{A}$. Then:

$\sin\angle(v, \hat{v}) \leq \frac{\|\hat{A} - A\|_{\text{op}}}{\delta}$

The angle between true and estimated eigenvectors is controlled by the perturbation size divided by the eigenvalue gap. Large gap (well-separated eigenvalue) means the eigenvector is stable. Small gap means the eigenvector is sensitive to perturbation.

This is exactly the "signal-to-noise" ratio for eigenvector estimation: $\|\hat{A} - A\|_{\text{op}}$ is the noise, $\delta$ is the signal strength.

Davis-Kahan is essential for:

• PCA: the estimated principal components are close to the true ones when $\|\hat{\Sigma} - \Sigma\|_{\text{op}}/\delta$ is small
• Spectral clustering: the estimated cluster indicators (from eigenvectors of the graph Laplacian) are close to the truth
• Low-rank matrix recovery: recovered factors are close to the true ones

Any spectral method requires Davis-Kahan for its theoretical analysis.

The bound depends on the reciprocal of the gap $\delta$. If eigenvalues are close together, eigenvectors are inherently unstable. The individual eigenvectors are meaningless, though their span may still be stable. For eigenvalue clusters, you need the block version of Davis-Kahan (the $\sin\Theta$ theorem) which controls the angle between eigenspaces.