Edit:
I've actually found an error:
Instead of full SVD I had to use, "economy size" SVD, where $U$ has only first $n$ columns, and $\Sigma$ becomes a square matrix. I also forgot to take the transpose of $V$, that's why I was getting wrong numbers. SO, the primary question is solved 🙂
But it would be great if someone could answer the bonus question.
I need to solve the linear least squares problem $\min_{x}\|Ax – b\|_{2}^{2}$ given the matrix
$A = \begin{pmatrix}
1&1 \\
0&1 \\
-1&0
\end{pmatrix} $ and vector $b = \begin{pmatrix}
1 \\
1 \\
1
\end{pmatrix} $
The normal equations method $A^{T}Ax = A^{T}b$ and the QR-decomposition $Rx = Q^{T}b$
give the same result: $x = \begin{pmatrix}
-0.667 \\
1.333
\end{pmatrix}$
However, I have some questions about the SVD method.
My lecture notes say that the solution to the LLS is
$$x = V\Sigma^{-1}U^{T}b$$
But $$A_{32} = U_{33}\Sigma_{32}V_{22}^{T}$$
Therefore, $\Sigma$ is an $3\times2$ matrix, and the inverse is not defined for it.
I though $\Sigma^{-1}$ could mean $\Sigma^{+}$ (pseudo inverse), then the dimensions agree.
But the solution is $x = \begin{pmatrix}
1.333 \\
0.667
\end{pmatrix}$ which looks quite close to the first solution, but it doesn't give the least value.
Thank you for your time! I really hope someone could help me figure it out.
As a bonus question, why is it written $\min_{x}\|Ax – b\|_{2}^{2}$ ?
Isn't $\min_{x}\|Ax – b\|_{2}^{2} \Leftarrow\Rightarrow \min_{x}\|Ax – b\|_{2}$, because norm is always $\geq0$?
Best Answer
Answer to your bonus question: Yes, $\min_{x}\|Ax - b\|_{2}^{2} \Leftrightarrow \min_{x}\|Ax - b\|_{2}$ is true. When you compute the gradient of the first expression (with square) you have less complex expressions. So when least squares solutions are to be derived, the first expression is usually preferred.