From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Minimising the distance of points from a plane Date: 13 Dec 1999 21:34:41 GMT Newsgroups: sci.math Keywords: regression results depend on objective function Andrew Francis wrote: > Given a set of points in 3 dimensions, I need to find the plane that > minimises the total of the distances from the plane to each point. > > I just read an article on z-regression but my understanding (admittedly not > good ;) is that regression only works in one dimension as far as minimising > distance is concerned. As others have pointed out, regression works just fine in higher dimensions. In article <38513A4C.82FB9219@online.no>, Michael Hovdan writes: > Let your points be specified by (x1,y1,z1), (x2,y2,z2), > (x3,y3,z3)....(xn,yn,zn). You want to find a regressio on the form: > z=a+bx+cy (this describes the plane you want). > > The problem is finding the a, b and c so that Sum over i=1,2,3...n of (z-zi)² > is mimimal. In response, Ed Hook wrote: > A small problem here: if the original really means what he says, > you have to use the distance from the points to the sought-after > plane. That is _not_ (z - zi)^2. > > If I recall correctly, the distance of the point (x*,y*,z*) from > the plane with equation Ax + By + Cz = D is given by > > | Ax* + By* + Cz* - D | > ------------------------- . > sqrt(A^2 + B^2 + C^2) This is the correct distance, and yes, it's true that this is a different question: minimizing the sum of the _squares of the distances_ is different from minimizing the sum of the _squares of the z-coordinates_. Moreover, each is different from minimizing the sum of the _distances_ and from minimizing the sum of the _z-coordinates_; the algebra is quite a bit messier without the additional squaring, but the opening question does seem to have asked for that. Then in article <3852B1B2.C3EE7D97@online.no>, Michael Hovdan wrote: > >Yes, I see your point. And I thought about that as I was writing my >original reply. But I think (I may be wrong!) I remember seeing a >proof once that the two norms lead to the same solution. Have you >checked this? Let's try the points (x,y,z)=(0,0,0), (0,1,1), (1,0,1), (1,1,3). What shall we minimize? Sum of squares of z-displacements? Writing as above z = a + bx + cy we see we want to choose a, b, c to minimize (a+b*0+c*0 - 0)^2 + (a+b*0+c*1-1)^2 + (a+b*1+c*0-1)^2 + (a+b*1+c*1-3)^2 = 4*a^2-10*a+4*a*c+11-8*c+2*c^2+4*a*b+2*b^2-8*b+2*b*c which happens when a=-1/4, b=c=3/2. The function is z=-.25+1.5(x+y). Sum of squares of distance? Writing Ax + By + Cz = D as above, we normalize by setting D = 1 (checking separately whether any plane through the origin might give a better fit). We want to choose A,B,C to minimize (4-4*B-10*C+2*B^2+8*B*C+11*C^2+2*A^2-4*A+8*A*C+2*A*B)/(A^2+B^2+C^2) The solution here is to take C to satisfy 2C^2+5C-4=0 (roughly -3.14) and then A=B= 1-(5C/4); then the function roughly -.32 + 1.57(x+y) Sum of z-displacements? Now we wish to choose a,b,c to minimize | a | + | a - 1 + c | + | a + b - 1 | + | a + b + c - 3 | There are many solutions which tie for best here: e.g. whenever b=c and c is between 3/2 and 2 and a is between -(c-1) and -2(c-3/2). All these give a sum of z-displacements equal to 1. Sum of distances? If I've done this right, the expression (1+abs(A-1+C)+abs(-1+B+C)+abs(A+B+3*C-1))/sqrt(A^2+B^2+C^2) is minimized when A=6, B=4, C=-3, giving an optimal plane of z=(-1/3)+ 2x + (4/3)y , although z=(-1/3)+ (4/3)x + 2 y is just as good. If I understand the original poster correctly, the last is what was asked for, although I'm guessing that the poster didn't really care about the specific criterion used. One final comment: as noted by others, finding the first of these planes is a simple regression problem. The second plane is also amenable to a nice analysis; this is what is sometimes called "principal component analysis", although there are other names used too. dave