# Limit definition of pseudoinverse: $A^+ b$ is as close as possible to $y$ in terms of the Euclidean norm $\lVert Ax-b\rVert_2$

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$$". I would greatly appreciate it if people would please take the time to explain this to me.

• You might find this post helpful. Aug 3, 2020 at 11:32
• @BenGrossmann Eh, I'm not exactly well-acquainted with the theory of singular value decompositions either. Aug 3, 2020 at 11:33
• What definition of $A^+$ are you familiar with, then? Aug 3, 2020 at 11:33
• @BenGrossmann According to my question math.stackexchange.com/q/3525644/356308 , the author introduced and defined the pseudoinverse of a matrix $\mathbf{A}$ as $$\mathbf{A}^+ = \lim_{\alpha \searrow 0^+}(\mathbf{A}^T \mathbf{A} + \alpha \mathbf{I} )^{-1} \mathbf{A}^T. \tag{2.46}$$ Not a very insightful introduction/definition, but that's it. Aug 3, 2020 at 11:35
• Thanks for pointing that out. Actually, I this definition might be easier to work with in our case Aug 3, 2020 at 11:37

We assume that $$(A^TA + \alpha I)^{-1}A^T$$ indeed has a limit as $$\alpha \to 0^+$$. Let $$x$$ be given by $$x = A^+ y = \lim_{\alpha \to 0^+ }[(A^TA + \alpha I)^{-1}A^T y].$$
Consider any $$\alpha > 0$$. We note that $$x_\alpha = (A^TA + \alpha I)^{-1}A^Ty$$ is the unique solution to the system $$(A^TA + \alpha I)x_{\alpha} = A^Ty,$$ and that $$x_{\alpha} \to x$$ as $$\alpha \to 0^+$$. It follows that $$\|A^Ty - A^TAx\| = \lim_{\alpha \to 0^+}\|A^T y - A^TAx_{\alpha}\| = \lim_{\alpha \to 0^+}\|\alpha x_{\alpha}\| \\ \qquad \qquad = \lim_{\alpha \to 0^+} \alpha \|x_{\alpha}\| = \lim_{\alpha \to 0^+} \alpha \|x\| = 0.$$ So, we indeed have $$A^TAx = A^Ty$$, which means that $$x$$ is a least-squares solution to $$Ax = y$$, which is what we wanted.
• I forgot about this question. Where did $\|A^Ty - A^TAx\|$ come from? I can't trace it back to anything that came before. Aug 7, 2020 at 19:17
• We want to show that $A^Ty = A^TAx$, which is the same as showing that $\|A^Ty - A^TAx\| = 0$ Aug 7, 2020 at 20:43
• If $Ax = y$, then we have that $x = A^+ x = \lim_{\alpha \to 0^+ }[(A^TA + \alpha I)^{-1}A^T Ax]$, which doesn't seem correct? Also, why do we want to show that $A^Ty = A^TAx$? I don't see how this follows from the work that was done before it. So, then, what was the point of the first half of the proof, and what is the reasoning for why the second part follows from it? Aug 8, 2020 at 0:37
• @ThePointer That should say $x = A^+y$, sorry for the typo Aug 8, 2020 at 10:32
• Oh, ok. And how did you get that that $\lim_{\alpha \to 0^+}\|A^T y - A^TAx_{\alpha}\| = \lim_{\alpha \to 0^+}\|\alpha x_{\alpha}\|$? Aug 8, 2020 at 17:24