|Re: [eigen] Does anyone know of a good l1-solver?|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Does anyone know of a good l1-solver?
- From: Márton Danóczy <marton78@xxxxxxxxx>
- Date: Tue, 17 Apr 2012 15:27:15 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=9y3ejJtDUJSBeTRfqniipAr5zkdhT6UmpG2czLTDUfo=; b=dCXnhysHiWuluWf4bGLwWcy451EQ29NBIOjEdzDvYpvJgh3f5tDSxouYBQZj0w/HE0 4TdKmRyqdZrgayXZSiV6vhlF5HOboijHGaiujaQoMsTaipbAOQAxwsxMmX4Of7w5ljtJ pyqpiAcjU/96VksWrJYchUDhBlJ+sEX/BROs+MIjNu9b2lBZ8a10M+vBElOMONGSHUhY uGgW7E1zVrZTTdbgfQ6/J9zvxbHooSRIFLi45SMxUjsU73OqN7gI+Szw/Xip3kxJKUj+ TnqE0/ZHC64g1SzzvbX0nrSOGqtwqWDHwT6QFkIzoBIe/hGg9++oWswHfjcjlPXheTcy Bktg==
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  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 , 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.
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.