4
$\begingroup$

The normal form $ (A'A)x = A'b$ gives a solution to the least square problem. When $A$ has full rank $x = (A'A)^{-1}A'b$ is the least square solution.

How can we show that the moore-penrose solves the least square problem and hence is equal to $(A'A)^{-1}A'$.

Also what happens in a rank deficient matrix ? $(A'A)^{-1}$ would not exist so is the moore-penrose inverse still equal to $(A'A)^{-1}A'$ ?

Thanks

$\endgroup$
  • 1
    $\begingroup$ Do you know about the SVD? The whole situation is made clear by replacing $A$ and $A'$ by their SVDs. $\endgroup$ – Ian Nov 20 '15 at 2:22
  • $\begingroup$ @Ian How is moore penrose inverse equal to $(A'A)^{-1}A'$ for a full rank mxn matrix (m>n). Replacing by their svd leads me nowhere. Could you elaborate ? $\endgroup$ – midi Nov 20 '15 at 2:53
  • $\begingroup$ $A=U \Sigma V^*$. $A^*=V \Sigma^* U^*$. Therefore $A^* A = V \Sigma^* \Sigma V^*$. $V$ and $V^*$ are invertible by the orthogonality. If $A$ is $m \times n$ and has rank $n$, then $\Sigma^* \Sigma$ will be a diagonal matrix with all positive diagonal entries, hence also invertible. Let $S=\Sigma^* \Sigma$. Then $(A^* A)^{-1} A^* = V S^{-1} V^* V \Sigma U^* = V S^{-1} \Sigma U^*$. I presume that in this form it should be obvious that it is equal to the pseudoinverse, but maybe not if you have a different definition of the pseudoinverse than the one I have in mind. $\endgroup$ – Ian Nov 20 '15 at 3:15
  • $\begingroup$ @Ian the above is a proof of how SVD can be used for least square problem for a rank deficient matrix. I was looking at the limit definition of moore-penrose and wanted to see how that leads us to the Normal equation or is the Moore-penrose defined as such ? But then what happens for a rank deficient matrix ? $(A'A)^{-1}$ would not exist. $\endgroup$ – midi Nov 20 '15 at 3:25
  • $\begingroup$ If $A$ has rank less than $n$ then the pseudoinverse still exists: in the above, the matrix $S$ is no longer invertible, but you can replace $S^{-1}$ with the matrix in which you take the reciprocals of the positive entries of $S$. $\endgroup$ – Ian Nov 20 '15 at 3:27
13
$\begingroup$

The generalized Moore-Penrose pseudoinverse can be classified by looking at the shape of the target matrix, or by the existence of the null spaces. The two perspectives are merged below and connected to left- and right- inverses as well as the classic inverse.

Singular value decomposition

Start with the matrix $\mathbf{A} \in \mathbb{C}^{m\times n}_{\rho}$ and its 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}{cccc|cc} \sigma_{1} & 0 & \dots & & & \dots & 0 \\ 0 & \sigma_{2} \\ \vdots && \ddots \\ & & & \sigma_{\rho} \\ \hline & & & & 0 & \\ \vdots &&&&&\ddots \\ 0 & & & & & & 0 \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] \\ % & = % U \left[ \begin{array}{cccccccc} \color{blue}{u_{1}} & \dots & \color{blue}{u_{\rho}} & \color{red}{u_{\rho+1}} & \dots & \color{red}{u_{n}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}_{\rho\times \rho} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{v_{1}^{*}} \\ \vdots \\ \color{blue}{v_{\rho}^{*}} \\ \color{red}{v_{\rho+1}^{*}} \\ \vdots \\ \color{red}{v_{n}^{*}} \end{array} \right] % \end{align} $$ Coloring distinguishes $\color{blue}{range}$ spaces from $\color{red}{null}$ spaces. The beauty of the SVD is that it provides an orthonormal resolution for the four fundamental subspaces of the domain $\mathbb{C}^{n}$ and codomain $\mathbb{C}^{m}$: $$ \begin{align} % domain \mathbb{C}^{n} &= \color{blue}{\mathcal{R}(\mathbf{A}^{*})} \oplus \color{red}{\mathcal{N}(\mathbf{A})} \\ % % codomain \mathbb{C}^{m} &= \color{blue}{\mathcal{R}(\mathbf{A})} \oplus \color{red}{\mathcal{N}(\mathbf{A}^{*})} \end{align} $$

Moore-Penrose pseudoinverse

In block form, the target matrix and the Moore-Penrose pseudoinverse are $$ \begin{align} \mathbf{A} &= \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}(\mathbf{A})}} & \color{red}{\mathbf{U}_{\mathcal{N}(\mathbf{A}^{*})}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{l} \color{blue}{\mathbf{V}_{\mathcal{R}(\mathbf{A}^{*})}^{*}} \\ \color{red}{\mathbf{V}_{\mathcal{N}(\mathbf{A})}^{*}} \end{array} \right] \\ %% \mathbf{A}^{\dagger} &= \mathbf{V} \, \Sigma^{\dagger} \, \mathbf{U}^{*} = % U \left[ \begin{array}{cc} \color{blue}{\mathbf{V}_{\mathcal{R}(\mathbf{A}^{*})}} & \color{red}{\mathbf{V}_{\mathcal{N}(\mathbf{A})}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{l} \color{blue}{\mathbf{U}_{\mathcal{R}(\mathbf{A})}^{*}} \\ \color{red}{\mathbf{U}_{\mathcal{N}(\mathbf{A}^{*})}^{*}} \end{array} \right] \end{align} $$ We can sort the least squares solutions into special cases according to the null space structures.

Both nullspaces are trivial: full row rank, full column rank

$$ \begin{align} \color{red}{\mathcal{N}(\mathbf{A})} &= \mathbf{0}, \\ \color{red}{\mathcal{N}\left( \mathbf{A}^{*} \right)} &= \mathbf{0}. \end{align} $$ The $\Sigma$ matrix is nonsingular: $$ \Sigma = \mathbf{S} $$ The classic inverse exists and is the same as the pseudoinverse: $$ \mathbf{A}^{-1} = \mathbf{A}^{\dagger} = \color{blue}{\mathbf{V_{\mathcal{R}}}} \, \mathbf{S}^{-1} \, \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} $$ Given the linear system $\mathbf{A}x = b$ with $b\notin\color{red}{\mathcal{N}(\mathbf{A})}$, the least squares solution is the point $$ x_{LS} = \color{blue}{\mathbf{A}^{-1}b}. $$

Only $\color{red}{\mathcal{N}_{\mathbf{A}^{*}}}$ is trivial: full column rank, row rank deficit

This is the overdetermined case, also known as the full column rank case: $m>n$, $\rho=n$. $$ \Sigma = \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \end{array} \right] $$ The pseudoinverse provides the same solution as the normal equations: $$ \begin{align} % \mathbf{A} & = % \left[ \begin{array}{cc} \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} & \color{red}{\mathbf{U_{\mathcal{N}}}} \end{array} \right] % \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \end{array} \right] % \color{blue}{\mathbf{V_{\mathcal{R}}}} \\ % Apinv \mathbf{A}^{\dagger} & = % \color{blue}{\mathbf{V_{\mathcal{R}}}} \, \left[ \begin{array}{cc} \mathbf{S}^{-1} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} \\ \color{red}{\mathbf{U_{\mathcal{N}}^{*}}} \end{array} \right] \end{align} $$ The inverse from the normal equations is $$ \begin{align} \left( \mathbf{A}^{*}\mathbf{A} \right)^{-1} \mathbf{A}^{*} &= % \left( % \color{blue}{\mathbf{V_{\mathcal{R}}}} \, \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} \\ \color{red}{\mathbf{U_{\mathcal{N}}^{*}}} \end{array} \right] % A \left[ \begin{array}{cx} \color{blue}{\mathbf{U_{\mathcal{R}}}} & \color{red}{\mathbf{U_{\mathcal{N}}}} \end{array} \right] \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \end{array} \right] \color{blue}{\mathbf{V_{\mathcal{R}}^{*}}} \, % \right)^{-1} % A* % \left( \color{blue}{\mathbf{V_{\mathcal{R}}}} \, \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} \\ \color{red}{\mathbf{U_{\mathcal{N}}^{*}}} \end{array} \right] \right) \\ \\ % &= % \color{blue}{\mathbf{V_{\mathcal{R}}}} \, \left[ \begin{array}{cc} \mathbf{S}^{-1} \, \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} \\ \color{red}{\mathbf{U_{\mathcal{N}}^{*}}} \end{array} \right] \\ % &= \mathbf{A}^{\dagger} % \end{align} $$ The figure below shows the solution as the projection of the data vector onto the range space $\color{blue}{\mathcal{R}(\mathbf{A})}$.

overdetermined

Only $\color{red}{\mathcal{N}_{\mathbf{A}}}$ is trivial: full row rank, column rank deficit

This is an underdetermined case, also known as the full row rank case: $m<n$, $\rho=m$. We lose uniqueness and the solution will be an affine space. $$ \Sigma = \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \end{array} \right] $$ The target matrix and pseudoinverse are: $$ \begin{align} % \mathbf{A} & = % \color{blue}{\mathbf{U_{\mathcal{R}}}} \, \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V_{\mathcal{R}}^{*}}} \\ \color{red} {\mathbf{V_{\mathcal{N}}^{*}}} \end{array} \right] % \\ % Apinv \mathbf{A}^{\dagger} & = % \left[ \begin{array}{cc} \color{blue}{\mathbf{V_{\mathcal{R}}}} & \color{red} {\mathbf{V_{\mathcal{N}}}} \end{array} \right] \left[ \begin{array}{c} \mathbf{S}^{-1} \\ \mathbf{0} \end{array} \right] % \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} % \end{align} $$ The inverse matrix is $$ \begin{align} \mathbf{A}^{*} \left( \mathbf{A} \, \mathbf{A}^{*} \right)^{-1} % &= % \left[ \begin{array}{cc} \color{blue}{\mathbf{V_{\mathcal{R}}}} & \color{red} {\mathbf{V_{\mathcal{N}}}} \end{array} \right] \left[ \begin{array}{c} \mathbf{S}^{-1} \\ \mathbf{0} \end{array} \right] % \color{blue}{\mathbf{U_{\mathcal{R}}^{*}}} \\ % &= \mathbf{A}^{\dagger} % \end{align} $$

The least squares solution is the affine space $$ \begin{align} x_{LS} = \color{blue}{\mathbf{A}^{\dagger} b} + \color{red}{ \left( \mathbf{I}_{n} - \mathbf{A}^{\dagger} \mathbf{A} \right) y}, \qquad y \in \mathbb{C}^{n} \\ \end{align} $$ represented by the dashed red line below.

No uniqueness

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

The matrix $A$ typically has many more rows than columns --- lets imagine $200$ rows and $3$ columns. The $200\times1$ vector $b$ is typically not in the column space of $A$, so the equation $Ax\overset{\Large\text{?}}=b$ has no solution for the $3\times1$ vector $x$. The problem is to find the value of $x$ that makes $Ax$ as close as possible to $b$, in that $\|Ax-b\|$ is as small as possible. The solution is the orthogonal projection of $b$ onto the column space of $A$. The entries in $x$ are the coefficients in a linear combination of the columns of $A$.

Vectors in the column space of $A$ are precisely vectors of the form $Ax$.

If the matrix $A$ has full rank (in our example, rank $3$), i.e. it has linearly independent columns, then the $3\times3$ matrix $A'A$ is invertible; otherwise it is not.

Consider the $200\times200$ matrix $Hu = A(A'A)^{-1}A'$, which has rank $3$. If a $200\times1$ vector $u$ is in the column space of $A$, then $Hu=u$. This is proved as follows: $$ Hu = A(A'A)^{-1} A'\Big( Ax\Big) = A(A'A)^{-1}\Big(A'A\Big) x = Ax = u. $$ If $u$ is orthogonal to the column space of $A$, then $Au=0$, as follows: $$ Hu = A(A'A)^{-1} (A'u),\qquad\text{and }A'u=0. $$ Thus $u\mapsto Hu$ is the orthogonal projection onto the column space of $A$.

So the least-squares solution satisfies $Hb = Ax$.

Thus $A(A'A)^{-1}A'b = Ax$.

If $A$ has a left-inverse, by which we can multiply both sides of this equation on the left, then we can get $(A'A)^{-1} A'b = x$, and that's the least-squares solution.

That left-inverse is $(A'A)^{-1}A'$, as can readily be checked.

If the columns of $A$ are not linearly independent, then each point in the column space can be written as $Ax_1 = Ax_2$ for some $x_1\ne x_2$. In that case, the least-squares solution is not unique.

| 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.