>  my reading of the literature suggests that the spectral embedding
>  implementation currently in sklearn is what the paper 1 below refers
>  to as a laplacian eigenmap.

The literature is very muddy with regards to names and definition. Paper
1 implies that laplacian eigenmap are always applied on graphs built
using kNN, while diffusion maps use an RBF kernel. I disagree with thes
definitions, as in my eyes, these methods can be applied to a similarity
graph, rather than a raw set of data point. I don't think that making a
difference based on how you construct the graph is relevant, and it seems
to me that all these methods fall in the very blurry spectrum of spectral
embedding methods. The reason that Laplacian based method and diffusion
based method are intrinsically linked is because they both relate to the
Laplace-Betrami operator, either by finding its eigenvectors, or by
iterating it.

However, paper 1 seems to define diffusion maps as i) finite iterations
ii) using an RBF kernel to construct a dense similarity graph. Let's take
this as a working definition for the discussion, just to move things
forward, although I am not convinced that such a definition is
universally accepted. By the way, I would agree with you that our
documentation could be improved to discuss the link between different
names, such as spectral embedding, diffusion maps, and laplacian
eigenmaps. We could for instance add that standard asymptotic diffusion
maps can be obtained using an RBF kernel in the spectral embedding.

> i hope to use sklearn to reproduce results such as these for my data/domain
> (and i think we should support the algorithms included in the comparison):

Our goal in scikit-learn is not to reproduce the literature. It may be a
enjoyable side effect of the fact that we are implementing many methods.
But we will not go out of our way to reproduce papers. In my experience,
scientific publications often contains hacks and specificities that we do
not want in a general purpose software library. To reproduce a paper, the
best option is probably to ask the authors for code.

As a side note, paper 1 does not come to very appealing conclusion about
diffusion maps, as they define them. I think that both having a dense
(and thus non-robust) affinity matrix and using finite-time diffusion is
a very bad idea.

> further, it's currently unclear on what basis algorithms are chosen for
> inclusion. even by crude metrics such as citations, "diffusion maps" has many
> more citations compared to ltsa. if anything, hopefully this discussion can
> lend some clarity to what one can contribute to sklearn before somebody spends
> time trying to develop something for the package.

> so here are some questions for you:

>   • what is the objective standard by which you measure practicality and
>     usefulness?
>   • what is a variant on an algorithm?

Off course its unclear. There is no absolute metric, no objective
standard. It's a tradeoff based on many different judgment calls that try
to build a useful and consistent library.

If your question is: "why did LTSA get into scikit-learn?", I can give
you an answer. Above all, Jake has shown over time that he does
absolutely beautiful code from the algorithmic and cosmetic points of
view, with great tests and documentation. He sticks around, fixes bugs
and refactors when needed (for instance rewriting all his ball tree code
from C to Cython). LTSA adds a fairly small number of lines to the LLE
code, and thus seems an acceptable tradeoff to me as have the conviction
that the author will be around for a while to answer questions on it.

Usually, my own personal rule of thumb for including or not an algorithm
in the scikit learn is that it should be widely cited, it should be well
implemented and scalable, and it should fit with the scikit-learn's
goals, but also it should come with an example based on a real-world
usecase that shows a clear cut benefit. That last one is important. 

It's also difficult to tell right ahead when starting work whether it
will be suited for inclusion in the scikit-learn. My own harddrive is
littered with a graveyard of 'good ideas' that didn't pass the bar. For
instance, I spent a fair amount of time on a super-fancy complete linkage
algorithm that didn't live up to its promises
https://github.com/GaelVaroquaux/tmp_complete_linkage 
In the same vein than diffusion maps, @ogrisel spent quite a while
working on 'power iteration clustering'
https://github.com/scikit-learn/scikit-learn/pull/138 
that still hasn't been able to convince us (or himself, I believe) that
it was worth including. And the list can go on for long. I have closed
some of my own pull requests because they turned out not to be as useful
as I would have liked.

I don't want to draw the line of finite-time diffusion maps. If you can
convince us that they bring a definite value and are scalable, we'll
integrate a good PR. I just want to stress that it should be well
motivated.