All set, waiting for review.

Thanks @smarie , LGTM. Let's wait for other reviews now.

Thanks @NicolasHug . If you have still a couple time for reviews in the next days, I would really appreciate a review for the companion PRs of this PR:

• [MRG before #12069] KernelPCA: raise Errors and Warnings according to eigenvalue decomposition numerical/conditioning issues #12145 to provide kernel warnings when the gram matrix has conditioning issues
• [MRG after #12145] Add "Randomized SVD" solver option to KernelPCA for faster partial decompositions, like in PCA #12069 to add the randomized svd solver to accelerate partial decompositions. This was my original PR actually :)

Your #12069 (comment)

the randomized method seems to naturally find the "perfect zero eigenvalues" while arpack and dense methods most of the time find a tiny non-zero number instead (e.g. of the order of magnitude of 1e-16 if my memory is correct)

makes me think we should not test for strict equality with zero but instead have an approximate comparison.

Actually that's already taken care of - but in #12145 :) where we round to zero the small eigenvalues that are due to bad numerical conditioning (as well as negative eigenvalues because a kernel is supposed to be semi-positive definite so they are probably numerical errors).

See https://github.com/scikit-learn/scikit-learn/pull/12145/files#diff-3b70045c110a30d29de66ed0ea3fb86dR1082 for details

OK. I guess this would make sense to do it here?

IMHO the way to go would be to first merge this one, then #12145, and then #12069. This way you can merge master each time to avoid the redundant changes in the diffs (right now #12145 diffs also show the changes from here and that make reviewing trickier)

Yes, this is the merge order that should be used since each PR contains and relies on the commits from the previous. I am not sure that it would make sense to backport the zero eigenvalues rounding here: indeed, that is precisely what #12145 is about : controling and harmonizing the eigenvalues found by the various solvers.

You're right, if #12145 sets small eigenvalues to 0 then the code here won't have to change.

Hi @NicolasHug , @jnothman , @ogrisel : any update on this PR and the subsequent ones #12145 and #12069 ? Experience shows that the more we wait the more likely the PRs will not be mergeable again...

Of course I understand that this is a volunteer-based open-source project with many contributions, but I really believe that the effort we collectively made on these three PR both in terms of idea (@grilling original code in matlab), coding, and code review, is mature now.

@jnothman I updated what's new following your advice on the other kPCA PR. The documentation does not need to be updated, this is ready to Merge (this PR is the first of a series of 3 : #12143, #12145 and #12069)

Maybe @adrinjalali and @qinhanmin2014 could to review this? Should be quick to review IMO (LGTM already) and it'd be nice to address @smarie great efforts ;)

This is +2 now, @thomasjpfan can you merge it please?

Thanks everyone!