Re: [eigen] Does anyone know of a good l1-solver?

[Rodrigo Benenson <rodrigo.benenson@xxxxxxxxx>]

I would be certainly interested on an eigenified version of libBFGS.
If not in Eigen/unsupported could you share the code in a public repository ?

Best regards,
rodrigob.

On Tue, Apr 17, 2012 at 3:27 PM, Márton Danóczy <marton78@xxxxxxxxx> wrote:
> Hi Anil,
>
> you mentioning L1 magic and primal-dual solvers makes me guess that
> you actually want to solve argmin ||Ax-b||^2_2 + a ||x||_1? That is,
> quadratic loss with L1-penalty, aka LASSO? In this case, I can
> recommend the orthant-wise limited-memory quasi-Newton (OWLQN)
> algorithm. Actually, it can solve f(Ax-b) + ||W x||_1, where f is a
> smooth convex loss and W is diagonal. There is a good implementation
> as part of the libBFGS [2] library. I have taken this implementation
> and eigenified it, if you (or somebody else) is interested, I can send
> it per Email. Or even push it to Eigen/unsupported? I have used it
> from MATLAB in the past (there's also a mex file wrapper) and found it
> to work ok, as long as there are not too many variables (then,
> convergence can be slow). A better behaved method is DAL [3], however,
> to my knowledge, there is only a MATLAB implementation.
>
> In case your loss function is really 1-norm, I think the standard
> method is called "column generation" but I have never used it.
>
> [1]: http://nlp.stanford.edu/~pupochik/papers/andrew07scalable.pdf
> [2]: http://www.chokkan.org/software/liblbfgs/
> [3]: http://www.ibis.t.u-tokyo.ac.jp/ryotat/dal/
>
> HTH,
> Marton
>
> On 17 April 2012 14:38, cr.anil@xxxxxxxxx <cr.anil@xxxxxxxxx> wrote:
>>> Either that, or maybe find x, s.t. ||Ax - b||_1=min ?
>>>
>> Yes this is what I want to solve although I want to add a l2 regulariser
>> sometime later to this.
>>
>>> Do you know anything about A? (sparse, square, symmetric, rank-deficient,
>>> ill-conditioned, ...)
>>>
>> No. A is a dense matrix and full rank but I do know that it has 6 columns
>> and 3N rows.
>>
>>> Anyways, afaik, Eigen itself does not provide L1-solvers, so you need to
>>> find an external library anyways (or find an algorithm and implement it). It
>>> is quite easy to interact with other libraries by using Eigen's Map and
>>> .data() functionality.
>>
>> Hmmm... I thought it would be nice if there was a efficient library which
>> did this since I run the optimisation in a loop.
>>
>> Also is the primal dual technique the most efficient for this problem?
>> That's what I found in a matlab library called l1 magic.
>>
>> Anil
>
>