1

Background:

I'm using non-linear least squares to solve indoor trilateration problem using BLE (bluetooth low energy) beacons. My starting point is this: https://nrr.mit.edu/sites/default/files/documents/Lab_11_Localization.html B part of the document.

(I've been using this JAVA lib for trilateration ( https://github.com/lemmingapex/Trilateration ) which works fine but needed to switch to c++ and I couldn't find a similar lib. So I experimented with google's ceres solver and eigen's levenberg-marquardt lib)

Problem/question:

$(x*,y*) = argmin \sum_{i=0}^n [ri^2-(x-xi)^2 - (y-yi)^2$

For these non-linear optimization libs, you have to define the nonsquared function.

Using this function for L-M algorithm: $\sqrt{(x-xi)^2 + (y-yi)^2} - ri$

c++ code:

fvec[i] = sqrt(pow(matrix(i, 0) - b[0], 2) + pow(matrix(i, 1) - b[1], 2)) - matrix(i, 2);

I get different results when using this: $1 - \frac{\sqrt{(x-xi)^2 + (y-yi)^2}}{ri}$

c++ code:

fvec[i] = 1 - sqrt(pow(matrix(i, 0) - b[0], 2) + pow(matrix(i, 1) - b[1], 2)) / matrix(i, 2);

The latter gives much better results. Shouldn't this function defined in different forms give the exact same result when using L-M algorithm to find minimum? What am I missing?

By the way for predefined problems (in the JAVA github lib tests) both give correct results, but the considerable difference happens when I'm testing with reallife data (many beacons).

Notes:

First defined function (fvec) returns RelativeReductionTooSmall and second (which gives good results) returns with RelativeErrorTooSmall. So I guess the stopping condition may not be set properly. But this shouldn't have an effect on my problem.

I'm new to optimization. I understand how gradient-descent works, but didn't have the time to dig deeper into L-M algorithm. I know it "balances"/switches between gradient descent and Newton-Gauss approach. But my gut says I'm missing something more basic.

I'm treating this function as an eqution (hence the above mentioned 2 forms): $0 = 1 - \frac{\sqrt{(x-xi)^2 + (y-yi)^2}}{ri}$ but maybe I can't treat the left side just as 0? Why not?

bartfer
  • 11

2 Answers2

0

It seems you missed a square, since the minimization problem refers to the function $$ \sum_{i=0}^n f_i(x,y)^2, $$ with $$ f_i(x,y) = r_i^2 - (x-x_i)^2 - (y-y_i)^2. $$

Rigel
  • 14,434
  • Yes that is missed on purpose. I mentioned in the question that "For these non-linear optimization libs, you have to define the nonsquared function.". So that's why I give the non-squared form. These libs (ceres, eigen) square it for you. Thanks for your answer though! – bartfer Jan 04 '21 at 16:20
  • But problem (2) of Ceres solver tutorial is exactly of the form that I've written above. As far as I can see, in your original problem you have the sum of the squares of the functions $f_i$, so there is no need to take a square root. – Rigel Jan 04 '21 at 16:25
  • Well I tried without square root as well before and it gives wrong results. But if I reorganize the function without square roots to the similar form of 1-[(x-x0)^2+(y-y0)^2]/r^2. I get good results. So the problem of the function's form can be seen here as well. Which is my question's goal. Strange thing is for some tests the squared and non-squared gives the exact same results, for some they differ and I have no idea why. – bartfer Jan 05 '21 at 10:41
  • 1
    It's not so strange. Looking at 1B in your document, your primary goal is to solve an exact system (with, due to measurement errors, could not have a solution). Then you "relax" the problem. In the first case (using the $f_i$ above) you are minimizing the sum of absolute errors in square distance, in the second case the sum of relative errors. I think you can also use other weights, based on your estimate "goodness" of the beacons. – Rigel Jan 05 '21 at 11:31
  • I understand what you mean. Thanks! For my original problem I found a similar question here: https://forum.kde.org/viewtopic.php?f=74&t=125563&hilit=levenberg but I'm calculating the jacobian automatically so I don't really understand what could be the reason for different results using different forms of the same function (just like in the linked example). "0" = a-b OR b-a="0" etc. why minimizing these give different results is what I don't understand. (so squaring is not the problem here as the lib squares automatically, so we just introduce 4th degree which results in more iterations) – bartfer Jan 05 '21 at 12:59
0

Q: "Shouldn't this function defined in different forms give the exact same result when using L-M algorithm to find minimum?"

A: Both forms of the function should work correctly. I tested both forms using java lib 1 2 and it's giving good results. So theoretically my assumption was correct. The form of the function to be minimized doesn't really matter(*). The problem most likely lies in the c++ libs that I tried out (eigen, ceres). (Or I'm not using those correctly.)

*Both forms don't give the exact same results (only very close) but I couldn't find out the reasons for that.

Followup question on stackoverflow if anyone is interested: https://stackoverflow.com/questions/65599497/what-is-this-strange-difference-between-c-eigen-levenberg-marquardt-and-java-l

bartfer
  • 11