Why are median filters non-separable?

Question

I'm reading through a digital signal processing textbook, which says "It should be noted that the square two-dimensional median mask is a non-separable mask" but gives no explanation as to why this is true. I can see why mean filters are separable (a $3\times 3$ matrix of ones can come from the convolution of $[1 1 1] * [1 1 1]^T$), but why is a median filter non-separable? Specifically, why are square median filters non-separable? And does this mean that all non-square median filters are separable?

Answer 1

A median filter is non-linear, since it consists of a median function that has no equivalent sum-product form, so it cannot be separated into a product of two vectors for any length larger than 2. Doesn't matter whether it has square mask or not.

For example, mean can be formed as sum product $\frac{1}{n}\sum_{i=1}^n 1\cdot x_i$, but median requires an operator that sorts and finds the middle, which is beyond any linear algebraic operations.

Answer 2

I don't have a proof, but median filters are not separable because the median of the medians of sets $S_i$ is not necessarily the same as the median of the union of those sets.

This property does hold for the mean, hence you can make a separable mean filter. The same is true for the maximum and the minimum operations (leading to separable dilations and erosions). I'm not aware of other non-linear operations used in image processing that have this property.

Note that the non-separability of the median is true for any shape mask, and for any dimensionality larger than 1.