On Wed, May 02, 2012 at 11:00:20AM -0400, Satrajit Ghosh wrote:
> that's helpful. the difference was in the adjacency matrix. i was assuming
> a system with a self loop on the nodes with arbitrary weights (i.e., a
> general form of a undirected graph).
AFAIK, spectral clustering and spectral embedding do not work with
weights on the diagonal. In the UvL tutorial that you point to, she says
on page 4, one paragraph above prop 2 that the graph laplacian does not
depend on the weights of the diagonal.
> The reason is that the eigenvectors of Lrw are cluster indicator vectors 1Ai
> , while the eigenvectors of Lsym are additionally multiplied with D1/2, which
> might lead to undesired arti- facts. As using Lsym also does not have any
> computational advantages, we thus advocate for using Lrw.
I disagree with this statement. Using Lsym enables to use an SPD solver
to diagonalize the matrix. SPD solvers are not only faster, they are in
addition much more stable if the spectrum of the matrix has almost
degenerate eigenvalues, because they can enforce orthogonality between
the corresponding eigenvectors. Back when I implemented this, my
experience was that using non SPD solvers was too prone to numerical
errors to be useful in many cases.
I am a bit surprised that UvL advocates Lrw. I find her arguments a bit
weak. Most importantly, there is exact mathematical correspondance
between the two approaches. Indeed, the generalized eigenvalue problem of
the non-symmetric approach is:
L u = lambda D u
Where D are the weights of the diagonal. We can rewrite this equation as:
D^(-1/2) L D^(-1/2) D^(1/2) u = lambda D^(1/2) u
Thus, if we write Lsym = D^(-1/2) L D^(-1/2) and v = D^(1/2) u, the
eigenvalue problem is equivalent to:
Lsym v = lambda v
The only reason for which one approach might be prefered to another is
better speed or stability properties of the solvers on one of the
problems or the other.
It might be that with a better knowledge of eigenvalue solvers, the
generalized eigenvalue problem of the Shi and Malik approach (alg top of
page 7) can be solved in an efficient and stable way. However, note that
the proposed approach is to keep a symmetric unnormalized laplacian and
solve a **generalized** eigenvalue problem, and not to solve a non SPD
eigenvalue problem.
> all sklearners: I'd like to propose allowing the different normalizations
> and if necessary switching to Lrw as the default and allowing for any
> adjacency matrix. any objections?
I have an objection. The type of solvers down the line are fairly
different. It is not just a matter of changing the normalization. In
addition, I'd like to be convinced that there is an actual benefit,
because my experience was the opposite. That said, when I did it, I used
a fairly naive approach to solving the generalized eigenvalue problem.
Is there a reason in particular that you are looking at this
normalization? Looking at this reason might help us understand the stakes
here.
Cheers,
Gaël
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Scikit-learn-general mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
