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

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Does anyone know of a good l1-solver?*From*: Rodrigo Benenson <rodrigo.benenson@xxxxxxxxx>*Date*: Tue, 17 Apr 2012 15:32:03 +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:content-transfer-encoding; bh=9Tq3oKr3c0jw59+bZp73UbU38e12i5+at86xVJoDqeQ=; b=QD/pmg0EnOQx/5lJtAan7zgHtzELNbliKq1calG6pfNHaQYe44i//D0WO2NxSk1fQv v8okvZcd4h9YfcpRIJ1++rILsv+e2Mw+e6a5ud/Mzo9hmqVqIr60f37MCoqfHcrfZjl2 DFAmiRN5iz+BfFdx9f7Xrw1IjVk0pPL5gBqC+u5PYALk9WmdAqpX1MsANcg6zJBw1vKp U+LfoxcJocIWs8K8tU6qV2cp+obmuzjOP5xBqX6zjWe++qsv1gNAqvMh0hX31gfHC66J AEJAqqWmwCnHkADF9Yzm/m2w5seoh1e/oeiFD8/6mXMNGF0j8jbakLgEnRM8Bzle7RCG 0bOg==

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 > >

**References**:**[eigen] Does anyone know of a good l1-solver?***From:*cr.anil@xxxxxxxxx

**Re: [eigen] Does anyone know of a good l1-solver?***From:*Helmut Jarausch

**Re: [eigen] Does anyone know of a good l1-solver?***From:*Markus Moll

**Re: [eigen] Does anyone know of a good l1-solver?***From:*Christoph Hertzberg

**Re: [eigen] Does anyone know of a good l1-solver?***From:*cr.anil@xxxxxxxxx

**Re: [eigen] Does anyone know of a good l1-solver?***From:*Márton Danóczy

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Does anyone know of a good l1-solver?** - Next by Date:
**[eigen] Re: Does anyone know of a good l1-solver?** - Previous by thread:
**Re: [eigen] Does anyone know of a good l1-solver?** - Next by thread:
**[eigen] Re: Does anyone know of a good l1-solver?**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |