Re: [eigen] New Levenberg Marquardt stuff

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

Regarding the scope of Eigen, I think that restricting it to linear algebra only would be quite boring. I like to define Eigen as unified, simply to use numerical toolbox for scientists. Just like the Eigen's website says:

"Eigen is a C++ template library for linear algebra: matrices, vectors, numerical solvers, and related algorithms."

this obviously includes linear algebra, but not only. Of course, implementing the whole literature on non linear optimization algorithms would be overkill. Eigen should provide all the building blocks to enable users to quickly and elegantly implement their own customized high level solvers. However, there exist a few non-linear optimization procedures which are extremely frequent and parts of these "building blocks".. In my opinion, the LM algorithm is one of them, and I'm also thinking about LP and QP solvers.

Actually, with a good "base", such algorithms are much simpler than advanced sparse direct linear solvers. For these later, it would be out of the scope of Eigen to implement a full featured, parallel, CUDA-enabled sparse LU/Cholesky solver. Instead, we implemented more basic, but still quite efficient built-in versions together with wrappers to existing advanced solvers for advanced users.

For the few non-linear optimization algorithms that I'd like to see in Eigen, we could imagine the same approach: a built-in lightweight implementation that an Eigen user can learn and use in 5 minutes, together with wrappers to the most advanced external libraries. This way, one (e.g., a Matser/PhD student) can very quickly test his ideas and when comes the need of more advanced features, wrappers are available to assist him.

As long as the built-in non-linear solvers are very lightweights, I don't really see the need to create a new project for them. Recall that since Eigen is header only, as long as a user do not #include <Eigen/Sparse>, then the compiler will never see the sparse related code. So for him the presence of sparse code only occupies a few KB on his hard drive but has zero effect on the compilation time or size of his/her binaries. Same for any additional module.

It is also interesting to have a quick look at the sizes of some modules:

- Eigen (all): 3.7MB

- SparseLU: 164KB (compared to 2MB for the original SuperLU code, and Eigen's version is even faster)

- LevenbergMarquart: 40KB (ceres: 3.3MB, original cminpack: 500KB)

- Eigen's products (gemm, gemv, trmm, trsv, etc.): 356KB (much more than LM !!)

 

gael

On Sat, Dec 8, 2012 at 8:23 AM, Sameer Agarwal <sameeragarwal@xxxxxxxxxx> wrote:

On Fri, Dec 7, 2012 at 6:57 PM, Radu B. Rusu <radu.b.rusu@xxxxxxxxx> wrote:

Dear Sameer,

Is there a particular reason why you'd like to remove the current LM implementation that Eigen has from the library? We have been using it for a long time, and are quite happy with it. There might be other implementations which are better, but there are use cases where the number of dependencies has to be very low, and one of our applications fits perfectly in this scenario. Eigen has a proven track record of being cross compilable on all the architectures that I can think of, with excellent unit tests, documentation, and really a fantastic user support, while other libraries are/do not. I'm bowing my hat every time I have a chance to the Eigen team, as they are an inspiration for other open source movements such as ours.

I am a huge fan of Eigen. But it is a question of scope. The arguments that you are making are arguments in favour of a simple to use and well crafted nonlinear least squares library, but not necessarily in favour of keeping one inside Eigen. Unless of course the plan is to turn Eigen into a general purpose numerical analysis library. 

I know Keir's original email mentioned Ceres so this may come across as self serving, but let me say this quite clearly and I know Keir will agree with me -- this is not about promoting one solver over another, but just addressing the issue as to what are the boundaries of a linear algebra library. I for one would not like to see more solvers in Eigen. I'd rather Eigen focus on on providing exceptional support for various advanced linear algebra algorithms.  

I think we can all agree that what Eigen did in the past few years changed the game completely for us C++-ers, as they made us move away from that ugly C code that we were using in the past while dealing with matrix operations / decompositions. That being said, I'd be more happy to see more solvers available in Eigen, either as part of the core or maybe the Eigen maintainers/developers can start adding additional modules ("libraries") alongside the core that deal with non-linear LS solvers. If there is code in CERES that is generally purpose and fits in the Eigen paradigm, it would be great to have it included it there. Why not have "libeigen-core", "libeigen-nonlinear", etc if adding more to the existing Eigen library is a problem?

Your argument essentially boils down to -- eigen is awesome.  we need X, so lets add X to eigen, and X will be awesome too.

I strongly disagree with this point of view.

Sameer

On 12/07/2012 03:07 PM, Sameer Agarwal wrote:

Dear  Christoph,
I think that discussion about releasing ceres is best had elsewhere rather than the eigen mailinglist.

        Have you considered punting on the LM library entirely?

        Ceres is almost uniformly better than what's there now, is heavily battle
        tested in production both large (Street View) and small (Android, in every
        Nexus 4), is BSD licensed, uses Eigen internally, has extensive sparse
        support.


    Well, it might use Eigen internally, but ceres' interface dealing a lot with double-pointers is far away from the
    clearity of Eigen ...

        It's not clear that Eigen dev's time is best spent working on LM when Ceres
        exists.

    As mentioned already by others, Eigen's LM module existed way longer than Ceres, and there existed a bunch of LM
    implementations before that.
    Furthermore, I agree with opinions raised by others that including a generic non-linear LS solver into Eigen
    might/should not be the goal of Eigen, which IMHO should basically be a *linear* algebra package.
    As long as no further dependencies are introduced (neither for compiling nor for licensing), I don't mind if some
    small extensions are added, though (clearly not the case for ceres having 2--5 more dependencies).


Keir and I are arguing exactly that, please do not add more stuff into eigen which has nothing to do with linear
algebra. We are not arguing for adding Ceres to eigen, but to remove nonlinear optimization code from eigen.

Sameer







    Christoph



    --

    ------------------------------__----------------

    Dipl.-Inf. Christoph Hertzberg
    Cartesium 0.049
    Universität Bremen
    Enrique-Schmidt-Straße 5
    28359 Bremen

    Tel: +49 (421) 218-64252 <tel:%2B49%20%28421%29%20218-64252>
    ------------------------------__----------------