Weighted median algorithms for \(L_ 1\) approximation (Q917229)

The weighted median problem consists of minimizing the function \[ f(x)=\sum^{n}_{i=1}w_ i| x-x_ i|,\quad x\in {\mathbb{R}}, \] where \(x_ 1,...,x_ n\) are given real numbers and \(w_ 1,...,w_ n\) are given positive real numbers (the so called weights). For solving this problem three algorithms (a partial heapsort method, a linear-time method, and a partial quicksort method) are presented and compared with each other. All these methods are based on the (necessary and sufficient) optimality condition \[ \sum_{x_ i\geq \hat x}w_ i- \sum_{x_ i<\hat x}w_ i\geq 0\text{ and } \sum_{x_ i>\hat x}w_ i-\sum_{x_ i\leq \hat x}w_ i\leq 0 \] for a solution \(\hat x\in {\mathbb{R}}\) of the problem. Computational experiments (on using a Fortran compiler on a VAX 11/780) are reported and show that the order of the three algorithms given above also reflects their performance in terms of CPU-times in different cases for unweighted problems (with \(w_ i=1\) for \(i=1,...,n)\). For weighted median problems modifications of the three algorithms are compared where the partial quicksort method turns out to be significantly faster than the other methods. An application of some of the algorithms to the line search in solving the multidimensional linear \(L_ 1\) problem is also discussed.