Today, Sameer Agarwal and Keir Mierle (as well as a couple others I'm sure) at Google open sourced the Ceres Non-Linear Least Squares Solver.
Since coming to Google, this is probably the most interesting code library that I have had a chance to work with. And now, you can use it too. So, what exactly is a "non-linear least squares solver"? and why should you care?
It turns out that a solver like Ceres is at the heart of many modern computer vision and robotics algorithms. Anywhere you have a bunch of observed sensor data about the world and you want to create an explanation of all those observations, a non-linear least squares solver can probably do that for you. For example, if you have a bunch of distance sensors and you want to figure out where you are relative to the walls. Like this:
Or if you have a camera, and you want to figure out the position of the camera and objects in view:
Or say you have a quad copter, and you want to model how it will respond to thrust on different propellers:
or (as in the case of Google Street view) combining vehicle sensors in the cars with GPS data:
or even figure out the best way to position your plant so it gets the most amount of sun (assuming you could accurately measure the amount of sun hitting the leaves):
Non-linear least squares solvers, like Ceres, are a tool for optimizing many variables simultaneously in a complex model/formula to fit some target data. Many of the advanced engineering problems today come down to this. It's basically a fancy version of your typical line fitting problem:
This is linear least-squares. The model here is:
This is "linear" because it is the simple addition of a scaled variable m*x and a constant b. It is "least-squares" because it minimizes the square of the distance between the line and each of the data points. In this simple case, that algorithm is simply solving for m and b in the line equation. There are methods for directly computing these values. But, if the equation was non-linear such as:
You now need a non-linear least squares solver. Many real world problems are non-linear such as anything that involves rotation, camera projection, multiplicative effects, or compounding/exponential behavior. You might be able to devise a clever way to calculate the optimal values for m and b directly, or you can use an iterative algorithm and let the computer tweak the values of m and b until the squared error to your data is minimized. While this example also only has two variables, Ceres can handle optimizing thousands of variables simultaneously and uses techniques for reaching an error minimizing solution quickly. Though, it's important to note that it can only iteratively crawl toward the lowest error solution starting from the initial values of m and b you provide... like a drop of water sliding down to the bottom of a bowl. If the bottom of the bowl is very bumpy, it can get stuck in one of the smaller divots and never reach the lowest part of the bowl. This is known as getting stuck in a "local minima" and never finding the "global minimum" and the shape of the bowl is called the "cost surface". When the cost surface of a problem is not very bowl-like, it can lead to problems.
Ceres can also handle something called "sparsity" efficiently. This occurs when you have many many variables, but only a few of them interact with each other at a time. For example, the current position of a flying quad copter depends on the previous position and previous velocity. But, the current velocity doesn't really depend that much on the previous position. Imagine if you made a giant table with all your input variables in the column names and all of your output values in row names and then put check mark in the table where ever the input was used to compute the output. If most of the table is empty, then you have a "sparse matrix" and Ceres can take advantage of this emptiness (which indicates independence of the variables) to dramatically increase the speed of computation.
Anywhere you that have data, and you have a model (which just a fancy term for complicated formula) that should be able to generate that data and you want to tweak the values inside your generative model to best fit your data... a tool like Ceres might do the job.
For many problems, mathematicians and engineers have spent decades devising clever and complex formulas to solve them directly. But in many fields, having a computer perform non-linear optimization on data is becoming the preferred method because it makes it much easier to tackle very complicated problems with many variables, and often the result can be more stable to noisy input.
The neat thing about using a non-linear solver in a real-time system, is that the computer can respond to feedback in much the same way you do. If an object is too far to the left of a target position, it knows to move it right. If the wind starts blowing, and it drift backwards it will automatically respond by pushing forward. As long as you have an equation to explain how the output will be affected by the controls. It can figure out the best way to fiddle with the controls to minimize the distance from a target value.
If I find the time, I might try to post some tutorials on using Ceres. Because I believe this is one of the most powerful tools in modern engineering, and no one ever taught it to me in undergrad or high school. It's like the difference between doing long division by hand and then being handed a calculator.
Posts
