Moore-Penrose pseudoinverse/Proofs

= Existence and Uniqueness =Let $A$ be an "m"-by-"n" matrix over "K", where "K" is either the field of real numbers or the field of complex numbers. Then there is a unique "n"-by-"m" matrix $A^+$ over "K" such that:
#$A\; A^+A\; =\; A$
#$A^+A\; A^+\; =\; A^+$
#$(AA^+)^*\; =\; AA^+$
#$(A^+A)^*\; =\; A^+A$$A^+$ is called the pseudoinverse of $A$.

Proof of existence

The proof proceeds in stages.

1-by-1 matrices

For any $x\; in\; K$, we define

It is easy to see that $x^+$ is a pseudoinverse of $x$ (interpreted as a 1-by-1 matrix).

quare diagonal matrices

Let D be an "n"-by-"n" matrix over "K" with zeros off the diagonal.We define $D^+$ as an "n"-by-"n" matrix over "K" with $(D^+)\_\{ij\}\; :=\; (D\_\{ij\})^+$. We write simply $D^+\_\{ij\}$ for $(D^+)\_\{ij\}\; =\; (D\_\{ij\})^+$.

Notice that $D^+$ is also a matrix with zeros off the diagonal.

We then proceed to show that $D^+$ is a pseudoinverse of $D$:
#$(DD^+D)\_\{ij\}=D\_\{ij\}D^+\_\{ij\}D\_\{ij\}=D\_\{ij\}\; Rightarrow\; DD^+D\; =\; D$
#$(D^+DD^+)\_\{ij\}=D^+\_\{ij\}D\_\{ij\}D^+\_\{ij\}=D^+\_\{ij\}\; Rightarrow\; D^+DD^+\; =\; D^+$
#$(DD^+)^*\_\{ij\}\; =\; overline\{(DD^+)\_\{ji\; =\; overline\{D\_\{ji\}D^+\_\{ji\; =\; (D\_\{ji\}D^+\_\{ji\})^*\; =\; D\_\{ji\}D^+\_\{ji\}\; =\; D\_\{ij\}D^+\_\{ij\}\; Rightarrow\; (DD^+)^*\; =\; DD^+$
#$(D^+D)^*\_\{ij\}\; =\; overline\{(D^+D)\_\{ji\; =\; overline\{D^+\_\{ji\}D\_\{ji\; =\; (D^+\_\{ji\}D\_\{ji\})^*\; =\; D^+\_\{ji\}D\_\{ji\}\; =\; D^+\_\{ij\}D\_\{ij\}\; Rightarrow\; (D^+D)^*\; =\; D^+D$

Arbitrary matrices

The singular value decomposition theorem states that there exists a factorization of the form:$A\; =\; USigma\; V^*$where::"U" is an "m"-by-"m" unitary matrix over "K".:Σ is an "m"-by-"n" matrix over "K" with nonnegative numbers on the diagonal and zeros off the diagonal.:"V" is an "n"-by-"n" unitary matrix over "K". [Some authors use slightly different dimensions for the factors. The two definitions are equivalent.]

We define $A^+$ as $VSigma^+U^*$.

We then proceed to show that $A^+$ is a pseudoinverse of $A$:

#$AA^+A\; =\; USigma\; V^*VSigma^+U^*USigma\; V^*\; =\; USigmaSigma^+Sigma\; V^*\; =\; USigma\; V^*\; =\; A$
#$A^+AA^+\; =\; VSigma^+U^*USigma\; V^*VSigma^+U^*\; =\; VSigma^+SigmaSigma^+U^*\; =\; VSigma^+U^*\; =\; A^+$
#$(AA^+)^*\; =\; (USigma\; V^*VSigma^+U^*)^*\; =\; (USigmaSigma^+U^*)^*\; =\; U(SigmaSigma^+)^*U^*\; =\; U(SigmaSigma^+)U^*\; =\; USigma\; V^*VSigma^+U^*\; =\; AA^+$
#$(A^+A)^*\; =\; (VSigma^+U^*USigma\; V^*)^*\; =\; (VSigma^+Sigma\; V^*)^*\; =\; V(Sigma^+Sigma)^*V^*\; =\; V(Sigma^+Sigma)V^*\; =\; VSigma^+U^*USigma\; V^*\; =\; A^+A$

Proof of uniqueness

Suppose that "B" and "C" are two "n"-by-"m" matrices over "K" satisfying the pseudoinverse properties.

*$AB=(AB)^T$, $AC=(AC)^T$
*$BA=(BA)^T$, $CA=(CA)^T$
*$ABA=A$, $ACA=A$
*$BAB=B$, $CAC=C$

We will show that $B=C$.

As a first step we show $AB=AC$::$AB\; =\; B^T\; A^T\; =\; B^T\; A^T\; C^T\; A^T\; =\; A\; B\; C^T\; A^T\; =\; ABAC\; =\; AC$Analogously we conclude that $BA=CA$.

We complete the proof with::$B\; =\; BAB\; =\; BAC\; =\; CAC\; =\; C$

= Relations =

Preliminaries

These lemmata do not concern the pseudoinverse itself, they are about complex matrices in general.

As always, they also hold for matrices with only real elements, in which case the conjugation operator (*) may be replaced by transposition (^T).

= L3: A*A = 0 ⇒ A = 0 . =

A is a matrix with complex elements, m rows and n columns. The assumption says that all elements of A*A are zero, including the diagonal elements. The j^th diagonal element of A*A is $sum\_\{i=1...m\}\; (a^*)\_\{ji\}a\_\{ij\}=sum\_\{i=1...m\}overline\{a\_\{ija\_\{ij\}$. Since $x\; overline\{x\}\; ge\; 0$ for all x, and equal to zero only for x = 0, the sum can only be 0 if all $a\_\{ij\}$ are 0. Since this holds for all j, all $a\_\{ij\}$ are 0, thus A=0.

= L4: BAA* = CAA* => BA = CA. =

A is a matrix with complex elements and m rows. B and C are matrices with complex elements and m columns.

BAA* = CAA* <=> 0 = BAA*-CAA* = (BA-CA)A* => 0 = (BA-CA)A*(B-C)* = (BA-CA)(BA-CA)* L3=> 0 = BA-CA <=> BA = CA.

Note that since BA = CA => BAA* = CAA* also holds, in effect equivalence results: BA = CA &hArr; BAA* = CAA*.

= L5: A*AB = A*AC => AB = AC. =

A is a matrix with complex elements and n columns. B and C are matrices with complex elements and n rows.

A*AB = A*AC <=> 0 = A*AB-A*AC = A*(AB-AC) => 0 = (B-C)*A*(AB-AC) = (AB-AC)*(AB-AC) L3=> 0 = AB-AC <=> AB = AC.

Note that since AB = AC => A*AB = A*AC also holds, in effect equivalence results: AB = AC &hArr; A*AB = A*AC.

= L1: A*⁺=A^+*. =

The proof works by showing that A^+* satisfies the four criteria for the Pseudoinverse of A*. Since this amounts to just substitution, it is not shown here.

This relation is given to prove as Exercise 18b in cite book | last=Ben-Israel | first = Adi | coauthors=Thomas N.E. Greville | title=Generalized Inverses | isbn=0-387-00293-6 | publisher=Springer-Verlag | year=2003] .

Identity Transformations

= A⁺ = A⁺ A^+* A* =

A⁺ = A⁺AA⁺ and AA⁺ = (AA⁺)* imply that A⁺ = A⁺(A A⁺)* = A⁺A^+*A*.

= A⁺ = A* A^+* A⁺ =

A⁺ = A⁺AA⁺ and A⁺A = (A⁺A)* imply that A⁺ = (A⁺A)*A⁺ = A*A^+*A⁺.

= A = A^+* A* A =

A = A A+ A and A A+ = (A A+)* imply that A = (A A+)* A = A+* A* A.

= A = A A* A^+* =

A = A A+ A and A+ A = (A+ A)* imply that A = A (A+ A)* = A A* A+*.

= A* = A* A A⁺ =

This is the conjugate transpose of A = A+* A* A above.

= A* = A⁺ A A* =

This is the conjugate transpose of A = A A* A+* above.

= A⁺ = (A* A)⁺ A*. =

In the B-I&G] , this relation, together with A+=A*(AA*)+ is given as exercise 18(d) for the reader to prove, "for every matrix A".It might also be found in cite book| last=Kohonen| first=Teuvo| title=Self-Organization and Associative Memory| isbn=0-387-18314-0| publisher=Springer-Verlag | year=1988] , possibly chapters 5 or 7, but this was not verified.The relation is proven here by showing that the right-hand side satisfies the defining criteria of the pseudoinverse of A.

Further lemmata: For any A, (A*A)+ exists and is unique, so that criteria 1 to 4 hold for it: B1: A*A (A*A)+ A*A = A*A; B2: (A*A)+ A*A (A*A)+ = (A*A)+; B3: ( A*A (A*A)+)* = A*A (A*A)+; <=> (A*A)+* A*A = A*A (A*A)+ L1=>= (A*A)+ A*A (not used here) B4: ((A*A)+ A*A )* = (A*A)+ A*A; <=> A*A (A*A)+* = (A*A)+ A*A L1=>= A*A (A*A)+Above, "L1=>=" means "from L1 follows equality with".B2 is used in the proof of 2 below, B4 is used in the proof of 4.

L6: A (A* A)+ A* A = A. L6 follows from applying L5 to B1. Note that L2 may not be applied to B1, since the X in L2 may in this case not be chosen independently of Y and Z, it is fixed (the A* in B1) .

Below, '*=>=' means 'applying complex conjugation'. 0. A+ = (A* A)+ A* . (That's what we suppose) 1. AA+A = A ; AA+A 0=>= A(A*A)+ A*A L6=>= A =<=0 A -> OK. 2. A+AA+ = A+ ; A+AA+ 0=>= (A*A)+ A* A (A*A)+ A* B2=>= (A*A)+A* =<=0 A+ -> OK. 3. (AA+)* = AA+; (AA+)* 0=>= (A(A*A)+ A*)* *=>= A(A*A)+* A* L1,*=>= A(A*A)+ A* =<=0 AA+ -> OK. 4. (A+A)* = A+A; (A+A)* 0=>= ((A*A)+ A*A)* *=>= A*A(A*A)+* B4=>= (A*A)+ A*A =<=0 A+A -> OK.

= A⁺ = A* (A A*)⁺ =

This proof works along a similar line as the above one. The relation is proven by showing that the right-hand side satisfies the defining criteria of the pseudoinverse of A: A1: AA⁺A = A . A2: A⁺AA⁺ = A⁺ . A3: (AA⁺)* = AA⁺. A4: (A⁺A)* = A⁺A.

First, some basic relations are named: M1: B=C => DB=DC. T0: (A*)* = A. T1: (AB)* = B*A*.

Further lemmata: For any A, (AA*)⁺ exists and is unique, so that criteria 1 to 4 hold for it: C1: AA* (AA*)⁺ AA* = AA* . C2: (AA*)⁺ AA* (AA*)⁺ = (AA*)⁺ . C3: ( AA* (AA*)⁺)* = AA* (AA*)⁺. (unused here) C4: ((AA*)⁺ AA* )* = (AA*)⁺ AA* .

More auxiliary results: I3: C4 and T1 (twice) and T0 => AA* (AA*)⁺* = (AA*)⁺ AA*. I4: I3 and L1 and T1 and T0 => AA* (AA*)⁺ = (AA*)⁺ AA*.

Applying A+ = A* (A A*)⁺ to A1 to A4, we have to prove these four relations: G1: AA* (AA*)⁺ A = A, G2: A* (AA*)⁺ AA* (AA*)⁺ = A* (AA*)⁺, G3: (AA* (AA*)⁺)* = AA* (AA*)⁺, G4: (A* (AA*)⁺ A)* = A* (AA*)+ A.

C1 and L4 (BAA* = CAA* => BA = CA) imply G1.

C2 and M1 imply G2.

I5: Equality holds: A* (AA*)⁺ A = A* (AA*)⁺ A I6: I5 and T0 and T1 => A* (AA*)*⁺ A = A* (AA*)⁺ A I7: I6 and L1 => A* (AA*)⁺* A = A* (AA*)⁺ A I8: I7 and T1 =>(A* (AA*)⁺ A)* = A* (AA*)⁺ A, proving G4.

I9: Equality holds: (AA* (AA*)⁺)* = (AA* (AA*)⁺)* I10: I9 and T1 (twice) and T0 => (AA* (AA*)⁺)* = (AA*)⁺* AA* I11: I10 and L1 and T1 and T0 => (AA* (AA*)⁺)* = (AA*)⁺ AA* I12: I11 and I4 => (AA* (AA*)⁺)* = AA* (AA*)⁺, proving G3.

Thus the hypothesis satisfies A1 to A4.

= References =