Investigate improvements in tiny_nnls_solver fork of Tiny Solver

[keir]

See https://github.com/Edwinem/tiny_nlls_solver/issues/1

They have added some interesting stuff like hessian support. It could be interesting to incorporate some of these changes in upstream.

[Edwinem]

Hey Keir,

Sorry I have been roadtripping across the US for the last 3 months and just now am reconnecting with the outside world. Anyways I would be happy to contribute my modifications back to Ceres upstream.

I would like to seek your opinion on the design of some of the extra features I added.

The 4 main modifications I would say are:

1. Different minimizers such as GN and Dogleg.
2. A bit better error handling.
3. Ability to generate Hessian in the cost function.
4. Addition of a parameterization function to increment the estimated value properly.

1,2 are straightforward to implement, and I will start putting together a pull request for Ceres over the next few weeks.

3 I implement right now with some template metaprogramming and is in my opinion quite ugly. I also don't know what will happen if you implement a normal functor and a hessian based one.

Possible solutions are as follows:

• Keep as is.
  • Requires template metaprogramming hack.
  • Possible compiler error.
  • Keeps everything as a single unit.
• Try to extract most of the functionality into one class/function and then have two separate solver classes: one for Hessian based cost functors and one for the standard method.
  • Increases number of classes.
  • No longer 1 do it all solver.
  • May require virtual functions which increase overhead, which for this tiny solver we might want to avoid.

4 I still need to think about cause I am not happy with the current solution I have which is to add another template parameter to the solver.

Anyways I'll try and slowly get started on creating a pull request for 1,2 on Gerrit and let me know what opinions you have on features 3,4.

[sandwichmaker]

@Edwinem (1), (2) and (4) will improve things while keeping the current semantics. (3) I am hesitant to add. I look forward to reviewing your code!

[sandwichmaker]

gentle ping?

[versatran01]

TinySolver may be missing a few noalias() calls.

194  jtj_ = jacobian_.transpose() * jacobian_;
195  g_ = jacobian_.transpose() * error_;
241  dx_ = jacobi_scaling_.asDiagonal() * lm_step_;

I would also like to propose a small change to TinySolver, which is to allocate storage using std::vector and use Eigen::Map. It looks roughly like this

void Initialize(int num_residuals, int num_parameters) {
    const int num_jacobian = num_residuals * num_parameters;
    const int num_hessian = num_parameters * num_parameters;
    const int total = num_parameters * 6 + num_residuals * 2 +
                      num_jacobian * 1 + num_hessian * 2;
    storage_.resize(total); // std::vector<Scalar>
    auto* s = storage_.data();

    new (&dx_) Eigen::Map<Parameters>(s, num_parameters);
    // More 

I can do a PR if you think this is useful.

[sandwichmaker]

I'd like to understand, why do you think we are missing some noalias calls? also I do not understand the reason for your proposed use of std::vector for storage. Could you elaborate, what problem you are trying to solve?

[versatran01]

If I remember correctly, matrix multiplication in Eigen assumes alias by default, so adding noalias() to those lines could avoid evaluating into a temporary matrix. For example https://github.com/ceres-solver/ceres-solver/blob/2a2b9bd6fa2a0ee62f58dceb786cb2dc3eb37630/internal/ceres/schur_eliminator.h#L505

For vector storage, it is not trying to solve any problem, it's just a small performance improvement. Whereas before, if a reallocation is needed, all those members will be allocated separately and there's no guarantee where they will end up in memory whereas the proposed change will just do it once. It is also possible to set a max size if one knows in advance the maximum number of residuals and parameters, thus even if the number of residuals changes between calls, as long as it is within the max size, there will only be one allocation on initialization.

Related issue #350

[versatran01]

Here is my proposed change https://github.com/versatran01/nano_solver

The change is in the Initialize() function. I made the solver non-template since I want better compilation time in my own project, which is NOT part of the change that I propose here.