Moore-Penrose Inverse

Moore-Penrose Pseudoinverse

The Moore-Penrose Pseudoinverse is a generalisation of the standard matrix inverse, used to solve linear systems that either lack an exact solution or where the matrix is not square or invertible.

The Moore-Penrose pseudoinverse extends the concept of matrix inversion to a broader set of matrices, including those that are not square or are not invertible. Denoted as $(A^{+})$, provides solutions to linear systems in cases where traditional matrix inversion is not applicable whereby the conditions such as being a squared, the determinant being strictly positive does not hold.

The pseudoinverse satisfies four key properties:

1. $(A{A}^{+}A=A)$
2. $(A^{+}A{A}^{+}=A^{+})$
3. $((A{A}^{+}{)}^T=A{A}^{+})$
4. $((A^{+}A{)}^T=A^{+}A)$

These properties ensure that the pseudoinverse provides solutions to least-squares problems and minimises the error in systems that may not have exact solutions.

General Form of the Pseudoinverse

Given a matrix $A\in {\mathbb{R}}^{m\times n}$, the pseudoinverse $A^{+}$ can be defined in terms of the Singular Value Decomposition (SVD) of $A$. The SVD is written as:

$$A=U\mathrm{\Sigma }{V}^T$$

where:

1. $U$ is an $m\times m$ orthogonal matrix,
2. $\mathrm{\Sigma }$ is an $m\times n$ diagonal matrix containing the singular values of $A$,
3. $V$ is an $n\times n$ orthogonal matrix.

The pseudoinverse $A^{+}$ is then given by:

$$A^{+}=V{\mathrm{\Sigma }}^{+}{U}^T$$

where ${\mathrm{\Sigma }}^{+}$ is the pseudoinverse of the diagonal matrix $\mathrm{\Sigma }$. The singular values on the diagonal of $\mathrm{\Sigma }$ are inverted (for non-zero values), and the dimensions of the resulting matrix ${\mathrm{\Sigma }}^{+}$ are transposed to match the dimensions of $A^{+}$.

Non-Square Matrices

One of the primary applications of the pseudoinverse is in solving linear systems where the matrix is non-square. A non-square matrix ( A ^{m n} ) does not have a regular inverse, but the pseudoinverse ( A^+ ) can be used to compute a solution.

This is especially useful in overdetermined systems (more equations than unknowns) or underdetermined systems (more unknowns than equations), where the pseudoinverse provides a least-squares solution.

• Example: For an overdetermined system ( Ax = b ), the pseudoinverse helps find ( x ) such that the residual ( |Ax - b| ) is minimised.

Complexity

If the matrix ( A ) is of size ( m n ), the computation of the pseudoinverse using Singular Value Decomposition (SVD) has a time complexity of:

$$O(min(m{n}^2,m^{2}n))$$

This is because SVD is typically used to compute the pseudoinverse, which involves decomposing the matrix into three components.

Singular or Rank-Deficient Matrices

Another important use of the pseudoinverse is for singular or rank deficient matrices. A square matrix ( A ) is singular if its determinant is zero, making it non-invertible. The pseudoinverse provides an approximate solution by minimizing the error even when the matrix does not have full rank.

• Example: In a linear system $Ax=b$, if $A$ is singular, the pseudoinverse $A^{+}$ can still be used to find a solution that minimises the squared error.

Computational Complexity

For a singular matrix, the computation still relies on SVD, so the time complexity remains:

$$O(n^3)$$

where $n$ is the size of the matrix $A$. This is the typical complexity for SVD on a square matrix.

Solving Linear Systems with No Exact Solution

The pseudoinverse is frequently used in solving linear systems of the form $Ax=b$ when no exact solution exists.

• In linear regression, the pseudoinverse is used to compute the best-fitting line that minimises the error between the observed and predicted values.

The least-squares solution can be computed as:

$$x=A^{+}b$$

where $A^{+}$ is the pseudoinverse of matrix $A$.

Computational Complexity

Solving a least-squares problem using the pseudoinverse requires the SVD of $A$, leading to the following complexity:

$$O(n^3)$$

for square matrices, and for non-square matrices, the complexity is $O(min(m{n}^2,m^{2}n))$, where $m$ and $n$ are the dimensions of the matrix.