Spectral gap

A spectral gap is a positive separation between designated parts of the spectrum of a linear operator. For the power method, the relevant gap separates the modulus of the dominant eigenvalue from the other eigenvalue moduli.

Suppose $H\ge 0$ has ground energy zero and positive spectral gap at least $g$, and $0\le V\le I$. Let $\nu$ be the minimum of $V$ restricted to the ground space. Splitting a normalized vector into ground and excited components bounds its energy below by $\delta \nu +(g-\delta )y^2-2\delta y$, with $y$ the excited norm. Completing the square yields the displayed bound for $0<\delta <g$. The error is controlled by the gap and cannot be treated as a uniform $O({\delta }^2)$ when $g$ closes.

The Davis-Kahan theorem bounds the change of an invariant eigenspace of a symmetric matrix in terms of a matrix perturbation and an appropriate spectral gap. The rank-one eigenprojector perturbation bound below depends only on the unperturbed gap. Yu, Wang and Samworth's formulation gives population-gap bounds in greater generality.

If a symmetric matrix $H$ has largest eigenvalue ${\lambda }_1$ separated from ${\lambda }_2$ by $\gamma >0$, and $P=v{v}^{\top }$ is its leading rank-one orthogonal projection matrix, then every unit vector $u$, with $Q=u{u}^{\top }$, satisfies the displayed inequality. Expanding $u$ in an orthonormal eigenbasis gives ${\lambda }_1-u^{\top }Hu\ge \gamma (1-|u^{\top }v{|}^2)$, while $\Vert P-Q{\Vert }_F^2=2(1-|u^{\top }v{|}^2)$. The analogous statement for a smallest eigenvalue follows by replacing $H$ by $-H$.

Let $\hat{P}$ project onto a leading unit eigenvector of $H+W$, with $H$ as in the Davis-Kahan curvature lemma. Its maximizing Rayleigh quotient gives $\mathrm{tr}(H(P-\hat{P}))\le \mathrm{tr}(W(\hat{P}-P))$. Duality of the operator norm and trace norm, together with the rank-two bound $\Vert \hat{P}-P{\Vert }_{\ast }\le \sqrt{2}\Vert \hat{P}-P{\Vert }_F$, proves the estimate. No gap condition on the perturbed matrix is needed.