Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
so this is for convenience, alright then, thanks! –  user825089 Oct 22 '12 at 11:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.