Optimal Pivot Selection in Fast Weighted Median Search

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors A. Rauh, G. Arce
Journal/Conference Name I
Paper Category
Paper Abstract Weighted median filters are increasingly being used in signal processing applications and thus fast implementations are of importance. This paper introduces a fast algorithm to compute the weighted median (WM) of N samples which has linear time and space complexity as opposed to O(N log N) which is the time complexity of traditional sorting algorithms. A popular selection algorithm often used to find the WM in large data sets is Quickselect whose performance is highly dependent on how the pivots are chosen. We introduce an optimization based pivot selection strategy which results in significantly improved performance as well as a more consistent runtime compared to traditional approaches. The selected pivots are order statistics of subsets. In order to find the optimal order statistics as well as the optimal subset sizes, a set of cost functions are derived, which when minimized lead to optimal design parameters. We compare the complexity to Floyd and Rivest's algorithm SELECT which to date has been the fastest median finding algorithm and we show that the proposed algorithm compared with SELECT requires close to 30% fewer comparisons. It is also shown that the proposed selection algorithm is asymptotically optimal for large N.
Date of publication 2012
Code Programming Language C++
Comment

Copyright Researcher 2022