Generalized Inverses

Generalized Inverses

For $A \in M_{m,n}$, $B \in M_{n,m}$ consider the conditions

1. $ABA = A$,
2. $AB$ is Hermitian,
3. $BAB = B$,
4. $BA$ is Hermitian.

$B$ is a $\{1\}$-generalized inverse if it satisfies 1, a $\{1,2\}$-generalized inverse if it satisfies 1 and 2, and so on. (Penrose's original numbering swaps conditions 2 and 3.)

Solving Linear Systems

Let $A \in M_{m,n}$, $b \in \mathbb{C}^m$ and $Ax = b$ consistent. If $B$ is a $\{1\}$-generalized inverse of $A$, then $x = Bb$ solves it.

Proof Let $z \in \mathbb{C}^n$ with $Az = b$. Then $A(Bb) = ABAz = Az = b$.

Least Squares

If $B$ is a $\{1,2\}$-generalized inverse of $A$, the minimizers of $\|Ax - b\|_2$ are exactly $Bb + \mathrm{null}(A)$.

Proof For any $y$,

$$\|A(Bb + y) - b\|_2^2 = \big[(AB - I)b + Ay\big]^* \big[(AB - I)b + Ay\big] = \|(AB - I)b\|_2^2 + \|Ay\|_2^2 + 2\,\mathrm{Re}\big(y^*A^*(AB - I)b\big)$$

The cross term vanishes, since $AB$ Hermitian gives

$$\big[y^*A^*(AB - I)b\big]^* = b^*(AB - I)Ay = b^*(ABAy - Ay) = 0$$

So the value is $\|(AB - I)b\|_2^2 + \|Ay\|_2^2$, minimized exactly when $Ay = 0$.

Moore-Penrose Inverse

$A^\dagger$ is the unique $\{1,2,3,4\}$-generalized inverse.

Uniqueness Let $B, C$ both be $\{1,2,3,4\}$-inverses of $A$. Then

$$AB = ACAB = C^*A^*B^*A^* = C^*(ABA)^* = C^*A^* = AC$$ $$BA = BACA = A^*B^*A^*C^* = (ABA)^*C^* = A^*C^* = CA$$

so $B = BAB = CAB = CAC = C$.

Existence

1. For a "diagonal" $\Sigma \in M_{m,n}$ let $\Sigma^\dagger \in M_{n,m}$ have $\Sigma^\dagger_{ii} = 1/\Sigma_{ii}$ where $\Sigma_{ii} \neq 0$ and 0 elsewhere. Then $\Sigma^\dagger$ is the Moore-Penrose inverse of $\Sigma$.
2. If $Z \in M_{n,m}$ is the Moore-Penrose inverse of $Y \in M_{m,n}$ and $U \in M_m$, $V \in M_n$ are unitary, then $UYV^*$ has Moore-Penrose inverse $VZU^*$.
3. Invoke the SVD, $A = U\Sigma V^* \Rightarrow A^\dagger = V\Sigma^\dagger U^*$.

So with $\mathrm{rank}(A) = k$,

$$A^\dagger = V\Sigma^\dagger U^* = \sum_{i=1}^{k} \frac{1}{\sigma_i} v_i u_i^*$$

Minimum Norm Least Squares

Among the solutions to $\min_{x \in \mathbb{C}^n} \|Ax - b\|_2$, $x^* = A^\dagger b$ is the unique one of minimum Euclidean norm.

Proof

1. $A^\dagger$ is a $\{1,2\}$-inverse, so the solutions are $A^\dagger b + \mathrm{null}(A)$. Let $A = U\Sigma V^*$ with $\mathrm{rank}(A) = k$.
2. $\mathrm{null}(A) = \mathrm{span}\{v_{k+1}, \ldots, v_n\}$ and $\mathrm{range}(A^\dagger) = \mathrm{span}\{v_1, \ldots, v_k\}$ since $A^\dagger = V\Sigma^\dagger U^*$.
3. So $y \perp A^\dagger b$ for all $y \in \mathrm{null}(A)$.
4. Now $\|A^\dagger b + y\|_2^2 = \|A^\dagger b\|_2^2 + \|y\|_2^2$, minimized only at $y = 0$.

Full Rank

If $A \in M_{m,n}$ has full column rank, $A^\dagger = (A^*A)^{-1}A^*$. If it has full row rank, $A^\dagger = A^*(AA^*)^{-1}$.