One-sided Median

Local Algorithm - One-Dimensional Algorithm

One-sided Median algorithm computes the median

$$m_n^Y = \text{Median}\{Y_{n-2k}, \ldots, Y_{n-1}\}$$

and the median

$$m_n^Z = \text{Median}\{Z_{n-2k}, \ldots, Z_{n-1}\}$$

with

$$Z_n = Y_n - Y_{n-1}.$$

$2k$ is the size of the neighborhood window. Defining

$$\hat{m}_n = m_n^Y + k m_n^Z \, \text{,}$$

$Y_n$ is treated as a value outside the region of interest if $|Y_n - \hat{m}_n| \geq \tau$.

Input Parameters

Parameter	Type	Constraint	Description	Remarks
$Y$	$Y \in \mathbb R^N$	$N \in \mathbb{N}$	Input data sequence of length $N$
$\tau$	$\tau \in \mathbb R^+$		User-specified threshold

Output Parameters

Parameter	Type	Constraint	Description	Remarks
$\hat{Y}$	$\hat{Y} \in \mathbb R^N$		Values in the $Y$ list which are outside the region of interest are marked

Single Steps using the Algorithm

• Outlier Detection with One-sided Median

References

• S. Basu, M. Meckesheimer, Automatic outlier detection for time series: an application to sensor data, Knowledge and Information Systems, vol. 11, Issue 2, pp 137-154, 2007.