search

epfl-lts2 / pygsp

Graph Signal Processing in Python
https://pygsp.rtfd.io
BSD 3-Clause "New" or "Revised" License
483 stars 93 forks source link

Bug in graph.compute_fourier_basis #53

Closed rodrigo-pena closed 5 years ago

rodrigo-pena commented 5 years ago

When you call graph.compute_fourier_basis(n_eigenvectors=k), only the first k-1 eigenvectors are computed, because of the design of the function sparse.linalg.eigsh.

In particular, we have as a consequence that graph.set_coordinates(kind='laplacian_eigenmap2D') sets graph.coords to a one-dimensional vector.

mdeff commented 5 years ago

Thanks for reporting! Would you be so kind as sending a PR? :)

mdeff commented 5 years ago

Actually, I think the problem is in set_coordinates. It asks for two eigenvectors when kind='laplacian_eigenmap2D' while it should ask for three as the first constant eigenvector is discarded. Isn't it? (BTW, why doesn't self.U[:, 1:3] raise an exception if there's only two eigenvectors?)

The documentation of scipy.sparse.linalg.eigsh says:

k : int, optional The number of eigenvalues and eigenvectors desired. k must be smaller than N. It is not possible to compute all eigenvectors of a matrix.

rodrigo-pena commented 5 years ago

Yes, it seems that the problem is in set_coordinates, because graph.compute_fourier_basis(n_eigenvectors=2) computes indeed the first 2 eigenvectors. However, we need at least 3, because the first one is trivial. Actually, there should be some functionality that detects how many trivial eigenvectors there are, and then returns the first two non-trivial ones.

As for your remark:

BTW, why doesn't self.U[:, 1:3] raise an exception if there's only two eigenvectors?

if self.U has only two columns, numpy returns self.U[:,1] no matter the index i that you put in self.U[:, 1:i], as long as i is larger than self.U.shape[1].

I'll open a branch to fix the issue.

mdeff commented 5 years ago

Fixed in #54.