Is the pseudoinverse matrix the solution to the least squares problem? I'm trying to verify that, given a matrix M, the pseudo-inverse $$M^{+}=(M^TM)^{-1}M^T$$
is the solution for the least squares.. but something went wrong and I can't undestand why...
$$e=\frac{1}{2}||y-Mx||=\frac{1}{2}(y-Mx)^T(y-Mx)\\
=\frac{1}{2}(y^Ty-y^TMx-x^TM^Ty+x^TM^TMx)=\\
=\frac{1}{2}(y^Ty-2y^TMx+x^TM^TMx)
$$
so
$$\frac{de}{dx}=\frac{1}{2}(-2y^TM+x^TM^TM)=0\\ x^TM^TM=2y^TM\\M^TMx=2M^Ty\\x=2(M^TM)^{-1}M^Ty$$
why can't I cancel the factor '2'?
 A: For a symmetric matrix $A$, the derivative of $x^\top A x$ with respect to $x$ is $2Ax$. You can prove this directly.
Using this fact you get $M^\top y = M^\top M x$ which yields the answer.
A: Hint: $x^TM^TMx=(Mx)^2$.  When you take the derivative with respect to $x$, you can't treat $x^T$ as a constant.
A: The form given assumes the full column rank linear system
$$
 \mathbf{A}x = b
$$
where 
$$
 \mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}, \quad b \in\mathbb{C}^{m}, \quad 
x\in\mathbb{C}^{n}
$$
There is an additional requirement that $b\notin\mathcal{N}\left(\mathbf{A}^{*}\right)$
The given solution comes from the normal equations
$$
  \mathbf{A}^{*} \mathbf{A}x = \mathbf{A}^{*} b
$$
The product matrix can be inverted because the matrix rank is the same as the number of columns. The solution is:
$$
 x = \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1} \mathbf{A}^{*}b
$$
Now the issue is to show that that
$$
  \mathbf{A}^{\dagger} = \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1} \mathbf{A}^{*}
$$
using the singular value decomposition:
$$
\begin{align}
  \mathbf{A} &=
  \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \\
%
 &=
% U 
  \left[ \begin{array}{cc}
     \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}}
  \end{array} \right]  
% Sigma
  \left[ \begin{array}{c}
     \mathbf{S} \\
     \mathbf{0}
  \end{array} \right]
% V 
  \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*}
\end{align}
$$
Show that
$$
\mathbf{A}^{*} \mathbf{A} = \color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S} \, \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*}
$$
which inverts easily
$$
 \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1}
= \color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S}^{-2} \, \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*}
$$
Finally
$$
\begin{align}
 \left( \mathbf{A}^{*} \mathbf{A} \right)^{-1}\mathbf{A}^{*} &=
\color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S}^{-2} \, \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \left( \color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S} \, \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*}\right)
=
\color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S}^{-2} \, \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \\
%
&= \mathbf{A}^{\dagger}
%
\end{align}
$$
