On the exact minimization of saturated loss functions for robust
  regression and subspace estimation
  This paper deals with robust regression and subspace estimation and more
precisely with the problem of minimizing a saturated loss function. In
particular, we focus on computational complexity issues and show that an exact
algorithm with polynomial time-complexity with respect to the number of data
can be devised for robust regression and subspace estimation. This result is
obtained by adopting a classification point of view and relating the problems
to the search for a linear model that can approximate the maximal number of
points with a given error. Approximate variants of the algorithms based on
ramdom sampling are also discussed and experiments show that it offers an
accuracy gain over the traditional RANSAC for a similar algorithmic simplicity.
