After I pointed out something was not right with the scikit-learn implementation of OMP, Vlad N. and Alejandro W. took up the challenge and found the very subtle reason for its mysterious behavior: column swapping gone awry. I have now tested the new implementation against my slower one, and the results show a nearly perfect match to the expected behavior … maybe even a little better than the QR implementation. Good work!

### Like this:

Like Loading...

*Related*

I think that the Cholesky and the QR implementation should be more or less equivalent, if not by complexity then certainly by the results they produce. I guess that the little dent in the plot is attributable to chance?

It would be a nice idea to apply the same memory layout optimizations that are used in the current Cholesky implementation used in scikit-learn to the QR algorithm, I will try it out and benchmark it sometime soon!

Thank you again for spotting this bug!

Vlad

LikeLike

I would say so too, but I think the QR implementation lends itself to more fancy algorithms, like orthogonal least squares (also known as recursive modified Gram-Schmidt and optimized orthogonal matching pursuit and stepwise projection algorithm and greedy forward selection and … ) The modification to my python implementation of QR OMP is very minimal, but involves an orthogonalization of the entire dictionary … I think. Maybe we can get around that.

Let me know about your results! :)

LikeLike