3
$\begingroup$

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'?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But does it hold also in the case of non-symmetric matrix? $\endgroup$ – sunrise Mar 31 '17 at 5:49
  • 2
    $\begingroup$ @sunrise $M^\top M$ is always symmetric $\endgroup$ – angryavian Mar 31 '17 at 17:30
0
$\begingroup$

Hint: $x^TM^TMx=(Mx)^2$. When you take the derivative with respect to $x$, you can't treat $x^T$ as a constant.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ .. :) If I write: $Mx \cdot Mx$, using the chain rule, I obtain $M\cdot Mx+Mx\cdot M$... but then... ? $\endgroup$ – sunrise Mar 30 '17 at 20:33
  • $\begingroup$ Not quite, since $Mx . M$ is not defined. $\endgroup$ – Paul Mar 30 '17 at 20:36
  • $\begingroup$ I'm sorry... I really don't know how to go on... thanks for your precious help! $\endgroup$ – sunrise Mar 31 '17 at 5:51
0
$\begingroup$

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} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.