Hi, @mblondel I would like / am working on this issue. I played with the current implementation of truncatedSVD, using a few examples, given in the research papers, If I am right, you would like to have a new algorithm "eigh" for finding the SVD decomposition of X?

Any specific pointers, before I actually start coding on this and submit a PR within 2-3 days?

Nope, only the right singular vectors.

We have this already. TruncatedSVD(algorithm="arpack") uses scipy.sparse.linalg.svds, which

is a naive implementation using ARPACK as an eigensolver on A.H * A or A * A.H, depending on which one is more efficient.

(http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.svds.html)

Thanks I didn't know that. If we only need the right singular vectors, it seems that svds does a little bit more than necessary (but I guess we can live with that?)
https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/arpack.py#L1660

I'm not sure what you mean; we always want both the components and the reduced X, right? (Otherwise, a PR to SciPy and a backported svds would seem more appropriate than introducing our own variant.)

I think I got confused by this comment:
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/decomposition/truncated_svd.py#L123

That was actually supposed to be a TODO: find out if there's any case where doing safe_sparse_dot(X, VT.T).T would be faster than np.dot(U, Sigma.T). The latter is a matrix-vector multiplication of cost O(n_samples×n_components), while the former is typically be a sparse-dense matrix multiplication of cost O(X.nnz×n_components), if I'm not mistaken. But since X.nnz is expected to be larger than n_samples and there's a large constant hiding in the latter big-O, I think the comment can go away.

Shall we close this issue?

I guess so. We could add the following comment:

svds is a naive implementation using ARPACK as an eigensolver on A.H * A or A * A.H, depending on which one is more efficient.