Skip to main content
So far in this book you have fitted models with stochastic gradient descent (SGD). That is the approach the neural network chapters build on, because a network has many parameters and is trained on a large data set. Many estimation problems in robotics and computer vision look different. They have tens to thousands of measurements and a handful of parameters. For those problems the standard tool is least squares: setting the gradient of the squared error to zero gives the normal equations, and solving them gives the exact minimizer in one step, without a learning rate. Least squares by itself is a fitting criterion. It picks the parameters that minimize the sum of squared residuals and says nothing about probability. It has a probabilistic reading only when you add a model of the noise. If the residuals are independent and Gaussian with a common variance σ2\sigma^2, the least squares solution is the maximum likelihood estimate, as the conditional maximum likelihood section shows, and its covariance is σ2(Φ⊤Φ)−1\sigma^2(\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}, which a filter or a planner can use. The methods of this chapter rely on that reading. The RANSAC threshold and the inlier and outlier mixture both come from a Gaussian model of the inlier noise, and each robust loss corresponds to a noise distribution with heavier tails than the Gaussian. The table lists places where least squares is used, and the sections of this book that cover them. Least squares gives every measurement the same weight and penalizes the square of its residual, so a few wrong measurements can move the fit far from the truth. This chapter starts from the least squares fit of a line and shows how one bad point moves it. It then covers the methods that limit that damage. Robust losses and the inlier and outlier mixture reweight the data around a current fit. RANSAC needs no starting fit and finds the inliers by fitting many small random samples.

Least Squares with Outliers

The least squares baseline, leverage, robust losses and the inlier and outlier mixture.

RANSAC

Fitting minimal random samples and keeping the largest consensus set.

RANSAC Applications

A floor plane in a point cloud and the settings of a homography estimate.
Found an error on this page? Report an issue.