15
$\begingroup$

My question relates to a simple case of the least squares problem. For example, take the system of equations \begin{align*} 2x- y &= 2, \\ x + 2y &= 1, \\ x+y &= 4, \end{align*} which is clearly overdetermined. Using a least squares approach, we can solve the system $$A^TA\mathbf{x^*} = A^T\mathbf{b},$$ where $\mathbf{x^*}$ minimises $\|\ A\mathbf{x} -\mathbf{b} \ \|$, and $$A = \begin{bmatrix} 2 & -1\\ 1 & 2 \\ 1 & 1 \end{bmatrix} \ , \quad \mathbf{b}= \begin{bmatrix} 2 \\ 1 \\ 4 \end{bmatrix} \quad \mbox{and} \quad \mathbf{x}= \begin{bmatrix} x \\ y \end{bmatrix},$$ to obtain an approximation for the solution as $\left(\frac{10}{7}, \frac{3}{7} \right)$.

If you plot the three straight lines that constitute the system of equations, they intersect at three points that form the vertices of a triangle.

My question is - does the solution always fall within this triangle (as in this example), and if so, is this point a (non-traditional) triangle center?

$\endgroup$
7
  • 1
    $\begingroup$ I believe the result will always be the barycenter of the triangle, but do not have a proof. $\endgroup$ – Alex Becker Aug 20 '13 at 6:47
  • 6
    $\begingroup$ The trouble is that scaling one of the equations does not change the triangle but it does change the least-squares solution. This is the difference between the geometry and the algebra of the problem. If you scale everything so that the rows of $A$ are unit vectors, you may get a meaningful triangle center. $\endgroup$ – user856 Aug 20 '13 at 6:56
  • $\begingroup$ It's not the barycentre. What do you get when two of the lines are nearly parallel? $\endgroup$ – Robert Israel Aug 20 '13 at 7:02
  • $\begingroup$ Good question. Suppose we "normalize" all the line equations -- we write them in the form $ax+by=c$, where $a^2+b^2=1$. Then I think you're asking ... what point in the interior of a triangle minimises the sum of the (squared?) distances to its three sides. I don't know the answer, but I'd like to know. $\endgroup$ – bubba Aug 20 '13 at 7:36
  • 3
    $\begingroup$ The point minimizing the sum of the squares of the distances to the sidelines of a triangle is the symmedian point of the triangle. See en.wikipedia.org/wiki/Symmedian for the definition, and Exercise 7.3 in Ross Honsberger's "Episodes in Nineteenth and Twentieth Century Euclidean Geometry" (but ignore the word "inside", which isn't really needed) for the proof of the above property. Basically it follows from the Cauchy-Schwarz inequality, along with the fact that the distances from the symmedian point to the sidelines are proportional to the length of these sides. $\endgroup$ – darij grinberg Aug 20 '13 at 8:32
5
$\begingroup$

As Rahul Narain commented, the precise position of the least-squares solution depends on the scaling of the individual equations: as you scale up an equation, so does the importance of the distance of your solution to the corresponding line, and the least-squares solution will end up closer to that line. You can say that in any case the least-squares solution will lie in the interior of the triangle formed by the three lines, since for a point in any of the other $6$ sectors into which the lines cut up the plane, moving in some direction will decrease the distances to all three lines at the same time, so one can never have a minimum there.

In the spacial case where you scale the equations in such a way that for each of the the sum-of-squares-of-coefficients gives the same value (for instance$~1$), then you can describe the least-square solution as the unique point$~P$ such that the sum of the three vectors from $P$ to its orthogonal projections on the three lines is zero; in other words $P$ is the barycenter of its own pedal triangle (the triangle formed by those projections). That this is so can easily be seen by taking the formula implicit in the comment by @bubba and differentiating it.

Giving a geometric construction of such a point is an interesting problem that probably has been considered by people, but I don't see an easy solution right now, nor do I recall having seen anything directly related. In particular, I am unsure if this point coincides with any one of the many "centers" associated to a triangle; however given that there are so many of them, and the description of the point we are interested is is quite natural, I would bet that it does equal one of those centers.

Indeed, thank you darij grinberg for pointing out that this is the Symmedian Point, the properties listed under the link correspond exactly to what we are after here.

$\endgroup$
2
  • $\begingroup$ Excellent answer, thank you. Can you elaborate a little on "such that the sum of the three vectors from it to its orthogonal projection on the three lines is zero"? I'm not quite sure what "it" refers to? What are we projecting onto the lines? How does one calculate the Symmedian Point given the vertices? Sorry for all the questions, this problem really struck me for some reason. $\endgroup$ – Bennett Gardiner Aug 20 '13 at 10:10
  • 1
    $\begingroup$ @BennettGardiner: I've reformulated a bit, and added a missing 's' to "orthogonal projection" whose absence made the sentence hard to decipher. I hope it is better now. $\endgroup$ – Marc van Leeuwen Aug 20 '13 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.