Wednesday, April 06, 2011

CS: Complex L1 Solvers

Mohammadreza Mahmudimanesh recently asked a good question on the LinkedIn group (there are now 801 members in that group!) about complex l1 minimization and attendant solvers. There were many insightful comments including one from Stephen Becker, here it is:
When we made the NESTA package, we specifically made sure it worked with complex numbers. I would recommend NESTA or TFOCS or SPGL1; they all work with complex numbers, and are all fast. Both CVX and CVXOPT are interior point method, so they don't scale to large problems well, but I use them for prototyping all the time.

If you need to avoid Matlab, then I would suggest implementing FISTA in whichever language you prefer, since this is a very nice yet still simple algorithm. You need to do continuation in order to make it fast though. For complex numbers, the key step is a complex shrinkage. You can look at the Matlab source code in NESTA, SPGL1 or TFOCS to see what the complex shrinkage algorithm should look like, and then port it to Python.

If you don't want to solve l1 minimization but just want to get something sparse, then you can try SL0, or try Iterated Hard Thresholding (IHT). The advantage of IHT is that it is very simple, so you can implement it in Python yourself.

Of interest is a resource that Stephen has made that lists most solvers used for sparse recovery and low rank matrices. It's a different resource than say the one in the Big Picture, my take is the more the better. Thanks Stephen for making this resource available! I'll add it in the Big Picture.

Personally, I have had fast and interesting results using SL0, SPGL1 when dealing with complex numbers.

Underlying there is, I think, a more generic question, are there implementation of solvers in languages other than Matlab. If you have an implementation that fulfills this conditions (of not being written in Matlab) please let me know. I am also a taker and will advertize your claim about running any solvers on Octave (instead of just Matlab).

Image Credit: NASA/JPL/Space Science Institute, W00066935.jpg was taken on March 19, 2011 and received on Earth March 21, 2011. The camera was pointing toward SATURN at approximately 551,664 kilometers away, and the image was taken using the CL1 and CL2 filters

No comments: