Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
By the way, why do you want the greatest residual and not the smallest? –  joriki Apr 26 '11 at 12:09
show 2 more comments

1 Answer 1

I assume that you know how to do linear regression (if not, you can Google it). To find the optimal break point, you have to iterate over all possible breakpoints. If you calculate all the sums that you need from scratch for each breakpoint, the number of required operations is quadratic in the number of points. You can do this more efficiently, with the number of operations linear in the number of points, as follows:

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.

share|improve this answer
    
I have done this once for datapoints in 2D by trying all possible combinations as given by Pascal triangle and then choosing the (piecewise linear) combination whose R^2 (Pearson correlation) values for different lines are most alike. That is by choosing the combination which has the smallest variance or standard deviation in the R^2 values of the lines fitted to the data. –  Mats Granvik Apr 26 '11 at 12:07
    
@Mats: I understood the question to mean that the points are ordered and there should be a single break point dividing the points according to that order, not arbitrary combinations of points. Also, why do you want to choose similar rather than large correlation coefficients? –  joriki Apr 26 '11 at 12:11
    
I don't understand the question completely. Anyways, in the simplest 2D case I tried to fit 2 lines to data points and find a break point in the data. I first plotted the partial R^2 values in the direction from the first data point to the last data point, and then plotted the partial R^2 values in direction from the last data point to the first data point. Then I compared those two R^2 plots and found that they cross each other somewhere in the data. That is where the R^2 values are most alike and the breakpoint is found. Hence I minimized variance of R^2 values of the fitted lines. –  Mats Granvik Apr 26 '11 at 12:44
    
In the case with 2 lines fitted to data: If you aim for large correlation values instead of alike correlation values you easily get a solution where one line is fitted to 2 data points only, and therefore seems to have an excellent fit, but the regression depth is bad (few data points per fitted line). Regression depth –  Mats Granvik Apr 26 '11 at 13:20
add comment

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.