Friday, November 23, 2012

Compressive Sensing Solvers in Python and the ones that ought be in Python, R,....

Due to being featured on a the SciPyTip twitter stream yesterday, and prompted by the question of Jaidev, I went through the list of compressive solvers and tried to find the ones that were developed using Python. What developers need to realize is that the vast majority of solvers in the compressive sensing big picture page are in Matlab mostly because those are research prototypes. Python codes are somewhat rare because the field is fluctuating fast. The initial solvers were a 1000 slower than some that appeared four years later
If you are a developer, and want to be a hipster when it comes to providing some of the best algorithms out there in compressive sensing (i.e.l finding the sparsest solution to underdetermined linear systems of equations), then this blog entry is for you.
Here is a list of current solvers written in Python. As noted yesterday, while L1 solvers are OK to see "if compressive sensing work" on small problems, they become slow when it comes to larger ones. For that you really need to look at the AMP solvers I mentioned yesterday. Hence I am also adding another list of solvers that ought to be implemented because:they are among the most optimal and their coding complexity is very much reduced compared to earlier solvers. 

An element of the compressive sensing framework relies on the building of dictionaries from training signals, for that there is:
Please also note that a C++ implementation of several solvers in KL1P (incuding AMP solvers). Here are the list of algorithms that ought to be implemented in Python or other languages:
GAMP mostly because this is an AMP solver that is continually supported by several researchers, Turbo AMP for imaging seems to do weill for images, SL0 because it is very simple in terms of coding complexity and BSBL as it seems to provide good results even when the signals are not sparse. If you do implement any of these algorithms please do let me know and I'll feature them on the blog and the big picture.
Image Credit: NASA/JPL/Space Science Institute
W00077074.jpg was taken on November 21, 2012 and received on Earth November 23, 2012. The camera was pointing toward SATURN at approximately 1,136,886 miles (1,829,640 kilometers) away, and the image was taken using the CB2 and CL2 filters. 

Join our Reddit Experiment, Join the CompressiveSensing subreddit and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.


Nicolae Cleju said...

Some Python solvers that I "translated" from the original Matlab functions, including SL0, can be found here:

They are usable but not thoroughly tested, but could at least be used as a starting point.

Also, I think the scikit-learn Python package has some OMP and dictionary learning algorithms.

Igor said...

Thanks Nicolae,

I have added your package to the list. Thanks.

Please note that the greedy algorithm (GAP and OMP), while of reduced complexity and faster than BP, are less interesting than AMP and other solvers I mentioned in the blog entry.

Thanks again!


Anonymous said...

I am a bit late to the party as this is an old post, but I just stumbled upon it and want to mention that there are also Python implementations of IHT, SL0, and an improved version of SL0 in this software package by some students of mine: