Moore-Penrose pseudoinverse and the Euclidean norm

Solution 1:

Eqn. (2.46) proposes to look at the minimizer $x_\alpha$ of the functional $$J_\alpha(x) := |A x - y|^2 + \alpha |x|^2.$$ For any finite $\alpha > 0$, the functional is strictly convex and has a unique minimizer $x_\alpha$; it is the smallest among those $x$ that produce the same residual magnitude $|A x - y|$. Minimization wrt $x$ gives $x_\alpha = (A^\top A + \alpha I)^{-1} A^\top y$. To see this, write the norm $|\cdot|^2$ in terms of the scalar product $\langle \cdot, \cdot \rangle$.

Ad 1. Suppose $A x = y$ has a solution $x^*$. The set of solutions is the convex set $(x^* + \ker A)$. So, there is only one solution that has minimal norm: the orthogonal projection of $0$ onto that set. As $\alpha \searrow 0$, the residual term becomes more important, and $A x = y$ is eventually enforced. Therefore, $x_0 := \lim_{\alpha \searrow 0} x_\alpha$ is the minimal-norm solution of $A x = y$.

Ad 2. If $A x = y$ has no solution, the residual $|A x - y|$ still has a minimum, which is selected for in the limit $\alpha \searrow 0$.

Solution 2:

Let $x$ be $A^+y$.

2. Let me begin by the second point. For all $z$, we have: \begin{align} \lVert Az-y \rVert_2^2 &= \lVert Ax-y \rVert_2^2 + \lVert A(z-x) \rVert_2^2 + 2 (z-x)^TA^T(Ax-y)\\ & \geq \lVert Ax-y \rVert_2^2 + 2 (z-x)^TA^T(Ax-y) \end{align} Moreover, because $(AA^+)^T = AA^+$, $$ A^T(Ax-y) = ((AA^+)A)^Ty - A^Ty = 0$$ Thus, we prove that for all $z$, $\rVert Az-y \lVert_2^2 \geq\rVert Ax-y \lVert_2^2$, that is to say $A^+y$ is as close as possible to $y$ in term of the Euclidian norm $\lVert Ax-y\rVert_2$.

3. Now, let us suppose that there exist $z$ so that $Az=y$. According to the first point, we have $\rVert Ax-y\lVert_2=0$, so $x$ is a solution. Moreover, for all solution $z$, $$ \lVert z \rVert_2^2=\lVert x \rVert_2^2 + \lVert z-x \rVert_2^2 + 2x^T(z-x)$$ Yet, because $A^+Ax=x$ and $(A^+A)^T=A^+A$, $$x^T(x-z) = (A^+Ax)^T(x-z) = x^T(A^+Ax-z) = x^T(A^+y-z)=0$$ Thus, $\lVert z \rVert_2^2 \geq \lVert x \rVert_2^2$, that is to say that $x$ is the solution with the minimal Euclidian norm.