Intersection of Lines / Least Squares

May 2010
1
0
Hi,

I'm trying to understand the following least squares example:

You have three lines:
2x - y = 2
x + 2y = 1
x + y = 4

The lines do not have a common intersection point, so the example is using least squares to find a point that minimizes the distance to the lines.

It goes on to build the matrices:
A(3x2) = ((2 1 1)^T (-1 2 1)^T)
b(3x1) = (2 1 4)^T

And then uses the least squares equation:
A^T A x* = A^T b
to come up with the least squares solution, x*.

I understand how least squares works. I also understand how it is used to come up with a solution given the matrices A and b.

We are minimizing the distance to b from the column spaces of A. The column spaces form a plane in R^3. I don't understand how this plane relates to our original problem. Why would the closest point to b in that plane somehow be the closest point to the three lines in our initial problem formulation ? (That is, is it somehow representing the closest point to the lines as calculated by a sum of perpendicular vectors from our least squares solution. And if so, why? Or, is it somehow representing the closest point to the lines as calculated by a sum of y-differences from our least squares solution. And if so, why? Or is it representing something totally different, and what?)
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
You are looking for a point (x, y, z) that satisfies all of 2x - y = 2, x + 2y = 1, and x + y = 4. You might suspect that, since there are three equations in only two unknowns, this is not possible.

Write it as a matrix equation. That is the same as looking for a vector \(\displaystyle \begin{bmatrix}x \\ y \\ z\end{bmatrix}\) such that
\(\displaystyle \begin{bmatrix}2 & -1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix}= \begin{bmatrix}2 \\ 1 \\ 4\end{bmatrix}\)
While we would normally solve such an equation by finding the inverse matrix, this matrix obviously does not have an inverse as it is not a square matrix.

Think of it as a linear transformation from \(\displaystyle R^2\) to \(\displaystyle R^3\). The "image" of \(\displaystyle R^2\) under this linear transformation is a two-dimensional subspace in \(\displaystyle R^3\). We can find an exact solution For Ax= v if and only if v happens to lie in that subspace. If not, the closest we can get is to the foot of the perpendicular from v to that subspace- Ax is the projection of v onto the subspace. In that case, Ax-v is perpendicular to the subspace: <w, Ax- v>= 0 (< , > is the inner product in \(\displaystyle R^3\) for all w in the subspace. Since that subspace is the image of \(\displaystyle R^2\) under A, w= Au for some u in \(\displaystyle R^2\)- we have <Au AX- v>= 0.

But the adjoint (transpose in the case of real matrices) of a linear transformation, from vector space U to vector space V, is defined as the linear transformation from V back to U such that \(\displaystyle <Au, v>_V= <u, A^Tv>_U\), for all u in U, v in V. If <Aw, Ax- v>= 0, then <w,A^T(Ax- v)>= 0. But now that inner product is in \(\displaystyle R^2\) and w can be any vector in \(\displaystyle R^2\). That means we must have \(\displaystyle A^T(Ax- v)= 0\) or \(\displaystyle A^TAx= A^Tv\). Even if A is not a square matrix, \(\displaystyle A^TA\) is and may have an inverse. In that case \(\displaystyle x= (A^TA)^{-1}A^Tv\(\displaystyle . That "\(\displaystyle (A^TA)^{-1}A^T\)" is often referred to as the "generalized inverse" of A.\)\)
 
  • Like
Reactions: Opalg