Computing the least quartile difference estimator in the plane

A common problem in linear regression is that largely aberrant values can strongly influence the results. The least quartile difference (LQD) regression estimator is highly robust, since it can resist up to almost 50%50% largely deviant data values without becoming extremely biased. Additionally, it shows good behavior on Gaussian data—in contrast to many other robust regression methods. However, the LQD is not widely used yet due to the high computational effort needed when using common algorithms. It is shown that it is possible to compute the LQD estimator for n   bivariate data points in expected running time O(n2logn)O(n2logn) or deterministic running time O(n2log2n). Additionally, two easy to implement algorithms with slightly inferior time bounds are presented. All of these algorithms are also applicable to least quantile of squares and least median of squares regression through the origin, improving the known time bounds to expected time O(nlogn)O(nlogn) and deterministic time O(nlog2n). The proposed algorithms improve on known results of existing LQD algorithms and hence increase the practical relevance of the LQD estimator.