Parallel calculation of the median and order statistics on GPUs with application to robust regression
For practitioners needing fast median/order statistic computation on large datasets using GPUs, this work offers a more efficient method, though it is an incremental improvement over existing GPU-based selection algorithms.
The paper introduces a new method for calculating order statistics (specifically the median) on GPUs, based on convex function minimization, and demonstrates its numerical superiority for very large arrays. It also applies this method to efficient parameter estimation in high-breakdown robust regression.
We present and compare various approaches to a classical selection problem on Graphics Processing Units (GPUs). The selection problem consists in selecting the $k$-th smallest element from an array of size $n$, called $k$-th order statistic. We focus on calculating the median of a sample, the $n/2$-th order statistic. We introduce a new method based on minimization of a convex function, and show its numerical superiority when calculating the order statistics of very large arrays on GPUs. We outline an application of this approach to efficient estimation of model parameters in high breakdown robust regression.