Finding the pseudoinverse using Lagrange multipliers

Question

Let $A\in R^{m*n}$ and $b\in Range(A)$. Then how can we find the minimum norm solution to the $Ax=b$ using lagrange multiplier(basically looking for proof of pseudoinverse using lagrange multipliers). Here is my attempt: $$min_x\frac{1}{2}||x||^2\text{ , s.t }Ax=b$$ $$L(x,\lambda)=\frac{1}{2}||x||^2+\lambda^T(Ax-b)$$ $$\triangledown L(x,\lambda)=x+A^T\lambda=0$$ which gives, $x=-A^T\lambda$ and $-AA^T\lambda=b$. Now $AA^T$ might not be invertible, so how can we proceed further to solve for $x$ and $\lambda$? Any hints?

Answer 1

Let $A=U\Sigma V^T$ be the economy SVD of $A$; that is, $$U\in\mathbb{R}^{m\times p} \quad \Sigma\in\mathbb{R}^{p\times p} \quad V\in\mathbb{R}^{n\times p} \quad U^TU=V^TV=I_p \quad p=\mathop{\textrm{rank}}(A)=\mathop{\textrm{rank}}(\Sigma)$$ Since we know that $b\in\mathop{\textrm{Range}}{A}$, it must be the case that $b=U q$ for some vector $q\in\mathbb{R}^p$. Similarly, the optimality condition $x+A^T\lambda=0$ implies that $x\in\mathop{\textrm{Range}}(A^T)$, which means that $x=Vr$ for some vector $r\in\mathbb{R}^p$. So now we have $$\begin{aligned} &Ax=b \quad\Longrightarrow\quad U\Sigma V^T (Vr) = U q \quad\Longrightarrow\quad r = \Sigma^{-1} q\\ &\quad\Longrightarrow\quad x = Vr = V\Sigma^{-1}q = V\Sigma^{-1}U^TUq=V\Sigma^{-1}U^T b = A^\dagger b. \end{aligned}$$ So the solution is indeed identical to the one obtained from the pseudoinverse.