1

I am currently working through the theory of spectral clustering and most of the 'tutorials' explain the laplacian L as being block diagonal where the blocks are related to possible clusters. It seems to me this heavily depends on the ordering of the input vectors and that this would only be true when consecutive input vectors are indeed close to eachother. Or am I missing something in the process of spectral clustering that would actually be responsible for this being 'block-diagonal' of L?

Smartkoder
  • 13

1 Answers1

2

It is block diagonal in the sense that you can always permute vertices such that each block represents a maximal cluster. Note that the eigenvalues will not change because if your original matrix is $L$, and you permute it to be block diagonal, you get $\tilde{L}=P^TLP$, where $P$ is your permutation matrix, and so if $Lx=\lambda x$ then $P^TLP (P^{-1}xP)=\lambda P^TxP=\lambda (P^{-1}xP)$,

(since $P$ is orthonormal). So for the purposes of spectral analysis, it's completely equivalent to work with the block diagonal version of $L$. The nice thing about putting it in block diagonal form will cause the eigenvectors to also be in blocks.

Alex R.
  • 32,771
  • Thanks , all clear now – Smartkoder Jun 04 '17 at 07:51
  • [+1] @Smartkoder I take the opportunity to ask you a which algorithm(s?) "permutes vertices such that each block represents a maximal cluster". – Jean Marie Jun 04 '17 at 07:54
  • @JeanMarie : Actually I found this thread which discusses your additional question, I just skimmed through the answers and there are multiple methods to approach "the search for P". However in my case I am happy with Alex's answer since he shows the rest of the process can be computed without worrying about L being an actual block matrix. – Smartkoder Jun 04 '17 at 13:05