SVD and linear least squares problem

Question

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

Answer 1

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.

Answer 2

Problem definition $$ \begin{align} \mathbf{A} x &= b\\ \left( \begin{array}{rr} 1 & 1 \\ 0 & 1 \\ -1 & 0 \\ \end{array} \right) \left( \begin{array}{c} x_{1} \\ x_{2} \end{array} \right) &= \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right) \end{align} $$

Normal equations $$ \begin{align} \mathbf{A}^{*} \mathbf{A} x &= \mathbf{A}^{*} b\\ \left( \begin{array}{cc} 2 & 1 \\ 1 & 2 \\ \end{array} \right) \left( \begin{array}{c} x_{1} \\ x_{2} \end{array} \right) &= \left( \begin{array}{c} 0 \\ 2 \end{array} \right) \end{align} $$ Given the inverse matrix $\left( \mathbf{A}^{*} \mathbf{A} \right)^{-1} = \frac{1}{3}\left( \begin{array}{rr} 2 & -1 \\ -1 & 2 \\ \end{array} \right)$, the solution is $$ x_{LS} = \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1} \mathbf{A}^{*}b = \frac{1}{3} \left( \begin{array}{r} -2 \\ 4 \end{array} \right) $$

SVD

The singular value decomposition is $$ \begin{align} \mathbf{A} &= \mathbf{U}\ \Sigma \ \mathbf{V}^{*} \\ &= \left( \begin{array}{ccc} \frac{1}{\sqrt{6}} \left[ \begin{array}{r} 2 \\ 1 \\ -1 \\ \end{array} \right] & \frac{1}{\sqrt{2}} \left[ \begin{array}{r} 0 \\ 1 \\ 1 \\ \end{array} \right] & \frac{1}{\sqrt{3}} \left[ \begin{array}{r} 1 \\ 1 \\ 1 \\ \end{array} \right] & \end{array} \right) % \left( \begin{array}{cc} \sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{array} \right) % \frac{1}{\sqrt{2}} \left( \begin{array}{rr} 1 & 1 \\ -1 & 1 \end{array} \right) \end{align} $$ The pseudoinverse solution provides the same answer $$ x_{LS} = \mathbf{A}^{\dagger} b = \mathbf{V}\ \Sigma^{\dagger} \mathbf{U}^{*} b = \frac{1}{3} \left( \begin{array}{rrr} 1 & -1 & -2 \\ 1 & 2 & 1 \\ \end{array} \right) \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right) = \frac{1}{3} \left( \begin{array}{r} -2 \\ 4 \end{array} \right) $$

Bonus answer: You can show that when the inverse to the product matrix exists, it must be the pseudoinverse. Start with the basic definitions $$ \mathbf{A}= \mathbf{U} \ \Sigma \ \mathbf{V}^{*}, \quad \mathbf{A}^{*}= \mathbf{V} \ \Sigma^{\mathrm{T}}\ \mathbf{U}^{*}, \quad \mathbf{A}^{\dagger} = \mathbf{V} \ \Sigma^{\dagger} \mathbf{U}^{*}. $$ To get there, use the following identities $$ \Sigma = \left( \begin{array}{cc} \sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{array} \right), \quad % \Sigma^{\mathrm{T}} = \left( \begin{array}{ccc} \sqrt{3} & 0 & 0\\ 0 & 1 & 0 \end{array} \right), \quad % \Sigma^{\dagger} = \left( \begin{array}{ccc} \frac{1}{\sqrt{3}} & 0 & 0\\ 0 & 1 & 0 \end{array} \right). $$ Given $\mathbf{S} = \left( \begin{array}{cc} \sqrt{3} & 0 \\ 0 & 1 \end{array} \right),$ $$ \Sigma = \left( \begin{array}{c} \mathbf{S} \\ 0 \end{array} \right)_{3\times 2}, \quad % \Sigma^{\mathrm{T}} = \left( \begin{array}{cc} \mathbf{S} & 0 \end{array} \right)_{2\times 3}, \quad % \Sigma^{\dagger} = \left( \begin{array}{cc} \mathbf{S}^{-1} & 0 \end{array} \right)_{2\times 3} $$

When the normal equations matrix product exists, it must be the same as the pseudoinverse: $$ \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1} \mathbf{A}^{*} = \left( \mathbf{V}\ \mathbf{S}^{2}\ \mathbf{V}^{*} \right)^{-1} \mathbf{V} \ \Sigma^{\mathrm{T}}\ \mathbf{U}^{*} = \left( \mathbf{V}\ \mathbf{S}^{-2}\ \mathbf{V}^{*} \right) \mathbf{V}\ \Sigma^{\mathrm{T}}\ \mathbf{U}^{*} = \mathbf{V}\ \Sigma^{\dagger}\ \mathbf{U}^{*} = \mathbf{A}^{\dagger} $$