Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a dataset of vectors and need to find the sum of squares or variance based on the euclidean distance between the vectors.

I can do this by finding the "average" vector (by calculating the average components of the vectors) and then summing up the squared euclidean distance between each vector and the average vector.

Is there a way to do this on the "fly" without calculating the average vector? I am familiar with the short cut method for finding the variance of a one-dimensional datasets and would like to find something similar for vectors.

Any help is greatly appreciated.

share|improve this question
    
This is off-topic here; it would probably be more appropriate on stats.stackexchange.com . –  Qiaochu Yuan Jan 20 '12 at 6:37
1  
Is it? Apart from the word "variance", it looks like a general algorithmic question to me. And it resembles a lot mathoverflow.net/questions/70345/… –  Federico Poloni Jan 20 '12 at 9:34
    
I don't think the question is off-topic here. Nevertheless, it's probably more likely to get good answers at either stats.stackexchange.com or scicomp.stackexchange.com . –  Mark Meckes Jan 20 '12 at 14:20

1 Answer 1

This wasn't really meant to be a stats question - more of a computational geometry question.

I think I found a way of doing this (at least for the euclidean distance measure).

First sum up each component for all the vectors. Then sum up the squared values for the components of all the vectors.

Now we have two new vectors: A "sum" vector containing the sum of each component and a "sumOFsquares" vector containing the sum of the squares of each components.

Assume n is the number of vectors in the dataset.

Then calculate sumOFsqaures - sum^2/n. Subtract the corresponding elements of sum from sumOFsquares) which will give a new vector.

Then sum up the components of this new vector. I tried this on a couple of examples and it seemed to give the Sum of Squares I was looking for.

I would be interested in finding a way to do this for other distance measures.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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