Minimum sum of distance vs L1 and geometric median
All this post is just a more detailed explanation of the end of the previous post.
Assume we want to estimating a state from noisy linear measurements , , – noise with outliers, like in the paper by Sharon, Wright and Ma Minimum Sum of Distances Estimator: Robustness and Stability
Sharon at al show that minimum norm estimator, that is
is a robust estimator with stable breakdown point, not depending on the noise level. What Sharon did was to use as cost function the sum of absolute values of all components of errors vector. However there are exists another approach.
In one-dimensional case minimum norm is a median.But there exist generalization of median to – geometric median. In our case it will be
That is not a least squares – minimized the sum of norm, not the sum of squares of norm.
Now why is this a stable and robust estimator? If we look at the Jacobian
we see it’s asymptotically constant, and it’s norm doesn’t depend on the norm of the outliers. While it’s not a formal proof it’s quite intuitive, and can probably be formalized along the lines of Sharon paper.
While first approach with norm can be solved with linear programming, for example simplex method and interior point method, the second approach with norm can be solved with second order cone programming and …surprise, interior point method again.
For interior point method, in both cases original cost function is replaced with
And the value of is defined by constraints. For
Sometimes it’s formulated by splitting absolute value is into the sum of positive and negative parts
, , ,
And for it’s a simple
Formulations are very similar, and stability/performance are similar too (there was a paper about it, just had to dig it out)
Sorry, the comment form is closed at this time.