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$ Aug 20, 2013 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, 2013 at 6:56
  • $\begingroup$ It's not the barycentre. What do you get when two of the lines are nearly parallel? $\endgroup$ Aug 20, 2013 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, 2013 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$ Aug 20, 2013 at 8:32

1 Answer 1

6
$\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$ Aug 20, 2013 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$ Aug 20, 2013 at 12:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .