# Least square solution

I have been given a system of linear equations as follows: $$2x_1-x_2-x_3=1\\ -x_1+x_2+3x_3=-1\\ 3x_1-2x_2-4x_3=3$$ I am told to find the least square solution(s) for the system. So I obviously made it into a matrix as follows.

$$\begin{pmatrix} 2 & -1 & -1 \\ -1&1&3\\3&-2&-4\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}1\\-1\\3\end{pmatrix}$$ and $$A^T = \begin{pmatrix} 2 & -1 & 3\\-1 & 1 & -2 \\ -1 & 3 & -4\end{pmatrix}$$

So when I do $A^TA$, I get $$\begin{pmatrix} 14 & -9 & -17\\-9 & 6 & 12 \\ -17 & 12 & 26\end{pmatrix}$$

Problem is that it's not invertible. So now I'm not sure if I'm doing this the right way or using an incorrect method. Also I've checked the numbers at least ten times and done the calculations multiple times and have come to the same matrix every time. Anybody know what to do?

• Have you seen the pseudoinverse? – Michael Biro Dec 10 '14 at 22:34
• I'm not sure what that is. We may have but I can't remember. – samir91 Dec 10 '14 at 22:40
• $A$ does not have full rank, so $A^TAx = A^Tb$ does not necessarily have a solution. Instead, find $x^+ = A^+b$, where $A^+$ is the pseudoinverse of $A$. – Michael Biro Dec 10 '14 at 22:50

the least squares solution is $$x_1 = 0, x_2 = -{4 \over 3} \mbox{ and } x_3 = 0.$$

if yo row reduce your matrix $A$ you will find that the third column of $A$ is the sum of twice the first coulmn and five times the second column. you only need the first two columns of $A.$ with that the normal equation $A^TAx = A^Tb,$ keeping only the first two columns of your original $A$ becomes $\pmatrix{14 & -9 \cr -9 & 6} \pmatrix{x_1 \cr x_2} = \pmatrix{12 \cr -8}$ with the solution $x_1 = 0$ and $x_2 = -{4 \over 3}.$

• The answer at the back of the book says $x_1=-2t$$,$$x_2=-5t-\frac{4}{3}$$and$$x_3=t$ – samir91 Dec 11 '14 at 18:18
• @samir91, oh sure, i forgot to add the solution $Ax = 0$ which is a multiple of $(-2, -5, 1)^T.$ – abel Dec 11 '14 at 18:57

Recall what the method of least squares is designed to accomplish.

You have a system $Ax = b$ that is typically overconstrained; no $x$ exists that solves the system exactly. You can "do the best you can in the least-squares sense" by instead finding an $x$ that minimizes $$E(x) = \|Ax-b\|^2;$$ finding such an $x$ is equivalent to solving the system $$A^TAx = A^Tb.$$

Note that nobody said that the minimizer $x$ must be unique; in fact if $A$ is singular you can explicitly construct entire families of vectors for which $E$ is minimized. The key point, though, is that $A^TAx = A^Tb$ is guaranteed to always have (at least one) solution, even if $A^TA$ is singular. (To see this, decompose your space into the span of the columns of $A$, and the complement of this span; you can then write $b = Ac + d$ where $d$ is in the complement. Thus $A^Tb = A^TAc + A^Td = A^TAc + 0$ and you see that $c$ is a solution to the system.)

Computing the pseudoinverse is a perfectly good way to find this (guaranteed to exist) $x$. In practice the most common way of doing so is using the QR decomposition, or in a pinch, the slightly more expensive SVD.

As mentioned in the comment, you can obtain the least-squares solution, by using the pseudo-inverse and compute $x = A^{+} b$ as your solution. Since the Pseudo-Inverse or Moore-Penrose inverse might be probably more unfamiliar concept, here is another way to deal with the problem, using standard Least-Squares Approximation.

Let's assume your system has a solution at all, then every solution can be represented as $x_{sol} = x_p + N*v$, $N\in R^{n\times k}$, $v \in \mathbb{R}^k$, where $Ax_p = b$ and the columns of $N$ span the nullspace of $A$. Now, you are searching for $v \in \mathbb{R}^k$, such that $\left| N*v - (-x_p)\right|_2$ is minimized, which poses a Least-Sqaures approximation problem! (Notice, this time $N$ is per construction full column rank).

Hence your solution for $v$ will be $v = -(N^T N)^{-1}N^T x_p$ and therefore your solution for $x$ will be $(I-N(N^T N)^{-1}N^T)x_p$. Notice that $(I-N(N^T N)^{-1}N^T)x_p$ is basically the orthogonal projection of a particular solution $x_p$ onto the orthogonal complentary space of the range of $A$.