The weighted median is a statistical measure that generalizes the concept of the median for datasets where individual observations have varying degrees of importance or reliability, denoted as weights. This computation is widely used in fields such as economics, computer science, and statistics, particularly in robust data analysis and image processing.

Understanding the Weighted Median

The median of a dataset is the value that separates the higher half from the lower half. In a similar way, the weighted median takes into account both the values of the data points and their associated weights. The intuition behind the weighted median is to identify a point that splits the dataset into two parts of equal weighted mass.

Definition

Given a dataset with $n$ elements $(x_1, x_2, \ldots, x_n)$ and corresponding non-negative weights $(w_1, w_2, \ldots, w_n)$, the weighted median is a value $x_k$ from the dataset such that:

$$\sum_{x_i < x_k} w_i \leq \frac{W}{2}$$

and

$$\sum_{x_i > x_k} w_i \leq \frac{W}{2}$$

where $W = \sum_{i=1}^{n} w_i$ is the total weight.

This condition ensures that the weighted sum of elements less than the median and the weighted sum of elements greater than the median is each no greater than half the total weight.

Example Calculation

Consider a simple example with the dataset $(8, 3, 5, 2, 10)$ and respective weights $(1, 2, 3, 4, 5)$. We need to compute the weighted median:

1. Sort the data by the values: $(2, 3, 5, 8, 10)$ with sorted weights $(4, 2, 3, 1, 5)$.
2. Compute the cumulative weights: • 2: 4 • 3: 6 • 5: 9 • 8: 10 • 10: 15
3. Total weight $W = 1 + 2 + 3 + 4 + 5 = 15$.
4. Weighted median condition: cumulative weight just exceeds $W/2 = 7.5$ at the value 5.

Thus, the weighted median in this example is 5.

Properties and Applications

• Robustness: The weighted median is robust to outliers, as extreme values with low weights have limited influence on the result. • Non-uniqueness: When cumulative weight passes half at multiple points, any of these can qualify as a weighted median. • Applicability: Weighted median is suitable for datasets with reliability differences among observations, commonly seen in sensor fusion, computational imaging, and survey data analysis.

Algorithm for Efficient Computation

The weighted median can be computed efficiently using an algorithm similar to the QuickSelect algorithm for the median. Key steps include:

1. Sort the Dataset: Sort the data entries by their values.
2. Cumulative Sum of Weights: Compute the cumulative sum of weights as you iterate through values.
3. Locate Weighted Median: Find the smallest index $k$ where the cumulative weight equals or surpasses $W/2$.

A well-informed choice of pivot in each iteration can ensure a time complexity of $O(n)$ on average for finding the weighted median, similar to the time complexity for finding the standard median.

Pseudocode for Weighted Median