Speed of linear modeling

Question

Asked already on stackexchange, this place is probably a better fit, if somebody could delete the old post I'd appreciate it.

I have a linear regression equation from school , which gives a value between 1 and -1 indicative of whether or not a set of data points are close enough to a linear function

and the equation given here

http://people.hofstra.edu/stefan_waner/realworld/calctopic1/regression.html

under best fit of a line. I would like to use these to do simple gesture detection based on a point in 3-space (x,y,z) - forward, back, left, right, up, down. First I would see if they fall on a line in 2 of the 3 dimensions, then I would see if that line's slope approached zero or infinity.

Is this fast enough for functional gesture recognition? If not, could someone propose an alternative algorithm?

Answer 1

Without knowing (a lot) more about your application, the best I can say is "maybe." Obviously, the runtime is going to depend on the number of points you've got, the speed of your processor, what "enough" is, etc.

All that said, it's a pretty simple formula and can be calculated in a single pass over your data, so I doubt it'll be a problem. If you absolutely had to, you could accumulate the sums ($\sum (x)$, $\sum(x^2)$, etc) on the fly, which would only leave you with a handful of operations (four multiplications, three subtractions, two squarings and square-rootings, and a division) at the end. That should be nearly instantaneous on anything short of an abacus.

Alternately, if you have lots of points, there are numerical libraries floating around, like ATLAS and IPP (relevant stackoverflow thread) are tuned for specific platforms. That's a rather heavy-weight solutions though. Personally, I would start by coding my own and seeing how well it works.

Finally, just be aware that linear regression may give you counterintuitive answers for some shapes (e.g., you may not have a vertical component if something rises and falls in an arc). Depending on what you're doing, that might be a bug or a feature :-)