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

The applicable setting is sums of independent, centered, Hermitian random matrices with bounded operator norm almost surely. The Hermitian dilation extends the same machinery to rectangular matrices; see Tropp (2015) Chapter 6.

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$ arises from a Rademacher symmetrization step in the proof; it can be tightened to $2$ when the summands $X_i$ are themselves symmetric (equal in distribution to $-X_i$), so the $8$ is not intrinsic to 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.

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. Let $V$ be any positive semidefinite matrix satisfying $V \succeq \sum_i \mathbb{E}[X_i^2]$ (in the Loewner order) and let $\sigma^2 = \|V\|_{\text{op}}$. Define the intrinsic dimension of $V$:

$\mathrm{intdim}(V) = \frac{\mathrm{tr}(V)}{\|V\|_{\text{op}}} \in [1, d]$

Then for $t \geq \sigma + R/3$:

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

Equivalently, with probability $\geq 1 - \delta$:

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

Source: Tropp (2015), Theorem 7.3.1.

The standard Matrix Bernstein bound has a prefactor $2d$ from the trace inequality $\mathrm{tr}(e^{\theta Y}) \leq d \cdot e^{\theta \lambda_{\max}(Y)}$. A sharper trace bound uses $\mathrm{tr}(f(Y)) \leq \mathrm{intdim}(V) \cdot f(\lambda_{\max}(Y))$ for suitable functions $f$, replacing $d$ with the effective rank of $V$.

When $V$ is approximately rank-$r$ ($r$ dominant eigenvalues, the rest small), $\mathrm{intdim}(V) \approx r$. For low-rank covariance ($r \ll d$), the $\log d$ factor in the standard bound becomes $\log r$, which can be a dramatic improvement.

The improvement is critical for low-rank matrix problems:

• Low-rank matrix completion: when only $r$ singular values are non-trivial, sample complexity scales with $r$, not $d$. Intrinsic-dimension Bernstein gives $n \gtrsim r \log r$ instead of $n \gtrsim d \log d$.
• Spectral methods on graphs with community structure: the signal matrix has $k$ dominant eigenvalues (one per community), so spectral recovery cost scales with $k$, not the number of nodes.
• Random features and kernel methods: low effective rank of the data kernel matrix translates to low sample complexity for kernel ridge regression.

The bound also matters for infinite-dimensional operators on Hilbert spaces, where $d = \infty$ but $\mathrm{intdim}$ remains finite.

If the variance is genuinely spread across all $d$ directions, then $\mathrm{intdim}(V) \approx d$ and the bound recovers standard Matrix Bernstein with no improvement. The intrinsic-dimension version is only useful when the noise is anisotropic. Estimating $\mathrm{intdim}(V)$ from data (rather than knowing $V$ a priori) typically requires a separate concentration argument.

Let $X_1, \ldots, X_n$ be independent positive semidefinite random matrices in $\mathbb{R}^{d \times d}$ with $\|X_i\|_{\text{op}} \leq R$ almost surely. Let $Y = \sum_i X_i$ and define $\mu_{\max} = \lambda_{\max}(\mathbb{E}[Y])$ and $\mu_{\min} = \lambda_{\min}(\mathbb{E}[Y])$. Then for any $\epsilon \in [0, 1)$:

$\mathbb{P}\!\bigl(\lambda_{\min}(Y) \leq (1 - \epsilon) \mu_{\min}\bigr) \leq d \cdot \exp\!\Bigl(-\frac{\epsilon^2 \mu_{\min}}{2R}\Bigr)$

$\mathbb{P}\!\bigl(\lambda_{\max}(Y) \geq (1 + \epsilon) \mu_{\max}\bigr) \leq d \cdot \exp\!\Bigl(-\frac{\epsilon^2 \mu_{\max}}{3R}\Bigr)$

Source: Tropp (2012), "User-Friendly Tail Bounds for Sums of Random Matrices," Theorem 1.1; Tropp (2015), Theorem 5.1.1.

This is the matrix analog of the multiplicative Chernoff bound. The factor of $\mu_{\min}$ in the lower-tail exponent is what distinguishes it from a naive Bernstein bound: when $\mu_{\min}$ is large, the relative error decays exponentially fast.

The key application: bounding the smallest eigenvalue of a sample covariance matrix to certify invertibility. If $X_i = x_i x_i^\top / n$ with $\|x_i\|_2 \leq \sqrt{R}$ and $\mathbb{E}[X_i] = \Sigma/n$, then $\mu_{\min} = \lambda_{\min}(\Sigma)$, and Matrix Chernoff gives a sample- complexity bound for spectral estimators that need lower-bounded eigenvalues.

• Random graph spectral gaps: lower-bound the smallest eigenvalue of the Laplacian to certify connectivity.
• Coupon-collector style sampling: $n$ coordinates of the identity drawn uniformly, bounded by Matrix Chernoff to control coverage.
• Compressed sensing: certify the restricted-isometry property of random projections via lower eigenvalue bounds on $\Phi^\top \Phi$.
• Bandit linear estimation: the design matrix $\sum_t x_t x_t^\top$ must be invertible for OLS; Matrix Chernoff gives sample-complexity bounds.

The bound requires PSD summands. For general (signed) matrices, only Matrix Bernstein applies, and you cannot directly bound $\lambda_{\min}$. The Hermitian dilation trick lifts non-PSD problems to PSD ones at a cost of doubling the dimension.

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, \hat{A}$ be symmetric matrices with eigenpairs $(\lambda_i, v_i)$ and $(\hat{\lambda}_i, \hat{v}_i)$ respectively. Fix an index $i$ and let

$\delta = \min_{j \neq i} |\lambda_i - \lambda_j| > 0$

be the gap in the spectrum of $A$ (not $\hat{A}$). Then:

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

Here $\angle(v_i, \hat{v}_i)$ denotes the angle between the one-dimensional subspaces spanned by $v_i$ and $\hat{v}_i$, equivalently $\min(\angle(v_i, \hat{v}_i), \angle(v_i, -\hat{v}_i))$, since eigenvectors are only defined up to sign.

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.