0
$\begingroup$

I am currently studying this answer on the Moore-Penrose pseudoinverse and the Euclidean norm by the user "Etienne dM". The first point of their answer proceeds as follows:

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

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

I realise that $x = A^+ y$, but I don't understand how any of this implies that "$A^+ b$ is as close as possible to $y$ in terms of the Euclidean norm $\lVert Ax-b\rVert_2$". The way I see it is that we have 4 facts:

  1. $\lVert Az - b \rVert_2^2 = \lVert Ax - b \rVert_2^2 + \lVert A(z - x) \rVert_2^2 + 2(z - x)^T A^T (Ax - b) \ge \lVert Ax - b \rVert_2^2 + 2(z - x)^T A^T (Ax - b)$;

  2. Because $(AA^+)^T = AA^+$, $A^T(Ax - b) = ((AA^+)A)^T b - A^T b = 0$;

  3. Singular value decomposition (SVD): $A^+ = VD^+U^T = V \Sigma^+ U^T$;

  4. $x = A^+ y$.

Supposedly, these 4 facts together prove that "$A^+ b$ is as close as possible to $y$ in terms of the Euclidean norm $\lVert Ax-b\rVert_2$". However, I do not see how this is so.

This answer by "Ben Grossmann" is supposed to show something similar. I can see how this answer is related to what "Etienne dM" did in their proof, but I do not see how it is the same.

I suspect that I am lacking some assumed, fundamental knowledge that "Etienne dM" had in constructing this proof, and so I am unable to see how these 4 facts combine to prove what is claimed. I would greatly appreciate it if people would please take the time to carefully explain this to me.

This related question is for the limit definition of pseudoinverse.

$\endgroup$
16
  • $\begingroup$ The phrase "$A^+ b$ is as close as possible to $y$ in terms of the Euclidean norm $\lVert Ax-b\rVert_2$" was chosen a little bit unlucky. All that it means is that $A^+b = \arg\min_x \|Ax-b\|_2$, and that is clear from showing $\|Az-b\|_2 \ge \|A(A^+b) - b\|_2$ for all $z$, i.e. point (1). (It would have been better to say that $A^+b$ is the input for which the function value of $f(x)=Ax$ comes as close as possible to $y$). In any case I do not really see how this question really differs from your previous one, so I will flag it as a duplicate for now. $\endgroup$
    – Hyperplane
    Commented Aug 3, 2020 at 16:50
  • $\begingroup$ @Hyperplane Ahh, phrasing it that way makes a lot more sense. With regards to your next point, the author actually shows that $\rVert Az-b \lVert_2^2 \geq\rVert Ax-b \lVert_2^2$, right? $\endgroup$ Commented Aug 3, 2020 at 16:59
  • 1
    $\begingroup$ The objective is to find the vector $x$ for which $Ax$ is as close as possible to $y$. And if one can prove that for the choice $x=A^+y$ holds that $\operatorname{dist}_\text{eucl.}(Az, y) \ge \operatorname{dist}_\text{eucl.}(Ax, y)$ for any other vector $z$, then well, you have found your optimum solution in terms of the euclidean distance metric. $\endgroup$
    – Hyperplane
    Commented Aug 3, 2020 at 17:57
  • 1
    $\begingroup$ @ThePointer It seems as though that you are having trouble parsing the definition of a "least squares solution." I would say that $x$ is a least squares solution if $z = x$ minimizes $\|Az - y\|$, with is to say that $\|Ax - y\|$ is smaller than or equal to $\|Az - y\|$ for all choices of $z$. Do you agree with that? $\endgroup$ Commented Aug 3, 2020 at 18:06
  • 1
    $\begingroup$ @ThePointer Missed this comment earlier. Anyway, glad it made sense! $\endgroup$ Commented Aug 8, 2020 at 20:21

0