Moore-Penrose Inverse

math
linear algebra
Author

Passawis

Published

June 22, 2022

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. (AA+A=A)
  2. (A+AA+=A+)
  3. ((AA+)T=AA+)
  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 ARm×n, the pseudoinverse A+ can be defined in terms of the Singular Value Decomposition (SVD) of A. The SVD is written as:

A=UΣVT

where:

  1. U is an m×m orthogonal matrix,
  2. Σ is an m×n diagonal matrix containing the singular values of A,
  3. V is an n×n orthogonal matrix.

The pseudoinverse A+ is then given by:

A+=VΣ+UT

where Σ+ is the pseudoinverse of the diagonal matrix Σ. The singular values on the diagonal of Σ are inverted (for non-zero values), and the dimensions of the resulting matrix Σ+ 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(mn2,m2n))

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(n3)

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(n3)

for square matrices, and for non-square matrices, the complexity is O(min(mn2,m2n)), where m and n are the dimensions of the matrix.