Least Squares for Linear Equations
Date: 06/06/2012 at 10:41:50 From: gul Subject: Least Square Method How does the least squares solution take you from an over-determined system of equations to an exactly determined one?
Date: 06/07/2012 at 10:23:18 From: Doctor George Subject: Re: Least Square Method Hi gul, Thanks for writing to Doctor Math. This is a great question! Assuming that you have in mind linear least squares, consider this over-determined system of equations: - - - - - - |ux vx| |a| |px| |uy vy| |b| = |py| |uz vz| - - |pz| - - - - I chose this example because we can interpret it in ordinary 3D space. On the right-hand side, we have a matrix composed of two 3D column vectors, u and v, which we will assume are non-collinear. We can rewrite it like this: - - - - - - |ux| |vx| |px| a|uy| + b|vy| = |py| |uz| |vz| |pz| - - - - - - We are looking for a linear combination of u and v that gives us point p. But there can only be a solution if p is in the plane formed by u and v. If there is no solution, then the least squares solution will be when the difference between the left- and right-hand sides is the shortest possible vector. In other words, we are looking for the point on that plane that is closest to p, which is the projection of p onto that plane. There will only be one such point, so the least squares solution will be unique, or exactly determined. Now let r be the vector that represents the difference between the left- and right-hand sides. - - - - - - - - |rx| |ux| |vx| |px| |ry| = a|uy| + b|vy| - |py| |rz| |uz| |vz| |pz| - - - - - - - - Making r as short as possible means that it will be perpendicular to the plane formed by u and v for the best choice of a and b. Making r perpendicular to the plane means that it is perpendicular to both u and v. This means that we want - - - - |ux uy uz| |rx| |vx vy vz| |ry| = 0 - - |rz| - - Now substitute for r in this equation and re-arrange the terms to get - - - - - - - - - - |ux uy uz| |ux vx| |a| |ux uy uz| |px| |vx vy vz| |uy vy| |b| = |vx vy vz| |py| - - |uz vz| - - - - |pz| - - - - This equation is normally written with transpose notation. On the left-hand side, we get a 2x2 matrix that is invertible. So the linear algebra representation will produce the unique solution. The projection operation has reduced the number of dimensions in the problem by one, and that is what we needed to go from being over- determined to uniquely determined. The same principles apply for higher dimension problems. Does that make sense? Write again if you need more help. - Doctor George, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum