To the rescue!

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!

OMPvs.png

Advertisements

2 thoughts on “To the rescue!

  1. 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

    Like

  2. 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! :)

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s