Solving Systems of Linear Equations (3)

The Pseudoinverse of a Matrix

The pseudoinverse introduced here is the Moore-Penrose inverse, defined as follows: given a matrix $A\in R^{m*n}$, if a matrix $A^{\dagger}\in R^{n*m}$ satisfies $AA^{\dagger}A=A$ and there exist two matrices $U\in R^{n*n},V\in R^{m*m}$ such that

then $A^{\dagger}$ is called the pseudoinverse of the matrix $A$. It can be proven that the pseudoinverse of a matrix is unique.

For a matrix $A\in R^{m*n},m\ge n$ with $rank(A)=n$, one can verify from the above definition that the pseudoinverse of $A$ is

For a matrix $A\in R^{m*n},m\le n$ with $rank(A)=m$, one can likewise verify from the above definition that the pseudoinverse of $A$ is

The two cases above give the pseudoinverse when the matrix has full column rank or full row rank. For a general matrix $A\in R^{m*n},rank(A)=r,r\le min(m,n)$, we can use the method of full-rank factorization to obtain its pseudoinverse.

Any matrix $A\in R^{m*n},rank(A)=r,r\le min(m,n)$ can be factored into the product of a full-row-rank matrix and a full-column-rank matrix: that is, $A=BC,B\in R^{m*r},c\in R^{r*n},rank(A)=rank(B)=rank(C)=r$

It can be proven that: $A^{\dagger}=C^{\dagger}B^{\dagger}$, where $B^{\dagger}=(B^{T}B)^{-1}B^{T},C^{\dagger}=C^{T}(CC^{T})^{-1}$, which is how the pseudoinverse of a general matrix is computed.

Solving Systems of Linear Equations in the General Case

Consider a system of linear equations $Ax=b,A\in R^{m*n},rank(A)=r$. The vector $x^{*}=A^{\dagger}b$ minimizes $||Ax-b||^{2}$ over the space $R^{n}$; moreover, among all vectors in $R^{n}$ that minimize $||Ax-b||^{2}$, the vector $x^{*}=A^{\dagger}b$ has the smallest norm and is unique.

When $r=m$, $A$ has full row rank, and in this case $x^{*}=A^{\dagger}b=A^{T}(AA^{T})^{-1}b$ is the minimum-norm solution of the system $Ax=b$.

When $r=n$, $A$ has full column rank, and in this case $x^{*}=A^{\dagger}b=(A^{T}A)^{-1}A^{T}b$ is the least-squares solution of the system $Ax=b$.