On the exact minimization of saturated loss functions for robust regression and subspace estimation
This addresses computational bottlenecks in robust regression and subspace estimation for applications requiring outlier-resistant models.
The paper tackles the computational complexity of minimizing saturated loss functions for robust regression and subspace estimation, showing that an exact algorithm with polynomial time-complexity can be devised. Experiments demonstrate it offers an accuracy gain over traditional RANSAC while maintaining similar algorithmic simplicity.
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.