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!



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!


Leave a comment

About this Entry

This page contains a single entry by Bob L. Sturm published on October 20, 2011 2:57 PM.

Signal recovery with pure greed was the previous entry in this blog.

CMP vs. OMP: A Computational Cost Perspective is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.