From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: Least Squares and Total Least Squares Date: 16 Oct 1995 21:30:29 GMT In article <95275.195027ALH4@psuvm.psu.edu>, Alan Horwitz wrote: >Given a set of data points in R^2, let y = m1*x + b1be the ordinary >least squares line to the data-i.e. the line which minimizes the sum of >the squares of the vertical distances to the data points. Let y = m2*x >+ b2 be the line which minimizes the sum of the squares of the >horizontal distances to the data points. Finally, let y = m*x + b be >the total least squares line, which minimizes the sum of the squares of >the perpendicular distances to the data. It appears that m is always >between m1 and m2, at least when the total least squares line is unique. Oh goody, a calculus problem. Let f(m,b)=Sum(yi - (m xi + b))^2, the usual total least squares function. Then the different lines are trying to minimize, respectively, f(m,b), (1/m)^2 * f(m,b), and (1/(1+m^2))*f(m,b). If the minimum of f occurs at (m0, b0), then we can choose new variables m'=m-m0 and b' (linear in m and b) so that in terms of the new variables, f(m,b) = c1 + c2 m'^2 + c3 b'^2. (by positivity, all ci are non-negative.) The other functions to be minimized are of the form R(m')*f; setting the partials w.r.t. m' and b' equal to zero shows the minima occur when b'=0 and R(m')*(2 c2 m') + R'(m')*(c1 + c2 m'^2) = 0. When R(m)=m^(-2) this leads to m'=c1/(c2 m0), i.e., m = m0 + c1/(c2 m0). In particular, the slopes of this "best" line and the standard one are of the same sign. When R(m)=(1+m^2)^(-1), the fact that b' will be zero means we are trying to minimize R(m)*f(m,b) = (c1 + c2(m-m0)^2)/(1+m^2) = c2 + (c1-c2+c2 m0^2 -2 c2 m0 m)/(1 + m^2) = c2 + (A - B m)/(1+m^2), say; this happens when m is the root of x^2 - 2(A/B)x - 1 = 0 having the same sign as B (and thus the same sign as m0). Now, this polynomial, when evaluated at m0, gives -c1/c2 < 0; when evaluated at m0 + c1/(c2 m0), gives (c1/c2 m0^2) > 0. Thus, one of the two roots of the quadratic lies between the slopes used for the other two lines. Clearly, the root in question is the one of the same sign as m0, which is the root described above. So yes, the slope used to minimize the absolute distances will be between the slopes used to minimize the distances to an axis. dave ============================================================================== Date: Mon, 27 Nov 95 18:05 EST From: "Alan Horwitz" Subject: Re: Least Squares and Total Least Squares To: rusin@math.niu.edu I've just gotten around to looking at your proof in some detail. A couple of things don't seem to be right, however. I'll try to fix them up myself since your approach looks promising, but maybe I'm missing something. First, to eliminatea term like (m-m0)(b-b0), don't you need m' to be linear in m and b as well as b' ? Also, when R(m)=m^(-2), I keep getting that c1=0, not m'=c1/(c2*m0). Am I missing something here ? If you still remember what you did, perhaps you could clear this up for me. Thank you. Alan Horwitz. - - The original note follows - - [deleted - djr] ============================================================================== Date: Thu, 7 Dec 95 13:19:50 CST From: rusin (Dave Rusin) To: ALH4@PSUVM.PSU.EDU Subject: Re: Least Squares and Total Least Squares >I've just gotten around to looking at your proof in some detail. A >couple of things don't seem to be right, however. Uh oh, I think you're right. > First, to eliminatea term like (m-m0)(b-b0), don't you need >m' to be linear in m and b as well as b' ? Yes indeed. Sorry. Let me try this again. Here's an edited version of the previous post. Let f(m,b)=Sum(yi - (m xi + b))^2, the usual total least squares function. Then the different lines are trying to minimize, respectively, f(m,b), (1/m)^2 * f(m,b), and (1/(1+m^2))*f(m,b). I tried to minimize them in a fancy way in the post and you saw I blew it. OK, let's try brute force. You've got a quadratic function of m and b, you use partial derivatives to find the minima of f, f/m^2, and f/(1+m^2), and you want to show some inequalities. Very well,... sun subshell 1 > maple |\^/| Maple V Release 3 (N I U) ._|\| |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the \ MAPLE / University of Waterloo. All rights reserved. Maple and Maple V <____ ____> are registered trademarks of Waterloo Maple Software. | Type ? for help. > f:=A*m^2+B*m*b+C*b^2+F*m+G*b+H: > l1:=diff(f,m): > l2:=diff(f,b); > solve({l1=0,l2=0},{m,b}); - B F + 2 A G 2 C F - G B {b = - -------------, m = - ------------} 2 2 - B + 4 A C - B + 4 A C > m1:=rhs("[2]): > f2:=f/m^2: > q1:=simplify(diff(f2,m)*(-m^3)): > q2:=simplify(diff(f2,b)*m^2): > solve({q1,q2},{m,b}); 2 - F G + 2 H B 4 C H - G {b = -------------, m = - -----------} 2 C F - G B 2 C F - G B > m2:=rhs("[2]): > f3:=f/(1+m^2): > r1:=simplify(diff(f3,m)*(-1)*(1+m^2)^2): > r2:=simplify(diff(f3,b)*(1+m^2)): > solve({r1,r2},{m,b}); 2 2 2 {m = RootOf((2 C F - G B) _Z + (B + 4 C H - 4 A C - G ) _Z + G B - 2 C F), b = - 1/2 2 2 2 B RootOf((2 C F - G B) _Z + (B + 4 C H - 4 A C - G ) _Z + G B - 2 C F) + G ---------------------------------------------------------------------------- C } OK, at this point we know where f and f/m^2 are minimized, but we see that to find the m coordinate of the minimum of f/(1+m^2), we need to solve a quadratic equation. All I have to do is to show you that this quadratic takes on a positive value at one m-coordinate and a negative value at the other; it follows that the quadratic is equal to zero somewhere between these two m-coordinates, and we are done. Well, > po:=(2*C*F-G*B)*z^2 + (B^2+4*C*H-4*A*C-G^2)*z+G*B-2*C*F; > va1:=simplify(subs(z=m1,po)): > va2:=simplify(subs(z=m2,po)): > simplify(va1*va2); 2 2 2 2 2 (- B H + 4 A C H - A G + F G B - C F ) C - 16 -------------------------------------------- 2 2 (- B + 4 A C) This is the negative of a perfect square, so it's negative, meaning po(m1) and po(m2) have opposite signs. So yes, the slope used to minimize the absolute distances will be between the slopes used to minimize the distances to an axis. dave ============================================================================== Date: Thu, 4 Jan 96 14:02 EST From: "Alan Horwitz" Subject: Re: Least Squares and Total Least Squares To: rusin@math.niu.edu I also tried what you did on Maple and everything goes thru as you indicated. There's only one small problem which I've been trying to rectify. The quadratic p0=0 has two solutions. If the total least squares problem in this case has a unique solution, then only one of those solutions(assuming they're distinct) can give the global minimum for f/(1+m^2). That solution might not be between m1 and m2. I hope there is a simple way to fix this, because I really like your proof. In general, the TLS problem may not ahve a unique solution, but for the specific case of data in the plane(xi/=xj) and y=mx+b, I believe it does. One of those solutions to p0=0 is related to an eigenvector which does not give the global min. I'll think about this somemore. ============================================================================== Date: Thu, 4 Jan 96 14:02 EST From: "Alan Horwitz" Subject: Re: Least Squares and Total Least Squares To: rusin@math.niu.edu I also tried what you did on Maple and everything goes thru as you indicated. There's only one small problem which I've been trying to rectify. The quadratic p0=0 has two solutions. If the total least squares problem in this case has a unique solution, then only one of those solutions(assuming they're distinct) can give the global minimum for f/(1+m^2). That solution might not be between m1 and m2. I hope there is a simple way to fix this, because I really like your proof. In general, the TLS problem may not ahve a unique solution, but for the specific case of data in the plane(xi/=xj) and y=mx+b, I believe it does. One of those solutions to p0=0 is related to an eigenvector which does not give the global min. I'll think about this somemore. ============================================================================== Date: Thu, 04 Jan 1996 15:11:18 -0500 To: rusin@math.niu.edu From: alh4@psu.edu (Alan Horwitz) Subject: example for p0 Hear is an example: Consider the data (1,2),(2,6),(6,1). Then p0=84z^2-84. One of the roots, m=-1, gives the slope of the TLS line. The other root, m=1, does not. P.S. You can send mail to the above address instead. ============================================================================== From: Alan Horwitz Date: Fri, 03 May 96 19:10:35 -700 To: rusin@math.niu.edu Subject: Monotone orthogonal least squares Dear Professor Rusin: I found your stuff on the WEB very interesting. I haven't had a chance to get to most of it yet, but I did look at the correspondence of our's which you included. I just wanted to point out that to be complete, you should include my last letter(of a few months ago) which indicates that the proof is still not quite there yet. Did you receive that ? ============================================================================== [oops -- the hazards of trying to maintain a project too big for one's time constraints! -- djr] ==============================================================================