Pages

Monday, June 23, 2008

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.

2 comments:

  1. The new documentation features in MATLAB are indeed great, and go a long way toward making MATLAB useful as a Knuthian Literate Programming environment.

    For all us open-source/literate programming devotees (meaning ... both of us?), might I commend the open-source literate programming environment NuWeb?

    NuWeb works well for writing and documenting all kinds of code (C, Mathematica, MATLAB, Python, etc.)---especially projects that mix-and-match several languages within one overall project.

    It is a great advantage that NuWeb is feature-poor ... hence not closely tied to any one language.

    I use Mathematica (with a custom NuWeb style) as a WYSIWYG text editor for NuWeb ... the Mathematica notebook extracts itself to a NuWeb file ... then "make" handles the unweaving of the NuWeb file into executables in the various languages, as well as compiling the overall (LaTeX) document.

    This approach allows blending of symbolic and numeric coding very conveniently, without requiring commitment to any one language ... and the final documentation looks *great*.

    ReplyDelete
  2. John,

    This looks good. However, I am more a windows person and it doesn't look like it works for that OS :-(

    Igor.

    ReplyDelete