# Find the least squares solution for rank deficient system

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?

• 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. Aug 1, 2016 at 23:05
• the only good answer to this problem was downvoted
– user3417
Oct 16, 2018 at 22:10

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.

• 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. Dec 1, 2018 at 9:19
• @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. Dec 1, 2018 at 17:33
• Why even bring the pseudoinverse to the discussion? Dec 1, 2018 at 17:36
• The pseudoinverse provides the most general form of the particular solution (the range space component). Dec 1, 2018 at 18:27

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.

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$

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

• @RodrigodeAzevedo Haha I think it might be. My up-vote will bring you back up to zero ;p Aug 2, 2016 at 11:48
• Then remove the worst Sep 27, 2020 at 19:05

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

• The thing is tho that the inverse does not exist Aug 2, 2016 at 3:53

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

• The OP is looking for the least-squares solution, which always exist. Aug 1, 2016 at 23:40
• @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. Aug 1, 2016 at 23:45
• @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)$ Aug 2, 2016 at 0:33
• @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/… Nov 22, 2018 at 17:48
• @dantopa SVD tells me there is always a least-squares solution. One of us is making unwarranted assumptions. Nov 30, 2018 at 19:16