2
$\begingroup$

I have a data from a sensor which the connection model of $x$ and $y$ is known:

enter image description here

For instance, in the case above, the model is linear.

The issue is how to handle outliers.
Specifically when there are many samples yet the model parameters is small.

Linear Least Squares fails in this case as the number of outliers can be up to 15-20%.

So the question is, what would be a robust fit which can handle large amount of data and a rate of up to 20% of outliers?

$\endgroup$
2
  • $\begingroup$ Hi Royi! Good to see you. $\endgroup$ Jan 23 at 22:59
  • $\begingroup$ @robertbristow-johnson, Hi. Good to see you. $\endgroup$
    – Royi
    Jan 26 at 16:50

2 Answers 2

2
$\begingroup$

A simple and cheerful approach is to solve regular LMS for the sequence using different subsets of the total sample set, then pick the model that best satisfies some fitting criterion for the entire sample set.

Scales poorly to long sequences and large numbers of potential outliers.

$\endgroup$
1
  • $\begingroup$ This is similar to RANSAC. Even less efficient, as in this case RANSAC will only need ~50-60 samples and the LS calculation will be negligible. I wanted something more bullet proof than iterative way to mark the outliers. $\endgroup$
    – Royi
    Jan 24 at 20:32
1
$\begingroup$

One way, which can handle ~30% of outliers is given by solving:

$$ \arg \min_{\boldsymbol{p}} {\left\| \boldsymbol{X} \boldsymbol{p} - \boldsymbol{y} \right\|}_{1} $$

Using the ${L}^{1}$ norm instead of the ${L}^{2}$ norm means the fit is more robust to outliers.
The intuition is form the fact that the ${L}^{1}$ norm minimizer is the median (See The Median Minimizes the Sum of Absolute Deviations (the ${\ell}_{1}$ Norm)) while the ${L}^{2}$ norm minimizer is the mean.

There are several ways to solve this:

  1. Forming the problem as a Linear Programming problem.
  2. Using the Sub Gradient method.
  3. Using Iterative Reweighted Least Squares (IRLS).

The IRLS method is very quick to converge.
Given $\boldsymbol{X} \in \mathbb{m \times n}$ and $n \ll m$ then it can be solved pretty quickly as the most demanding step will be solving a linear system composed by an SPSD matrix of size $n \times n$.

For affine function, as above, it means solving a $2 \times 2$ system.

enter image description here

As can be seen, it works pretty well handling all the samples.
Solving this with efficient code is about ~100 [Mili Sec] for ~10,000 samples.
Run time could be even improved by a sub sampling.

The full Julia code is available on my StackExchange Signal Processing GitHub Repository (Look at the SignalProcessing\Q91788 folder).

$\endgroup$
5
  • $\begingroup$ Wondering where the Convex.jl line is? $\endgroup$
    – Peter K.
    Jan 22 at 1:38
  • 1
    $\begingroup$ @PeterK. , I load it at github.com/RoyiAvital/StackExchangeCodes/blob/…. Using it at github.com/RoyiAvital/StackExchangeCodes/blob/…. $\endgroup$
    – Royi
    Jan 22 at 6:13
  • 1
    $\begingroup$ @PeterK., At the graph you can't see it as the IRLS solution is on top of it. They are the same. I use Convex.jl to verify the implementation of the IRLS code. $\endgroup$
    – Royi
    Jan 22 at 6:15
  • $\begingroup$ @PeterK., I created a tag named data-fitting. Could you make fit-data, data-fit and fitting-data its synonymous? $\endgroup$
    – Royi
    Jan 23 at 20:29
  • 1
    $\begingroup$ No existing tag fit-data or fitting-data seem to be there, but I've merged data-fit onto data-fitting and made data-fit a synonym. $\endgroup$
    – Peter K.
    Jan 23 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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