Find the least squares solution to the system
$$x - y = 4$$
$$x - y = 6$$
Normally if I knew what the matrix $A$ was and what $b$ was I could just do $(A^TA)^{-1} A^Tb$, but in this case I'm not sure how to set up my matrices. How can I find the least square solution to the system?
On
The linear system
$$\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
has no solution. Left-multiplying both sides by $\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix}^T$, we obtain the normal equations
$$\begin{bmatrix} 2 & -2\\ -2 & 2\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 10 \\ -10\end{bmatrix}$$
Dividing both sides by $2$ and removing the redundant equation,
$$x - y = 5$$
Thus, there are infinitely many least-squares solutions. One of them is
$$\begin{bmatrix} \hat x\\ \hat y\end{bmatrix} = \begin{bmatrix} 6\\ 1\end{bmatrix}$$
The least-squares solution is a solution to the normal equations, not to the original linear system.
On
First, choose points (x,y) that satisfy each equation.
$\begin{cases} x - y = 4, & \text{(6,2)} \\ x - y = 6, & \text{(10,4)} \end{cases}$
Then, proceed as usual
$Ax = \begin{bmatrix} 1 & 6 \\ 1 & 10 \\ \end{bmatrix} \begin{bmatrix} b \\ m \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix}$
$\begin{bmatrix} b \\ m \\ \end{bmatrix} =\begin{bmatrix} 5 \\ 1/2 \\ \end{bmatrix}$
$y = 1/2x + 5$
On
We have the linear system
$$\begin{bmatrix} 1 & -1\\ 1 & -1\end{bmatrix} \begin{bmatrix} x\\ y\end{bmatrix} = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
which can be rewritten in the form
$$\begin{bmatrix} 1\\ 1\end{bmatrix} \eta = \begin{bmatrix} 4 \\ 6\end{bmatrix}$$
where $\eta = x - y$. Left-multiplying both sides by $\begin{bmatrix} 1\\ 1\end{bmatrix}^\top$, we obtain $2 \eta = 10$, or, $\eta = 5$. Hence,
$$x - y = 5$$
Thus, there are infinitely many least-squares solutions. One of them is
$$\begin{bmatrix} \hat x\\ \hat y\end{bmatrix} = \begin{bmatrix} 6\\ 1\end{bmatrix}$$
On
Problem statement: underdetermined system
Start with the linear system $$ \begin{align} \mathbf{A} x &= b \\ % \left[ \begin{array}{cc} 1 & -1 \\ 1 & -1 \\ \end{array} \right] % \left[ \begin{array}{c} x \\ y \end{array} \right] % &= % \left[ \begin{array}{c} 4 \\ 6 \end{array} \right] % \end{align} $$
The system has matrix rank $\rho = 1$; therefore, if a solution exists, it will not be unique.
Provided $b\notin \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)}$, we are guaranteed a least squares solution $$ x_{LS} = \left\{ x\in\mathbb{C}^{2} \colon \lVert \mathbf{A} x_{LS} - b \rVert_{2}^{2} \text{ is minimized} \right\} \tag{1} $$
Subspace resolution
By inspection, we see that the row space is resolved as $$ \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A} \right)} = \color{blue}{\left[ \begin{array}{r} 1 \\ -1 \end{array} \right]} \oplus \color{red}{\left[ \begin{array}{c} 1 \\ 1 \end{array} \right]} $$ The column space is resolved as $$ \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)} = \color{blue}{\left[ \begin{array}{c} 1 \\ 1 \end{array} \right]} \oplus \color{red}{\left[ \begin{array}{r} -1 \\ 1 \end{array} \right]} $$
The coloring indicates vectors in the $\color{blue}{range}$ space and the $\color{red}{null}$ space.
Finding the least squares solution
Since there is only one vector in $\color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)}$, the solution vector will have the form $$ \color{blue}{x_{LS}} = \alpha \color{blue}{\left[ \begin{array}{r} 1 \\ -1 \end{array} \right]} $$ The goal is to find the constant $\alpha$ to minimize (1): $$ \color{red}{r}^{2} = \color{red}{r} \cdot \color{red}{r} = \lVert \color{blue}{\mathbf{A} x_{LS}} - b \rVert_{2}^{2} = 8 \alpha ^2-40 \alpha +52 $$ The minimum of the polynomial is at $$ \alpha = \frac{5}{2} $$
Least squares solution
The set of least squares minimizers in (1) is then the affine set given by $$ x_{LS} = \frac{5}{2} \color{blue}{\left[ \begin{array}{r} 1 \\ -1 \end{array} \right]} + \xi \color{red}{\left[ \begin{array}{r} 1 \\ 1 \end{array} \right]}, \qquad \xi\in\mathbb{C} $$
The plot below shows how the total error $\lVert \mathbf{A} x_{LS} - b \rVert_{2}^{2}$ varies with the fit parameters. The blue dot is the particular solution, the dashed line homogeneous solution as well as the $0$ contour - the exact solution.
Addendum: Existence of the Least Squares Solution
To address the insightful question of @RodrigodeAzevedo, consider the linear system:
$$ \begin{align} \mathbf{A} x &= b \\ % \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right] % \left[ \begin{array}{c} x \\ y \end{array} \right] % &= % \left[ \begin{array}{c} 0 \\ 1 \end{array} \right] % \end{align} $$
The data vector $b$ is entirely in the null space of $\mathbf{A}^{*}$: $b\in \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)}$
As pointed out, the system matrix has the singular value decomposition. One instance is: $$\mathbf{A} = \mathbf{U}\, \Sigma\, \mathbf{V}^{*} = \mathbf{I}_{2} \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right] \mathbf{I}_{2}$$ and the concomitant pseudoinverse, $$\mathbf{A}^{\dagger} = \mathbf{V}\, \Sigma^{\dagger} \mathbf{U}^{*} = \mathbf{I}_{2} \left[ \begin{array}{cc} 1 & 0 \\ 0 & 0 \\ \end{array} \right] \mathbf{I}_{2} = \mathbf{A}$$
Following least squares canon, the particular solution to the least squares problem is computed as $$ \color{blue}{x_{LS}} = \mathbf{A}^{\dagger} b = \color{red}{\left[ \begin{array}{c} 0 \\ 0 \\ \end{array} \right]} \qquad \Rightarrow\Leftarrow $$ The color collision (null space [red] = range space [blue]) indicates a problem. There is no component of a particular solution vector in a range space!
Mathematicians habitually exclude the $0$ vector a solution to linear problems.
Your matrix is just the coefficients of your system of equations. In this case $$ x-y = 4 $$ $$ x-y = 6 $$ leads to $$ \begin{bmatrix} 1 & -1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 4 \\ 6 \end{bmatrix} $$ but you should see that there is no solution to this since you can't have $x-y$ be both $4$ and $6$...