arpack_wrapper.hpp handles non self-adjoint input ?

[coderlevi]

Hi,

When I read the file include/tapkee/utils/arpack_wrapper.hpp, I see that it only handles the self-adjoint matrix A to solve the eigen problem A v = \lambda v. If A is not self-adjoint, then it looks that we can not use arpack in tapkee or we have to modify the arpack_wrapper.hpp to handle non self-adjoint input ?

When I run 'examples/borsch swissroll isomap', it shows that arpack_wrapper.hpp is handling the non-symmetric maxtrix A since I printed out
A[533][207] = -148.229072 and A[207][533] = -143.89085

Could you clarify this ?

Thanks.

Best,
Levi

[lisitsyn]

Hey, you're right the matrix has to be self-adjoint. Isomap should produce self-adjoint matrix as well so I will have to check what's going on there.

[lisitsyn]

I can reproduce some asymmetry in isomap matrix, will let you know what caused that

[coderlevi]

Hi,

I think the non symmetric matrix is caused by our logic using K nearest neighbors.

For example, when I run "examples/borsch scurve isomap", I see that point 947 is the neighbor of point 0 but point 0 is not the neighbor of point 947. In this case, K = 20, which means that point 947 is among the 20 nearest neighbors of point 0 while point 0 is not among the 20 nearest neighbors of point 947

Furthermore, let's assume that 1 -> 0 -> 947 is the shortest path from point 1 to point 947, but the shortest path from point 947 to point 1 can not be the path 947 -> 0 -> 1 since point 0 is not a neighbor of point 947.

We are using K-isomap which is looking for K nearest neighbors of every point. In this case the shortest path matrix is not symmetric and arpack wrapper has to deal with non symmetric input, right ?

Or we can use \epsilon-isomap which considers all the points within \epsilon distance as the neighbors of one point. In this case we can get a symmetric shortest path matrix. But this is not implemented in current tapkee code.

[lisitsyn]

@coderlevi thanks for researching on that. You are right, it was somehow missed that neighborhood matrix (hence, the shortest path matrix) is not symmetrical.

I think it makes sense to enforce symmetricity of neighborhoods with either intersection (mutual neighbors) or union. If you feel like experimenting with that - I can help, otherwise I'll try to get to that once I get some spare time.

[coderlevi]

@lisitsyn Thanks for the suggestion, which makes perfect sense. I will use union of neighbors idea.

[lisitsyn]

I'd keep it open until I or someone else merge some code fixing that