# How do I fit a model with piecewise linear regression

I have a set of points in 3D (x,y,z). I ordered these points from the lowest to highest. So, I want to used linear regression to fit a line through these ordered points and then to find out a break point where the that exhibits the greatest residual occurs.

-
By "lowest to highest", are you referring to the $z$ coordinates? – joriki Apr 26 '11 at 11:16
Already in this simpler problem: math.stackexchange.com/questions/31047/…, it turns out that there are local minima and you can't avoid examining all possible break points. I suspect that will also be true in your case. If that is so, all you can do is to compute the required sums efficiently as you iterate over the possible break points (as described in my answer there). – joriki Apr 26 '11 at 11:20
yes i used Z coordinates to ordered my points. – anh Apr 26 '11 at 11:25
yes joriki, all possible break points need to be check, since i am poor in mathamatics..could you explain me steps that i should follow – anh Apr 26 '11 at 11:27
By the way, why do you want the greatest residual and not the smallest? – joriki Apr 26 '11 at 12:09

Start out with the breakpoint at one end (so all points are on one side and none on the other), and calculate the sums you need for the regression ($\sum x_iy_i$ etc.). These will be all $0$ on the empty side and will include all the data points on the other side. Then in each step move the breakpoint by one, and instead of recalculating all the sums from scratch, just add the appropriate term (e.g. $x_iy_i$ if you're moving the breakpoint past data point $i$) to the one sum (the one that started out empty) and subtract them from the other. That only requires a constant number of operations for each potential position of the break point.