Random sample consensus

Random sample consensus (RANSAC) is an iterative algorithm to estimate parameters of a model.

The idea is to continuously randomly sample a subset of your data.
For each subset, you build a model and do cross-validation until you find a model with sufficiently small error. You quit after \(\displaystyle k\) iterations or once your model has sufficiently low error.

This is commonly used when you have a lot of points and building a model is worse than \(\displaystyle O(n)\).
An example is if you need to do least squares minimization or calculate an SVD to build your model.
In this case, it is more efficient to build several models using a small subset of the points and pick the best model.

Algorithm

Copied from Wikipedia: Random sample consensus

Given:
    data – A set of observations.
    model – A model to explain observed data points.
    n – Minimum number of data points required to estimate model parameters.
    k – Maximum number of iterations allowed in the algorithm.
    t – Threshold value to determine data points that are fit well by model.
    d – Number of close data points required to assert that a model fits well to data.

Return:
    bestFit – model parameters which best fit the data (or nul if no good model is found)

iterations = 0
bestFit = nul
bestErr = something really large

while iterations < k do
    maybeInliers := n randomly selected values from data
    maybeModel := model parameters fitted to maybeInliers
    alsoInliers := empty set
    for every point in data not in maybeInliers do
        if point fits maybeModel with an error smaller than t
             add point to alsoInliers
    end for
    if the number of elements in alsoInliers is > d then
        // This implies that we may have found a good model
        // now test how good it is.
        betterModel := model parameters fitted to all points in maybeInliers and alsoInliers
        thisErr := a measure of how well betterModel fits these points
        if thisErr < bestErr then
            bestFit := betterModel
            bestErr := thisErr
        end if
    end if
    increment iterations
end while

return bestFit