\(\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\) \(\newcommand{\norm}[1]{\left\lVert#1\right\rVert}\) \(\newcommand{\inner}[1]{\left\langle#1\right\rangle}\) \(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\) \(\DeclareMathOperator*{\V}{\mathbb{V}}\)
C
oncentration inequalities for random matrices, and the perturbation bounds that turn a norm bound on the noise into a statement about eigenvalues and eigenvectors. This note uses the norms, decompositions, and $\mathcal O_p$ notation from the other three.
From Scalar to Matrix Concentration
Hoeffding and Bernstein control sums of independent scalars. The matrix versions below control sums of independent random matrices in operator norm, which is what any bound on eigenvalues or eigenspaces eventually needs.
Sub-Gaussian and Sub-Exponential Random Variables
A mean-zero random variable $X$ is sub-Gaussian if there exists $K>0$ such that
\[\mathbb E e^{tX} \le e^{K^2 t^2/2} \quad \forall t\in\mathbb R.\]It is sub-exponential if
\[\mathbb E e^{tX} \le e^{K^2 t^2} \quad \text{for } |t| \le 1/K.\]Most of the bounds below assume one of these two.
Hanson-Wright Inequality (Quadratic Forms)
Let $x\in\mathbb R^n$ be a random vector with independent, mean-zero, sub-Gaussian entries with parameter $K$. For any fixed matrix $A\in\mathbb R^{n\times n}$,
\[\mathbb P\!\left( \big|x^\top A x - \mathbb E[x^\top A x]\big| > t \right) \le 2\exp\!\left[ - c \min\!\left( \frac{t^2}{K^4 \|A\|_F^2}, \frac{t}{K^2 \|A\|_2} \right) \right].\]Sample covariances and Gram matrices are quadratic forms in the data, so this is the inequality behind most of their entrywise bounds.
Matrix Bernstein Inequality
Let ${X_k}$ be independent, mean-zero, symmetric random matrices in $\mathbb R^{d\times d}$. Assume
\[\|X_k\|_2 \le L \quad \text{almost surely}.\]Define the variance parameter
\[\sigma^2 := \left\| \sum_k \mathbb E(X_k^2) \right\|_2.\]Then for all $t\ge 0$,
\[\mathbb P\!\left( \left\|\sum_k X_k\right\|_2 \ge t \right) \le 2d \exp\!\left( -\frac{t^2/2}{\sigma^2 + Lt/3} \right).\]Except for the leading factor $2d$, this is the scalar Bernstein bound. Integrating the tail shows that the dimension costs only a logarithm:
\[\mathbb E\left\|\sum_k X_k\right\|_2 \le \sqrt{2\sigma^2\log(2d)} + \frac{1}{3}L\log(2d).\]Spectral Norm Concentration of Random Matrices
Sub-Gaussian Noise Matrices
Let $E\in\mathbb R^{m\times n}$ have i.i.d. mean-zero sub-Gaussian entries with variance proxy $\sigma^2$. Then with high probability,
\[\|E\|_2 \le C \sigma \left(\sqrt{m} + \sqrt{n}\right).\]The rate $\sqrt{m}+\sqrt{n}$ is sharp up to the constant.
Sample Covariance Concentration
Let $X_1,\dots,X_n\in\mathbb R^p$ be i.i.d. sub-Gaussian with covariance $\Sigma$. For $p\le n$, the sample covariance satisfies
\[\left\|\frac{1}{n}\sum_{i=1}^n X_i X_i^\top - \Sigma\right\|_2 = \mathcal O_p\!\left(\|\Sigma\|_2 \sqrt{\frac{p}{n}}\right).\]So sample PCA is consistent when $p/n\to 0$. When $p/n$ does not go to zero, the leading sample eigenvector is in general inconsistent (Johnstone and Lu, 2009).
Weyl’s Inequality (Eigenvalue Perturbation)
For symmetric matrices $A$ and $E$,
\[|\lambda_i(A+E) - \lambda_i(A)| \le \|E\|_2 \quad \forall i.\]Eigenvalues move by at most the operator norm of the perturbation, with no gap condition. Eigenvectors do need a gap; see Davis-Kahan below.
Principal Angles Between Subspaces
Let $V,\widehat V \in \mathbb{R}^{n\times r}$ have orthonormal columns, and let $\mathcal S=\mathrm{col}(V)$ and $\widehat{\mathcal S}=\mathrm{col}(\widehat V)$. The principal angles $\theta_1,\ldots,\theta_r \in [0,\pi/2]$ between $\mathcal S$ and $\widehat{\mathcal S}$ are defined by
\[\cos \theta_i = s_i(V^\top \widehat V),\]where $s_i(\cdot)$ denotes the singular values in decreasing order.
Define $\sin\Theta(\widehat V, V)$ as the diagonal matrix with entries $\sin\theta_1,\ldots,\sin\theta_r$. Its operator norm satisfies
\[\|\sin\Theta(\widehat V, V)\|_2 = \|V_\perp^\top \widehat V\|_2,\]where $V_\perp$ spans the orthogonal complement of $\mathcal S$.
Davis-Kahan $\sin\Theta$ Theorem (Eigenspace Perturbation)
Let $A$ and $\widehat A = A + E$ be symmetric. Let $V$ hold the eigenvectors of $A$ for a group of $r$ eigenvalues, and $\widehat V$ the eigenvectors of $\widehat A$ for the corresponding group. Let $\delta>0$ be the distance between those eigenvalues of $A$ and the remaining eigenvalues of $\widehat A$.
Then
\[\|\sin\Theta(\widehat V, V)\|_2 \le \frac{\|E\|_2}{\delta}.\]Eigenvectors are stable only relative to the gap $\delta$. Noise that barely moves the eigenvalues can still rotate the eigenvectors a lot if two eigenvalues are close. Yu, Wang and Samworth (2015) give a variant in which the gap is computed from the eigenvalues of $A$ alone, which is usually what one knows.
Low-Rank Plus Noise Models
Consider the model
\[Y = L + E,\]where $\mathrm{rank}(L)=r$ and $E$ is random noise.
Basic norm bounds yield
\[\|Y\|_2 \le \|L\|_2 + \|E\|_2, \qquad \|Y\|_F^2 = \|L\|_F^2 + \|E\|_F^2 + 2\langle L,E\rangle.\]With the spectral bound from above,
\[\|E\|_2 = \mathcal O_p(\sqrt{m}+\sqrt{n}),\]and Davis-Kahan, this gives error bounds for the truncated SVD of $Y$ as an estimator of $L$.
Nuclear Norm Bounds and Duality
For any matrices $A,B$,
\[|\mathrm{tr}(A^\top B)| \le \|A\|_*\,\|B\|_2.\]The nuclear norm is dual to the spectral norm, and on the spectral-norm unit ball it is the convex envelope of rank (Fazel, 2002). That is why it replaces rank in convex formulations of low-rank recovery and matrix completion.
Summary
| Tool | Controls |
|---|---|
| Hanson-Wright | Quadratic forms |
| Matrix Bernstein | Spectral norm of sums |
| Weyl | Eigenvalues |
| Davis-Kahan | Eigenspaces |
| Sub-Gaussian norm bounds | Noise matrices |
| Nuclear/spectral duality | Low-rank recovery |
Most consistency results for PCA and factor models follow the same two steps: concentration bounds $\norm{E}_2$, then Weyl or Davis-Kahan turns that bound into eigenvalue or eigenvector error.