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.

I read about the SVD theory and its usage for solving Linear Equation System. I saw many papers mentioning property of the solution yet no proof of it.

The Property: The solution given the Pseudo Inverse ( $ V {\Sigma}^{1} {U}^{H} $ ) minimizes both the error norm and the solution norm.

The minimization of the error norm is easily proved using the Normal Equations ( $ \hat{x} $ is the Least Squares solution iff $ {A}^{H} A \hat{x} = {A}^{H} b $ ).

Yet beyond the intuition of $ \hat{x} $ must lie in the Row Space of A hence its norm is minimized I couldn't find a formal proof for that.

Moreover, Let's define $ A = U \Sigma {V}^{H} $ then when we calculate its pseudo inverse we we handle $ \Sigma $ with extra care, only reversing its non zero entries. What the formal reasoning for that?

Thanks!

share|improve this question
    
I don't quite understand you question. What is the "solution" in your second paragraph for? I would suggest you state the property completely and give the references(book, chapter, page, etc.) –  Jack Jul 6 '11 at 16:17

1 Answer 1

up vote 6 down vote accepted

As Jack pointed out in a comment, the question is somewhat unclear. I interpret it as follows:

You have a system $Ax=b$ of linear equations. You understand why $\hat x=A^+b$, where $A^+$ is the (Moore–Penrose) pseudo-inverse of $A$, minimizes the error norm $|Ax-b|$, but you want to know why, if $Ax=b$ has solutions, $\hat x$ is the unique solution that minimizes the solution norm $|x|$.

You state that $\hat x$ must lie in the row space of $A$. That's true in the real case; more generally, in the complex case, $\hat x$ must lie in the column space of $A^*$, or equivalently in the orthogonal complement of the null space of $A$. This can be seen in two different ways:

Any solution $x$ of $Ax=b$ can be written as $x=u+v$, where $u$ is in the null space of $A$ and $v$ in its orthogonal complement. Then $|x|^2=|u|^2+|v|^2$. Since $u$ is in the null space of $A$, $v$ also solves $Ax=b$. Thus, the solution with minimal norm must have $u=0$, and must therefore lie in the orthogonal complement of the null space.

Alternatively, this can be derived using constrained minimization. To minimize $|x|^2$ under the system of constraints $Ax=b$, we introduce a vector $\lambda$ of Lagrange multipliers and consider the function $f(x)=x^*x-(Ax-b)^*\lambda$. Its gradient is $2x-A^*\lambda$, and setting this to zero yields $\hat x=A^*\lambda/2$. Thus $\hat x$ is in the column space of $A^*$.

Now there can be only one solution of $Ax-b$ in the orthogonal complement of the null space of $A$. If $x_1$ and $x_2$ are two solutions, then $A(x_1-x_2)=Ax_1-Ax_2=(Ax_1-b)-(Ax_2-b)=0$, so their difference is in the null space of $A$. If the solutions are both in the orthogonal complement of the null space, then so is their difference; since the difference is both in the null space and in its orthogonal complement, it must be zero.

Thus it suffices to show that $A^+b$ solves $Ax-b$ and lies in the column space of $A^*$. We know that if $Ax-b$ has solutions then $A^+b$ is one of them, because $A^+b$ minimizes the error norm. We also know that $A^+b$ lies in the column space of $A^*$, since $A^+b=(A^*A^{+*}A^+)b=A^*(A^{+*}A^+b)$ .

share|improve this answer
    
A very clear explanation. –  user1551 Oct 9 '11 at 8:32
    
@user1551: Thanks :-) –  joriki Oct 9 '11 at 9:00

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.