# Intersection of Lines / Least Squares

#### xasmx

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
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.\)\)

Opalg