CS: LASSO algos, Comparison between SPGL1 and Bregman.

Jort Gemmeke pointed me to the page of Mark Schmidt who made available about 15 different algorithms solving the LASSO problem. When I asked Michael Friedlander about how these algorithms mapped into the ones currently implemented in SPGL1. Here is what he responded:

I'm glad to see that Mark still has his solvers up on the web. He wrote these as part of his project for my graduate course in numerical optimization. We were mainly interested in getting a feel for the various approaches, and were---or at least I was!---surprised to see so many variants.

Looking through Mark's m-files, I don't think there's much overlap. Both SPGL1 and Mark's "LassoConstrained" and "LassoActiveSet" m-files can solve the LASSO problem i.e. minimize ||Ax-b||_2 subj to ||x||_1 <= tau, but the algorithms are very different. I think that LassoConstrained implements Tibshirani's (1994) original suggestion which explicitly forms a series of linear constraints for the one-norm ball; "LassoActiveSet" implements some version of Osborne, Purnell, and Turlach's homotopy approach.

On a different note, within SPGL1, I noted the appearance of a great new page for examples which was produced using Matlab's publishing feature. As Michael noted, these features are " a great way to get documentation up on the web". Michael also mentions the following:

Yesterday I noticed that you mentioned the latest SPGL1 ..., and also L1-Bregman. About a month ago, ... I ran some benchmarks of the L1-Bregman code [for comparison with SPGL1]...The main difficulty I had was that the Bregman algo needs a certain parameter as input. But I gave up when I couldn't figure out how to systematically choose parameters so that the method would work on the various Sparco problems. Probably I don't understand their method well enough.

Anyway, in case you're interested, here's a set of scripts

http://www.cs.ubc.ca/~mpf/public/BregCompare.zip (73.7K)

that I just dusted off that compares L1-Bregman and SPGL1 on some of the test problems from the Bregman paper. The README in that directory gives a few lines of Matlab code that will run the comparison. (The script requires Sparco.)

This is one of the many reasons this blog exists, i.e. accelerating our collective understanding of the intricacies of specific approaches. Now if we could have this type of comparison with the proximal algorithms, it would be great. While I see that they provide some type of theoretical results on convergence, do we know for a fact that an algorithm based on proximity operators is fast ? (Reference: Applying the Proximal Point Algorithm to a Non Negative Basis Pursuit Denoising model by Francois Malgouyres, Tieyong Zeng. The attendant software is here.)

Credit: NASA/JPL-Caltech/University of Arizona/Texas A&M. Phoenix on Sol 25.