dbindel
commented
5 years ago By Gershgorin’s theorem, the Laplacian matrix has eigenvalues between zero and 2*d_max where d_max is the maximum (weighted) degree. One can get a tighter interval that contains the spectrum using a few steps of Lanczos to estimate the extreme eigenvalues (and then pushing out by a small safety factor).
Once one has an interval [a, b] that contains the spectrum of L, compute the spectral density of A = 2 (L-cI) / (b-a) where c = (a+b)/2. The eigenvalues of A lie between [-1,1]; and to recover the eigenvalues of L, note that if mu is an eigenvalue of A, then lambda = mu(b-a)/2 + c is an eigenvalue of L.
On Sep 1, 2019, at 9:08 PM, sjyang notifications@github.com wrote:
The paper has mentioned that this approximation method can be easily extended to compute the Laplacian matrix's eigenvalues. Could you please give me some intuition on how to modify the original algorithm, i.e. how to scale the Laplacian matrix spectrum(to let its spectrum lies in [-1, 1])
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.
Jasmineysj
The paper has mentioned that this approximation method can be easily extended to compute the Laplacian matrix's eigenvalues. Could you please give me some intuition on how to modify the original algorithm, i.e. how to scale the Laplacian matrix spectrum(to let its spectrum lies in [-1, 1])