residual minimization for a vector

[Athul Mathew]

Hello All,

I have a function which computes the residuals for a given set of input parameters. I want to minimize the residuals computed by the function using ceres.

I went through the tutorials and examples provided on-line to get started and I find that I need a cost functor that models each residual term. However I have a function already which computes the residuals ( 100 plus dimensional vector) and I just want to pass this function somehow to ceres to minimize the residuals.

In other words, I am looking for someway to replicate the below code snippet in MATLAB, on which we developed our prototype :

input_optim_flat = lsqnonlin(@(input_ls_test) nonlin_function_seg(input_ls_test, ...
        edge_points, ...
        edge_dir, next_segment, param, 'MATCH_POINTS'), ...
        input_optim_flat, [], [], options);


nonlin_function_seg is the function which takes in the parameters as inputs (90 dimensional vector ) and outputs the residuals.

I did try using AutoDiffCostFunction functionality of Ceres. However this does not compile. Could anyone guide me in the right direction of how to tackle this problem ? Maybe some documentation or examples on how to minimize the residuals computed from a user-defined function ?

Thanks and regards,
Athul.

[Sameer Agarwal]

Athul,

Does your function compute residuals or residuals and the jacobian? if the former, then wrap it in a NumericDiffCostFunction, if the latter, wrap it in a CostFunction object.

Ceres does not require you have a separate residual block for each residual. You can have a single residual block for all your residuals, especially if your residuals are dense in the parameters. Which it appears is the case here.

I can say more if you share the signature of your c++ function for computing the residuals.

Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/90e9ef3d-3d1f-4a8b-baa0-57d61996b7ee%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Athul Mathew]

Hello Sameer,

Thanks a lot for your quick response !

This is the signature of the function that I would want to integrate into ceres :

std::vector<double> nonlin_function_seg(std::vector<double>input, std::vector<std::vector<double> >  edge_points_new, std::vector<double> edge_dir_new,std::vector<std::vector<double> > next_segment_index);

For explanatory purposes, input is the parameters to be minimized and the function returns the residuals. In answer to your question, the function only computes the residuals.

I have used ceres with AutoDiffCostFunction when I had few parameters only to minimize and thus had individual residual block for every residual. I tried extending the same concept with some modification and tried something like mentioned below :


  Problem problem;
  problem.AddResidualBlock(new AutoDiffCostFunction<ComputeResidual,128, 90>(new ComputeResidual), NULL, &ri->input_optim_flat);

struct ComputeResidual {

 template <typename T> bool operator()( std::vector<T*> input_optim_flat, std::vector<T*> residuals)  {

   residuals = nonlin_function_seg(input_optim_flat);
//NOTE : I have not used other function parameters as  shown in the function signature as I have declared them public in my class and thus they are all accessible by my function
   return true;
  }

};
However, this does not seem to work. It would be great if you could give me some pointers on how to resolve this :)

Regards,
Athul.

[Sameer Agarwal]

Athul,

My comments are inline.

On Wed, Mar 9, 2016 at 7:56 AM Athul Mathew <athulma...@gmail.com> wrote:

Hello Sameer,

Thanks a lot for your quick response !

This is the signature of the function that I would want to integrate into ceres :

std::vector<double> nonlin_function_seg(std::vector<double>input, std::vector<std::vector<double> >  edge_points_new, std::vector<double> edge_dir_new,std::vector<std::vector<double> > next_segment_index);

A couple of questions

1. Can this function be templated? I am guessing not. That would be the only way you can use it for automatic differentiation.

2. If not, then you will need to wrap it using NumericDiffCostFunction. So as long as you can implement a functor which wraps this function and just returns the residuals and let ceres numerically differentiate it.

Your signature of the functor below is incorrect, you will have to follow the tutorial to get it right.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/10a06eec-cc1f-4489-8fdc-9c3a5a8dba48%40googlegroups.com.

[Athul Mathew]

Hello Sameer,

I wrapped my function with NumericDiffCostFunction as you had suggested and it does compile fine now :)

However, I get some run-time errors now.
This is the summary report :

Solver Summary (v 1.11.0-eigen-(3.2.0)-lapack-suitesparse-(4.2.1)-openmp)

                                     Original                  Reduced
Parameter blocks                            1                        1
Parameters                                 90                       90
Residual blocks                             1                        1
Residual                                  128                      128

Minimizer                        TRUST_REGION

Dense linear algebra library            EIGEN
Trust region strategy     LEVENBERG_MARQUARDT

                                        Given                     Used
Linear solver                        DENSE_QR                 DENSE_QR
Threads                                     1                        1
Linear solver threads                       1                        1

Cost:
Initial                         -1.000000e+00

Minimizer iterations                        0
Successful steps                            0
Unsuccessful steps                          0

Time (in seconds):
Preprocessor                           0.0000

  Residual evaluation                  0.0000
  Jacobian evaluation                  7.1724
  Linear solver                        0.0000
Minimizer                              7.1724

Postprocessor                          0.0000
Total                                  7.1725

Termination:                          FAILURE (Residual and Jacobian evaluation failed.)


I see that the Residuals are shown to be uninitialized. However my function does return the residuals to and assigns it. The problem definition and functor signature is as shown below :

Problem problem;
CostFunction* cost_function = new NumericDiffCostFunction<ComputeResidual, CENTRAL, 128, 90> (new ComputeResidual);
problem.AddResidualBlock(cost_function, NULL, input_optim_func);

struct ComputeResidual {
bool operator()(const double* const input_optim_func, double* residual) const {

//some addtional code here
residual = rt->nonlin_function_segment_joint_match_points(input_optim_func);
return true;
}
};

Below is my function defintion :
double* nonlin_function_segment_joint_match_points( const double*  input);

Could you provide me with some suggestions on this ?

[Sameer Agarwal]

run your program with -v=3 -logtostderr it should show you where your evaluation is failing.

also how are you assigning to residual? it is a pointer. You should be copying values into the residuals array.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/1e04a82c-51c8-4ce3-8d72-d8d656d8e836%40googlegroups.com.

[Athul Mathew]

Hello Sameer,

Thanks for your help and advice until now. It is really appreciable :)

My problem now converges with no errors.

However, I have the following issues :

1. The solver takes too long to be run in real-time

2.Some of the optimized parameter values are way out of bounds in comparison to the initial parameters values passed to the function. One logical solution I felt would work was to set upper and lower bounds to the problem since I have an idea of the limits to be assigned to parameters. However Ceres does not seem to obey the bound constraints that I set.

Is there something I am missing since the parameters are not converging to the expected values nor stays within the bounds that I manually set  ?

Regards,
Athul.

[Sameer Agarwal]

1. The solver takes too long to be run in real-time

Please share the output of Solver::Summary::FullReport(). It is likely that you are have one large residual which you are numerically differentiating which is costing you all the time.

 

2.Some of the optimized parameter values are way out of bounds in comparison to the initial parameters values passed to the function. One logical solution I felt would work was to set upper and lower bounds to the problem since I have an idea of the limits to be assigned to parameters. However Ceres does not seem to obey the bound constraints that I set.

Please share the code to show how you are setting the bounds constraints.

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/b103f1c9-56e0-4022-a8a2-a4f30b9995a5%40googlegroups.com.

[Athul Mathew]

Hello Sameer,

Find the summary report below :

Solver Summary (v 1.11.0-eigen-(3.2.0)-lapack-suitesparse-(4.2.1)-openmp)

                                     Original                  Reduced
Parameter blocks                            1                        1
Parameters                                 90                       90
Residual blocks                             1                        1
Residual                                  128                      128

Minimizer                        TRUST_REGION

Sparse linear algebra library    SUITE_SPARSE

Trust region strategy     LEVENBERG_MARQUARDT

                                        Given                     Used

Linear solver          SPARSE_NORMAL_CHOLESKY   SPARSE_NORMAL_CHOLESKY

Threads                                     1                        1
Linear solver threads                       1                        1

Cost:

Initial                          1.824092e+00
Final                            1.572026e+00
Change                           2.520653e-01

Minimizer iterations                       18
Successful steps                            7
Unsuccessful steps                         11

Time (in seconds):
Preprocessor                           0.0001

  Residual evaluation                  0.0770
  Jacobian evaluation                 20.7370
  Linear solver                        0.0459
Minimizer                             20.8605

Postprocessor                          0.0000
Total                                 20.8606

Termination:                      CONVERGENCE (Function tolerance reached. |cost_change|/cost: 1.440264e-07 <= 1.000000e-06)



To add upper and lower bounds, I just added this ( since it is reasonable to assume all values of my parameters vector to lie between 0 and 200 ) :

 Problem problem;
CostFunction* cost_function = new NumericDiffCostFunction<ComputeResidual,CENTRAL,128, 90> (new ComputeResidual);

problem.AddResidualBlock(cost_function, new ceres::CauchyLoss(0.5), input_optim_func);
problem.SetParameterLowerBound(input_optim_func, 0, 0.0);
problem.SetParameterUpperBound(input_optim_func, 0, 200.0);


Regards,
Athul.

[Sameer Agarwal]

Athul,
As you can see all the time is going in Jacobian evaluation. You need to make your function use analytic or automatic differentiation.

This problem is made worse by adding bounds constraints which require more derivative evaluations.

As for the bounds constraints, the two calls you made only set the first componenent of your parameter block to the bounds constraints you also need to set bounds constraints on the rest of the components.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/e8392d34-0658-4651-b94e-40de69957385%40googlegroups.com.

[William Rucklidge]

You need to call SetParameterLower/UpperBound once for each parameter, not once for the parameter block as a whole. What you've done is tell it that the first parameter must be between 0 and 200.

for (int i = 0; i < 90; i++) {

  problem.SetParameterLowerBound(input_optim_func, i, 0.0);

  problem.SetParameterUpperBound(input_optim_func, i, 200.0);

}

As Sameer said, you've got a length 128 residual vector, with 90 parameters as input. Using numerical differentiation means that to work out the Jacobian your cost function needs to be invoked several hundred times - which you can clearly see in the full report:

  Residual evaluation                  0.0770

  Jacobian evaluation                 20.7370

  Linear solver                        0.0459

Minimizer                             20.8605

Almost all of the time is spent in Jacobian evaluation.

If you can convert to automatic differentiation, you may see a speedup - but even then, Ceres doesn't know the structure of your cost function and so it needs to investigate the dependency of each residual element on each parameter (i.e., it has to allow for your Jacobian being dense), so it will still be pretty slow.

If not every residual depends on every parameter (i.e., if your Jacobian is not dense), then you can have a significant win by analytically computing the Jacobian. Unlike numerical or automatic differentiation, this involves writing new code.

And the best win of all is if you can break down the problem into smaller sets of residuals, each of which can depend on a subset of the parameters. This is possible if your Jacobian is block-structured. If you can do this, then you break up your single monolithic cost function into a bunch of smaller ones. With this approach, Ceres will be able to exploit the block structure of the problem for much more efficient operation. As an example, I often run problems with ~10 million residuals and hundreds of thousands of parameters - but because the problem breaks down into blocks the Jacobian is very sparse and Ceres knows that.

-wjr

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/e8392d34-0658-4651-b94e-40de69957385%40googlegroups.com.