Find all the least squares solutions of Ax=b

Question

Find all least squares solutions of A x = b, where A =

\begin{bmatrix} 1 & 3 \\[0.3em] -2 &-6 \\[0.3em] 3 & 9 \end{bmatrix}

and b = \begin{bmatrix} 1 \\[0.3em] 0 \\[0.3em] 1 \end{bmatrix}

and confirm that all the solutions have the same error vector (and hence the same least squares error). Compute the least-squares error.

The system that corresponds to the reduced row echelon form of the augmented matrix is $x_1 + 3x_2 =0, 0=1, 0=0 $ since the second equation cannot be solved the system is inconsistent

I'm not sure how to calculate the least squares solutions of A x = b because the inverse of $A^TA$ does not exist and so I can't solve the normal equations $A^TAx=A^Tb$ for x

score 2 · Answer 1 · answered May 14 '13 at 00:55

2

Even though $A^TA$ is singular, you can solve the normal equations. Note that, from a theoretical perspective, $A^Tb$ is in the column space (image) of $A^T$, and the column space of $A^TA$ is the same subspace — again, for emphasis, always.

answered May 14 '13 at 00:55

Ted Shifrin

115,160

Please would it be possible to explain how the normal equations can be solved? – user51462 May 14 '13 at 01:01
1

Without inverses. Just solve with an augmented matrix, as you would any inhomogeneous system. – Ted Shifrin May 14 '13 at 01:50
Please could you explain how i would go about finding the error in this case. Thanks – user51462 May 14 '13 at 02:30
How do you usually find the error? – Ted Shifrin May 14 '13 at 03:45

score 0 · Answer 2 · answered Jan 22 '14 at 17:27

You want to choose $x$ that minimizes in a least squares sense the error of $Ax = b$. So you want to minimize $(Ax-b)^\intercal(Ax - b) = x^\intercal A^\intercal Ax - x^\intercal A^\intercal b - b^\intercal A x + b^\intercal b = x^\intercal A^\intercal Ax - 2 b^\intercal A x + b^\intercal b$.

At a local minimum the partial derivatives with respect to each element of $x$ will be 0.

So we want to solve $2A^\intercal A x - 2A^\intercal b = 0$, which is equivalent to $A^\intercal A x = A^\intercal b$. Since $A^\intercal A$ is square, so we can try to invert it and solve $x = (A^\intercal A)^{-1}A^\intercal b$

That's a linear equation, so it only has one solution if it has any. So there can only be one minimum.

Note that $A^\top A$ is not invertible in this case. – Ted Shifrin Jul 06 '14 at 02:44 — Ted Shifrin, Jul 06 '14 at 02:44

Find all the least squares solutions of Ax=b

2 Answers2