08-10 Linear least squares

Roughly a month ago I started reading about trilateration. Since then I haven't done anything really. The focus of my work today is to get back on track and start solving problems.

Since I took a lot of time off for vacation and real school is starting again, I feel under pressure time-wise to stay on schedule. I have two weeks of time alotted for trilateration, so I have to deliver a solution quite soon. According to "Statistical Methods in Surveying by Trilateration", a nonlinear least squares regression calculator performs the best in trilateration. Based on this I will focus my efforts on this approach.

An article from the MIT explains the way of solving things quite nicely, the formulas are available on the webpage. In layman's terms, I have three beacons with three corresponding distances between them and the blind node. The idea is to try out different X and Y that supposedly specify the position of the blind node until a minimum squared error is attained. The way that the optimal X and Y coordinates are found using this "trial and error" system vs directly calculating them with a linear regression system can be done in a few different ways.

Problem

Nonlinear regression seems very tricky to implement by myself. I now have to consider my options for doing it by myself or using some outside help.

Solution

Doing it by myself

There are three predominant algorithms for finding appropriate X and Y coordinates to find a local minima of a function. According to the National University of Singapore and a professor at Duke University, the Levenberg-Marquardt method is the best. It combines the best features of the Gauss-Newton and the Gradient Descent methods. The issue is that the LM method is way more complicated, so if anything I would just do the Gauss Newton or Gradient Descent version.

I find it quite hard to guess how hard it actually will ultimately be. I found some Gauss-Newton implementations in Python online, but they are also based on sublibraries (numpy) and cannot be translated to PHP directly.

PHP library

There is a PHP abstract class put online by Andrew Que via http://gaussnewton.drque.net/ that can be extended with a nonlinear function to be optimized. It hasn't been maintained since 2013 and is thus probably riddled with PHP 7.4 compatibility issues. There is also RubixML which implements a "gradient boost" class . Apart from the similar name, gradient boosting probably will not do much good since it does not tweak parameters, it tweaks the entire loss function. RubixML implements all sorts of other nonlinear regression methods, most of which I have no idea about. As the name of the library suggests, the approach is primarily machine learning based. This means that it relies primarily on identifying patterns in existing training data (distances, rssi) that is mapped to a given outcome (position x/y coordinates) through inference. Unless I create a training rssi data set at given x and y coordinates, I fear that this is quite useless since I have taken a different, more deterministic and explicit approach from the beginning.

Python libraries

SciPy implements various optimization functions such as scipy.optimize.least_squares that implements the Levenberg Marquardt method on a given function. Conveniently I would not have to implement the algorithm myself.

Further actions

My decision is to move forward with the python option. For complex math operations PHP is simply not enough. Every programming language has an optimal use case and calculus is not the intended purpose of PHP. Therefore in my eyes it does not make sense to try and use it for my trilateration system.

Redis can bridge the gap between PHP and Python on the localhost, the REST API can publish the data via a redis pub-sub channel. Redis-py implements a redis protocol compliant client that can subscribe to the latest distances. Python is available on docker and supports all the necessary ARM processor architectures. Ultimately I think it reduces complexity since I am using the most suitable tool for the issue instead of trying to use a website programming language to do complex math.

Since this is my first post after a long break, I also considered the roadmap. Based on previous research, it is either direct trilateration using NLLS regression OR kalman filtering. That means I have the next month to finish this chapter before I should start with a GUI or working on the report for schweizer jugend forscht.