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: omp_phase3.py. 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.
Folk the Algorithms 
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)
Cheers,
Manu
LikeLike
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.
Best,
Nic
LikeLike
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: http://venefrombucharest.wordpress.com/2011/09/19/dictionary-learning-in-scikit-learn-0-9/
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. :)
LikeLike
Thanks Manu! I will check it out.
LikeLike
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.
LikeLike
I am interested in learning more as you do, so don’t be a stranger! :)
LikeLike
Don’t worry, if my new-Python-convert enthusiasm lives long enough to produce anything useful, I won’t be.
LikeLike