Suppose Ax=b is any underdetermined linear system. Prove that the minimum-norm solution to an underdetermined system can be obtained by projecting any solution of the system onto range space of transpose of the matrix A That is, if P is the orthogonal projection onto R(A'),then the minimum norm solution z is given by z=P*y,where y is any solution.
Asked
Active
Viewed 104 times
1 Answers
2
Let $\mathbf{y}$ denote some solution to the system First, note that we can express $\mathbf{y}$ as $\mathbf{y} = \mathbf{z} + \mathbf{y'}$ where $\mathbf{z}$ is in the rowspace and $\mathbf{y'}$ is in the nullspace. It follows that $\mathbf{z}$ is the orthogonal projection of $\mathbf{y}$ onto the rowspace. Since we have $$\mathbf{b} = A\mathbf{y} = A\mathbf{z} + A\mathbf{y'} = A\mathbf{z}$$ It follows that $\mathbf{z}$ is also a solution to the system.
Now any solution of the system can be expressed as the sum of a homogenous solution to a particular solution. That is, if $\mathbf{x}$ is any solution, we can write $$\mathbf{x} = \mathbf{z} + \mathbf{x'}$$ for some $\mathbf{x}'$ in the nullspace. Since $\mathbf{z}$ is in the rowspace and $\mathbf{x'}$ is in the nullspace, they are orthogonal. By the Pythagorean theorem, we have $$\|\mathbf{x}\|^2 = \|\mathbf{z}\|^2 + \|\mathbf{x'}\|^2 \ge \|\mathbf{z}\|^2$$ with equality if and only if $$\|\mathbf{x'}\|^2 = 0 \iff \mathbf{x'} = \mathbf{0} \iff \mathbf{x} = \mathbf{z}$$
EuYu
- 41,421
-
1Thank you a lot for your reply. I am highly grateful to you..thank you again. – Sujeet Apr 21 '13 at 13:30
-
@Sujeet It was my pleasure. – EuYu Apr 21 '13 at 20:03