# Is there a connection between the Davis-Kahan sin theta Theorem and the smallest nonzero singular value of a symmetric Matrix

I'm trying to understand a step in a proof in the paper "Consistency of Spectral Clustering in stochastic Block Models" from J.Lei and A.Rinaldo.

In Lemma 5.1 they use the

Davis Kahan-sin $\Theta$ Theorem:

Let $A,B\in \mathbb{R}^{n\times n}$ hermitian Matrices, $S_1=\left[a,b \right]$ and $S_2=\mathbb{R}\setminus\left(a-\delta,b+\delta \right)$. Let $E:=P_A(S_1)$ and $F:=P_B(S_2)$, then for each unitary invariant Norm $\lVert EF\rVert \le \frac{1}{\delta}\lVert E(A-B)F\rVert \le \frac{1}{\delta} \lVert A-B\rVert$ where $P_S(M)$ is the orthogonal Projection in the Space spanned by the Eigenvectors of the Matrix M to the Eigenvalues in $S\subset\mathbb{R}$.

in the following Problem:

Let $A,B\in \mathbb{R}^{n \times n}$ be symmetric Matrices, $B$ has rang $K$ and the smallest nonzero singular value $\lambda$. Let $U,\hat{U}\in\mathbb{R}^{n \times K}$ be the Matrices of the Eigenvectors coresponding to the $K$ first Eigenvalues (ordered in descending order) from $A$ and $B$

What they want to proof is

$\lVert (I-\hat{U}\hat{U}^T)UU^T\rVert\le 2\frac{\lVert A-B\rVert}{\lambda}$

this leads to two cases the first is $\lVert A-B\rVert\le\lambda$ (the other one is trivial)

and now they use the Davis Kahan Theorem to show that $\lVert (I-\hat{U}\hat{U}^T)UU^T\rVert\le \frac{\lVert A-B\rVert}{\lambda-\lVert A-B\rVert}\le 2\frac{\lVert A-B\rVert}{\lambda}$.

I don't understand what they use as $\delta$ and if they use $\delta=\lambda-\lVert A-B\rVert$ how does the Theorem still aply. I tried other versions of the Theorem for example from http://arxiv.org/pdf/1405.0680.pdf, but it didn't help me.

Is there maybe a connestion between the singular Value and $\delta$?

Indeed, they are using Davis-Kahan $\sin (\Theta)$ theorem. But the theorem also works if we interchange $S_1$ and $S_2$.

In this particular application of the theorem, $E = U$ and $F = \hat{U}^{\perp}$, such that $[\hat{U}; \hat{U}^\perp]$ forms an orthogonal matrix or in other words,

$$I = \hat{U} \hat{U}^T + \hat{U}^\perp {\hat{U}^\perp}^T\,.$$

Now we need to find corresponding $S_1, S_2$. Since $B$ is rank $K$, we know that eigenvalues of ${\hat{U}^\perp}^T B {\hat{U}^\perp}$ are all $0$ (thus $S_1 = [0,0]$).

Since $U$ spans the space corresponding to top-$K$ eigenvectors of $A$, eigenvalues of ${U^T A U}$ are the eigenvalues are top-$K$ eigenvalues of $A$. Assuming $\|A-B\| \leq \lambda$, one can trivially show that,

$$\lambda_i(B) + \lambda_n(A - B) \leq \lambda_i(A) \leq \lambda_i(B) + \lambda_1(A - B) \\ \implies \lambda_i(B) - \|A - B\| \leq \lambda_i(A) \leq \lambda_i(B) + \|A - B\|\,,$$ where $\|A - B\|$ is the operator norm or the largest singular value of $A-B$. This implies that top-$K$ eigenvalues $A$ lies in $S_2 = \mathbb{R} \setminus (-\lambda + \|A - B\|, \lambda - \|A - B\|)$, which implies that $\delta = \lambda - \|A - B\|$.

Finally using Davis-Kahan we get, $$\|(I - \hat{U} \hat{U}^T) UU^T\| = \|\hat{U}^\perp {\hat{U}^\perp}^T UU^T\| \leq \|{\hat{U}^\perp}^T U\| \leq \frac{\|A-B\|}{\lambda - \|A-B\|}\,.$$