Pseudoinverse

$A\in {\mathbb{R}}^{m\times n}$ invertible then there is $A^{-1}$ and $\forall b\in {\mathbb{R}}^n$ one can solve $Ax=b$

$Ax\approx b⟹x=A^{†}b$

Case 1: $A\in {\mathbb{R}}^{m\times n}$ has full column rank $n$ Case 2: $A\in {\mathbb{R}}^{m\times n}$ has full row rank $m$ Case 3: general case

Proof

Case 1: full column rank

• $A^{\top }A$ is invertible
• $Ax=b$ for $b\in {\mathbb{R}}^m$ is not always solvable However, we can try to solve $Ax={\text{proj}}_{C(A)}(b)$ $⟺A^{\top }A\hat{x}=A^{\top }b$ $\hat{x}=(A^{\top }A{)}^{-1}{A}^{\top }b$

Definition: Pseudoinverse

Let $A\in {\mathbb{R}}^{m\times n}$ and $Rank(A)=n$, then $A^{†}=(A^{\top }A{)}^{-1}{A}^{\top }$ Properties $A^{†}A=I$ (Note that $A^{†}$ is here the left inverse) $A{A}^{†}=A(A^{\top }A{)}^{-1}{A}^{\top }=$ projection matrix of $C(A)$

$Ax=b$ might not be solvable, but $A^{†}b$ solves $A^{\top }Ax=A^{\top }b$

Case 2: full row rank

Idea: $A^{\top }$ has full column rank Let $B=A^{\top }$ We use the definition from case 1 and get $B^{†}=(B^{\top }B{)}^{-1}{B}^{\top }$

Definition: Pseudoinverse

Let $A\in {\mathbb{R}}^{m\times n}$ and $Rank(A^{\top })=m$, then $A^{†}=(B^{†}{)}^{\top }=((B^{\top }B{)}^{-1}{B}^{\top }{)}^{\top }=B(B^{\top }B{)}^{-1}=A^{\top }(A{A}^{\top }{)}^{-1}$

Properties $A{A}^{†}=I$ (Note that $A^{†}$ is only the left inverse) $A^{†}A=A^{\top }(A{A}^{\top }{)}^{-1}A$ projection matrix of $R(A)$ or $C(A^{\top })$

Since $A$ is full row rank, $\forall b\in {\mathbb{R}}^m$ there exists $x\in {\mathbb{R}}^n$ such that $Ax=b$, but there might be more than one such vectors. (a natural strategy is to choose the smallest $x$). Therefore, we choose $A^{†}$ such that $A^{†}b$ is the solution from $min\{\Vert x\Vert |Ax=b,x\in {\mathbb{R}}^n\}$

For $A\in {\mathbb{R}}^{m\times n}$, $b\in C(A)$ vector $\hat{x}\in C(A^{\top })$ with $A\hat{x}=b$ is the unique solution from $min\{\Vert x\Vert |Ax=b,x\in {\mathbb{R}}^n\}$ Proof: $\{x\in {\mathbb{R}}^n|Ax=b\}=\hat{x}+N(A)$ where $\hat{x}\in C(A^{\top }),A\hat{x}=b$ Then $\forall y\in N(A)$:

$$\Vert \hat{x}+y{\Vert }^2=\Vert {\hat{x}}^2\Vert +2{\hat{x}}^{\top }y+\Vert y{\Vert }^2>\Vert x{\Vert }^2$$

Therefore $\Vert \hat{x}{\Vert }^2$ is the smallest.

Note that $A^{†}$ is precisely the matrix that maps $b$ to $\hat{x}$, meaning $\hat{x}=A^{†}b$ Proof: we need to prove

• $A{A}^{†}b=b$
  • using $A{A}^{†}=I$, this is proved
• $A^{†}b\in C(A^{\top })$
  • $A^{†}b=A^{\top }(A{A}^{\top }{)}^{-1}b\in C(A^{\top })$, proved

Case 3: general case

$A\in {\mathbb{R}}^{m\times n}$, $Rank(A)=r$ Idea: $A=C\cdot R$ (CR decomposition) with $C\in {\mathbb{R}}^{m\times r},R\in {\mathbb{R}}^{r\times n}$ Observation:

• $C(A)=\{Ax|x\in {\mathbb{R}}^n\}=\{Cy|y\in {\mathbb{R}}^r\}$
• $N(A)=\{x\in {\mathbb{R}}^n|Ax=0\}=N(R)$

Definition: Pseudoinverse

For $A=C\cdot R$ $A^{†}=R^{†}\cdot C^{†}$ $A^{†}=R^{\top }(R{R}^{\top }{)}^{-1}(C^{\top }C{)}^{-1}{C}^{\top }=R^{\top }(C^{\top }CR{R}^{\top }{)}^{-1}{C}^{\top }=R^{\top }(C^{\top }A{R}^{\top }{)}^{-1}{C}^{\top }$

Lemma 6.4.8

Given $A\in {\mathbb{R}}^{m\times n}$ and $b\in {\mathbb{R}}^m$, the unique solution of $min\{\Vert x\Vert |x\in {\mathbb{R}}^n,A^{\top }Ax=A^{\top }b\}$ is given by $\hat{x}=A^{†}b$

Let $\hat{x}=A^{†}b$, show $A^{\top }A\hat{x}=A^{\top }b$: $A^{\top }A\hat{x}=A^{\top }A{R}^{\top }(C^{\top }A{R}^{\top }{)}^{-1}{C}^{\top }b=R^{\top }{C}^{\top }CR{R}^{\top }(C^{\top }A{R}^{\top }{)}^{-1}{C}^{\top }$ $=R^{\top }(C^{\top }A{R}^{\top })(C^{\top }A{R}^{\top }{)}^{-1}{C}^{\top }b=R^{\top }{C}^{\top }b=A^{\top }b$

Show that $\hat{x}\in C(A^{\top }A)$ $C(A^{\top }A)=C(A^{\top })=C(R^{\top })$ (see Lemma 5.1.10) $\hat{x}=A^{†}b=R^{\top }\underset{\text{vector}}{\underbrace{[(C^{\top }A{R}^{\top }{)}^{-1}{C}^{\top }b]}}$ $⟹x\in C(R^{\top })$

Conversely We can also find two matrices $S\in {\mathbb{R}}^{m\times r}$ (full column rank) $T\in {\mathbb{R}}^{r\times n}$ (full row rank) Then for $A=S\cdot T\in {\mathbb{R}}^{m\times n}$ $A^{†}=T^{†}{S}^{†}$

NOTE

$C(A)=C(S)$ $N(A)=N(T)$

Properties

$A{A}^{†}A=A$ $A^{†}A{A}^{†}=A^{†}$ $A{A}^{†}$ is symmetric and projection matrix of $C(A)$ $A^{\top }A$ is symmetric and projection matrix of $C(A^{\top })$ $(A^{\top }{)}^{†}=(A^{†}{)}^{\top }$