3
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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\|}\,. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.