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
The pseudoinverse satisfies four key properties:
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
where:
is an orthogonal matrix, is an diagonal matrix containing the singular values of , is an orthogonal matrix.
The pseudoinverse
where
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:
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
, if is singular, the pseudoinverse 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:
where
Solving Linear Systems with No Exact Solution
The pseudoinverse is frequently used in solving linear systems of the form
- 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:
where
Computational Complexity
Solving a least-squares problem using the pseudoinverse requires the SVD of
for square matrices, and for non-square matrices, the complexity is