5
$\begingroup$

I can easily prove that the mean filter minimizes the square error $L_2$ cost function using simple calculus.

However, how do you prove that the median filter is optimal with respect the absolute error $L_1$ norm?

$\endgroup$
2
  • $\begingroup$ I think you better describe the use case in the Signal Processing world. $\endgroup$
    – David
    Feb 19 at 6:01
  • $\begingroup$ @David what exactly are you saying/asking? $\endgroup$
    – Izzo
    Feb 19 at 16:08
6
$\begingroup$

Given a set of values $ {\left\{ {s}_{i} \right\}}_{i = 1}^{N} $, we're basically after: $$ \arg \min_{x} \sum_{i = 1}^{N} \left| {s}_{i} - x \right| $$

One should notice that $ \frac{\mathrm{d} \left | x \right | }{\mathrm{d} x} = \operatorname{sign} \left( x \right) $ (Being more rigorous would say it is a Sub Gradient of the non smooth $ {L}_{1} $ Norm function).
Hence, deriving the sum above yields $ \sum_{i = 1}^{N} \operatorname{sign} \left( {s}_{i} - x \right) $.
This equals to zero only when the number of positive items equals the number of negative which happens when $ x = \operatorname{median} \left\{ {s}_{1}, {s}_{2}, \cdots, {s}_{N} \right\} $.

Remarks

  1. One should notice that the median of a discrete group is not uniquely defined.
  2. The median is not necessarily an item within the group.
  3. Not every set can bring the Sub Gradient to vanish. Yet employing the Sub Gradient Method is guaranteed to converge to median.
  4. It is not the optimal way to calculate the Median. It is given to give intuition about what's the median.
$\endgroup$
2
  • 1
    $\begingroup$ For remark 1, is this only the case when the number of elements is even? For remark 2, I don't understand this. Something can't be a median if it's not in the group correct? $\endgroup$
    – Izzo
    Feb 19 at 13:55
  • 1
    $\begingroup$ Remark 1: In case all items are unique indeed it is only for even. But for non unique sets it might be for odd as well. Remark 2: No, the $ {L}_{1} $ minimizer in a number which doesn't have to be in the set. In case it must be in the set it is a different optimization problem (Discrete and hence not convex). $\endgroup$
    – Royi
    Feb 19 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.