0
$\begingroup$

I simplified a summation over a matrix to speed up an algorithm I'm writing. There's an error in my code though: I'm getting a negative value inside the square root. I can't tell if it's a programming error or if I did the simplification wrong so ... (forgive the syntax if it's bad ... this is more abstract than I'm used to writing...). Am I doing something wrong here?

Given a vector $M$ of length $N$: $$sum = \sum_{N}{} M_{i}$$ $$avg = \frac{1}{N} * sum$$ $$sqsum = \sum_{N}{} M_{i}^2$$

I am simplifying this expression:

$$\sum_{N}(M_{i} - avg)^2$$

which expands to

$$\sum_{N}M_{i}^2 - 2*M_{i}*avg + avg^2$$

the summation can then be split up:

$$\sum_{N}M_{i}^2 - \sum_{N}2*M_{i}*avg + \sum_{N}avg^2$$

Extracting constants and using earlier definitions:

$$sqsum - 2*avg\sum_{N}*M_{i} + N*avg^2$$

And one more replacement with an earlier definition ...

$$sqsum - 2*avg*sum + N*avg^2$$

But avg can be expanded...

$$sqsum - 2*\frac{sum}{N}*sum + N*\frac{sum^2}{N^2}$$

Thus one of the middle terms cancels and I am left with

$$sqsum - \frac{sum}{N}*sum = sqsum - avg*sum $$

Have I done anything "illegal"?

$\endgroup$
  • $\begingroup$ Looks right to me. Programming error maybe. $\endgroup$ – David Nov 27 '15 at 3:46
  • $\begingroup$ You did not do any mistake. It is a standard result to compute the variance. $E[(X -\mu)^2]=E[X^2]-\mu^2$. You may get negative because of MATLAB precision error. $\endgroup$ – Rajat Nov 27 '15 at 3:47
  • 1
    $\begingroup$ Right, @Rajada overflow is also an issue. Numbers that are too large can become negative. $\endgroup$ – Matt Samuel Nov 27 '15 at 3:50
  • 1
    $\begingroup$ @Arjang The application is a (very simple) face recognition program. I was attempting to reduce execution time by simplifying a more complex algorithm, but from the look of it, my simplification is causing errors in the floating point math that result of the expression discussed here being negative. I'll have to look more closely at what's happening to see exactly why and if it's avoidable or if I need to do it the longer way. Interfacing with matlab is outside the scope of my project. $\endgroup$ – Daniel B. Nov 27 '15 at 4:54
  • 1
    $\begingroup$ It seems this is actually a fairly well known problem, and there exist Algorithms for calculating variance to avoid it. $\endgroup$ – Graham Kemp Nov 27 '15 at 10:28
2
$\begingroup$

There's nothing wrong with your equations.   Everything is as expected.

$$\frac 1 N \sum_{i=1}^N \left(X_i-\sum_{j=1}^N X_j\right)^2 = \frac 1 N \sum_{i=1}^N X_i^2 - \left(\frac 1 N\sum_{i=1}^N X_i\right)^2$$

This is a well known result for population variance of data; which is basically what you are calculating.   It should always be positive, but rounding errors may occur in the RHS when the two terms are close; resulting in catastrophic cancellation when the loss of significance is greater than the difference.

$\endgroup$

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.