Davis-Kahan Theorem

[[concept]]

Theorem (Davis-Kahan)

Let $T$ and $T^{'}$ be self-adjoint Hilbert-Schmidt operators with eigenspectra ( $λ_{i,}, φ_{i}$ ) and $(λ_{i}^{'}, φ_{i}^{'})$ respectively ordered by eigenvalue magnitude. Then

| | φ_{i} - φ_{i}^{'} | | \leq \frac{π}{2} \frac{| | T - T^{'} | |}{d (λ_{i}, λ_{i}^{'})}

Where $| | \cdot | |$ is the operator norm and $d (λ_{i}, λ_{i}^{'})$ is defined as

d (λ_{i}, λ_{i}^{'}) \equiv min (min_{j \neq i} (| λ_{i} - λ_{j}^{'} |), min_{j \neq i} (| λ_{j} - λ_{i}^{'} |))

Call the first interior min $d_{1}$ and the second $d_{2}$

Example

$d (λ_{i}, λ_{i}^{'})$ corresponds to the minimum "eigengap" for the closest eigenvalue for eigenvalue $λ_{i}$ in its own spectrum.

Note

If $d (\cdot, \cdot)$ is large, then this is OK for fast convergence. But if this is small, then we also need small $| | T - T^{'} | |$ to get fast convergence.

Process into its own note? #concepts/edit

Let ${G_{n}, X_{n}} \to (W, X)$ . We can use the Davis-Kahan Theorem with $T_{W}$ (the limiting graphon shift operator) and $T_{W_{n}}$ (induced graphon shift operator).

| | φ (T_{W_{n}}) - φ_{i} (T_{W}) | | \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{d (λ_{i} (T_{W}), λ_{i} (T_{W_{n}}))}

This is good because from lecture 15, we know that if $G_{n}$ converges to $W$ in the cut norm, then $T_{W_{n}}$ converges to $T_{W}$ in $L_{2}$ (cut norm Convergence in the cut norm implies convergence in L2). Thus we have convergence in the numerator!

Does this mean everything is OK?

No! The denominator might vanish as $i \to \infty$ since we have $λ_{i} \to 0$ from the second part of the spectral theorem for self-adjoint compact operators on Hilbert spaces
- even though we look at $min (d_{1}, d_{2})$ and $λ_{i} \neq λ_{j}$ converge to different values (and therefore $d (\cdot) \to ℓ > 0$ ), it still might not work.
Even if we have eigenvalue convergence, this convergence is not necessarily uniform. (recall the difference between convergence and uniform convergence) because the graphon eigenvalues accumulate at 0.

Mentions

File
2025-04-02 lecture 17
Davis-Kahan Theorem

Created 2025-04-09 Last Modified 2025-05-13