Hierarchical Eigensolver for Transition Matrices in Spectral Methods

We show how to build hierarchical, reduced-rank representation for large stochastic matrices and use this representation to design an efficient algorithm forcomputing the largest eigenvalues, and the corresponding eigenvectors. In particular, the eigen problem is first solved at the coarsest levelof the representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy. A small number of power iterations are employed at each stage to correct the eigen solution. The typical speedups obtained by a Matlab implementation of our fast eigensolver over a standard sparse matrix eigensolver [13] are at least a factor of ten for large image sizes. The hierarchical representation has proven to be effective in a min-cut based segmentation algorithm that we proposed recently [8].