OMP in Python, expected results

With some help from Vlad N., and Alejandro Weinstein, I was able to translate my MATLAB implementation of OMP with QR factorization into Python. And below are the results I am seeing with an exact recovery condition of Maleki and Donoho, i.e., \(\|\vx – \hat\vx\|_2^2 < 10^{-4}\|\vx\|_2^2\). This is exactly what should happen.

And here is the phase transition for exact support recovery.

Here is my code: It doesn’t run as fast as I was hoping, and in fact takes about 100 times as long as MATLAB. Maybe I am doing some unnecessary copying to and from memory, transpositions, and whatever.


7 thoughts on “OMP in Python, expected results

  1. Hi Bob,
    I haven’t looked carefully at the code, but you might want to profile it to see where the bottlenecks are. using the cProfile module is quite straigthforward, just replace your last line by :
    cProfile.runctx(‘runProblemSuite(ambientDimension,numGradations,numTrials) ‘ , globals() , locals())
    and you should quickly see what is(are) the issue(s)


  2. Hi Bob,
    Do you happen to know if there are Python implementations available for other basic CS algorithms, besides OMP? I’m pondering on migrating from Matlab to Python, but translating existing Matlab-only algorithms would be a nightmare. I mean l1 minimization (I think cvxopt could be used), OMP, K-SVD and such.


  3. Hi Nic. I am only a few days new to Python myself, so I am not sure. But I do know that part of scikit-learn is being developed for K-SVD … which is really just SVD and any choice of sparse approximation algorithm. See:
    And as soon as I figure out how to make my QR implementation of OMP in Python run much faster, I will translate other algorithms as well, such as OLS, SL0, etc. :)


  4. Thanks Bob. Yeah I could roll my own quick direct implementations, it’s rather the parameter checking, all options, solver choosing and all the stuff that makes a well written code different from a quick hack that I was trying to avoid. But I suppose that somebody’s just got to do them, so ‘tmight well be me.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s