Least squares for programmers

with illustrations

This repository contains the course notes as well as the source code for the long course I gave at SIGGRAPH 2021.

You can find the full video of the course on youtube:

This course explains least squares optimization, nowadays a simple and well-mastered technology. We show how this simple method can solve a large number of problems that would be difficult to approach in any other way. This course provides a simple, understandable yet powerful tool that most coders can use, in the contrast with other algorithms sharing this paradigm (numerical simulation and deep learning) which are more complex to master.

Linear regression is often underestimated being considered only as a sub-domain of statistics / data analysis, but it is much more than that. We propose to discover how the same method (least squares) applies to the manipulation of geometric objects. This first step into the numerical optimization world can be done without strong applied mathematics background; while being simple, this step suffices for many applications, and is a good starting point for learning more advanced algorithms. We strive to communicate the underlying intuitions through numerous examples of classic problems, we show different choices of variables and the ways the energies are built. Over the last two decades, the geometry processing community have used it for computing 2D maps, deformations, geodesic paths, frame fields, etc. Our examples provide many examples of applications that can be directly solved by the least squares method. Note that linear regression is an efficient tool that has deep connections to other scientific domains; we show a few such links to broaden reader's horizons.

This course is intended for students/engineers/researchers who know how to program in the traditional way: by breaking down complex tasks into elementary operations that manipulate combinatorial structures (trees, graphs, meshes...). Here we present a different paradigm, in which we describe what a good result looks like, and let numerical optimization algorithms find it for us.