2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The matrices are right there - for A, just pull out the coefficients of the variables on the left-hand side of each linear equation and line them up, and for B, get the constants on the right-hand side. $\endgroup$ – ConMan Aug 1 '16 at 23:05
  • 2
    $\begingroup$ the only good answer to this problem was downvoted $\endgroup$ – user3417 Oct 16 '18 at 22:10
1
$\begingroup$

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}^T$, 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}$$

$\endgroup$
  • 1
    $\begingroup$ @RodrigodeAzevedo Haha I think it might be. My up-vote will bring you back up to zero ;p $\endgroup$ – Carser Aug 2 '16 at 11:48
  • $\begingroup$ Why do you have two nearly identical answers to this question? $\endgroup$ – Morgan Rodgers Mar 14 '17 at 3:56
  • $\begingroup$ @MorganRodgers Because one is better than the other. $\endgroup$ – Rodrigo de Azevedo Mar 14 '17 at 7:48
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the RHS of the normal equations is zero, there will be infinitely many solutions when $\bf A$ does not have full column rank. Lastly, I do not understand your hostility towards the zero solution. $\endgroup$ – Rodrigo de Azevedo Dec 1 '18 at 9:19
  • $\begingroup$ @Rodrigo de Azevedo: Here is a picture in 3D: math.stackexchange.com/questions/2253443/…. The least squares solution $$ x_{LS} = \color{blue}{\mathbf{A}^{+} b} + \color{red}{ \left( \mathbf{I}_{n} - \mathbf{A}^{+} \mathbf{A} \right) y}, \quad y \in \mathbb{C}^{n} \tag{1} $$ The topology of the particular solution is a point (finite), and the homogeneous solution is a hyperplane. The pseudoinverse solution is where the homogenous solution intersects the range space. There is no intersection here. $\endgroup$ – dantopa Dec 1 '18 at 17:33
  • $\begingroup$ Why even bring the pseudoinverse to the discussion? $\endgroup$ – Rodrigo de Azevedo Dec 1 '18 at 17:36
  • $\begingroup$ The pseudoinverse provides the most general form of the particular solution (the range space component). $\endgroup$ – dantopa Dec 1 '18 at 18:27
0
$\begingroup$

$$A = \left [\begin{array}{cc} 1 & -1 \\ 1 & -1 \\ \end{array} \right], \quad b = \begin{bmatrix}4\\6 \end{bmatrix} $$

$\endgroup$
  • $\begingroup$ The thing is tho that the inverse does not exist $\endgroup$ – Yusha Aug 2 '16 at 3:53
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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$...

$\endgroup$
  • 1
    $\begingroup$ The OP is looking for the least-squares solution, which always exist. $\endgroup$ – Rodrigo de Azevedo Aug 1 '16 at 23:40
  • $\begingroup$ @RodrigodeAzevedo What would it be in this case, and is it unique? Yes maybe you can identify a LS solution, but what would the meaning of it be here with only two points? The OP's suggestion of inv(A'*A)*A'*b results in [NaN;NaN] according to MATLAB. $\endgroup$ – Carser Aug 1 '16 at 23:45
  • 1
    $\begingroup$ @Carser it's not necessary for the system to have a solution. This is the essence of least squares. Find the $(x,y)$ that minimises the distance between the vectors $(1,1)'x +(-1,-1)'y$ and $(4,6)$ $\endgroup$ – theoGR Aug 2 '16 at 0:33
  • $\begingroup$ @theoGR You are of course correct, you can find a LS fitting here, but what is it worth when there are only two datum and a singular matrix? $\endgroup$ – Carser Aug 2 '16 at 0:41
  • 1
    $\begingroup$ @Rodrigo de Azevedo: There is no (non-trivial) least squares solution when the data vector s in the null space. See, for example, math.stackexchange.com/questions/2244851/… $\endgroup$ – dantopa Nov 22 '18 at 17:48

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.