Pseudoinverse


In mathematics, and in particular linear algebra, the pseudoinverse of an matrix is a generalization of the inverse matrix.[1] More precisely, this article talks about the Moore-Penrose pseudoinverse, which was independently described by E. H. Moore[2] in 1920 and Roger Penrose[3] in 1955. Earlier, Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. The term generalized inverse is sometimes used as a synonym for pseudoinverse.

A common use of the pseudoinverse is to compute a 'best fit' (least squares) solution to a system of linear equations (see below under Applications). The pseudoinverse is defined and unique for all matrices whose entries are real or complex numbers. The pseudoinverse can be computed using the singular value decomposition.

Definition

The pseudoinverse of a matrix is the unique matrix satisfying the following criteria:

  1. ;
  2.       ( is a weak inverse for the multiplicative semigroup);
  3.       ( is Hermitian); and
  4.       ( is also Hermitian).

Here is the conjugate transpose of a matrix M. For matrices whose elements are real numbers instead of complex numbers, .

An alternative way to define the pseudoinverse is via a limiting process: (see Tikhonov regularization). These limits exist even if and do not exist.

Properties

Special cases

If the columns of are linearly independent, then is invertible. In this case, an explicit formula is:[1] . In the first limit in the "Definition" section above, the limiting expression is continuous at ; that is, we can simply substitute in the limiting expression. It follows that is a left inverse of A:   .

If the rows of are linearly independent, then is invertible. In this case, an explicit formula is: . In the second limit in the "Definition" section above, the limiting expression is continuous at . It follows that is a right inverse of A:   .

If both columns and rows are linearly independent (that is, for square nonsingular matrices), the pseudoinverse is just the inverse: .

If A and B are such that the product is defined and either A or B is unitary, then . If A and B are such that the product is defined, A is of full column rank, and B is of full row rank, then . The second case here does not cover the first; a unitary matrix must be of full rank, but otherwise there is no assumption made on the matrix it multiplies.

It is also possible to define a pseudoinverse for scalars and vectors. This amounts to treating these as matrices. The pseudoinverse of a scalar is zero if is zero and the reciprocal of otherwise:

The pseudoinverse of the null vector is the transposed null vector. The pseudoinverse of other vectors is the conjugate transposed vector divided by its squared magnitude:

For a proof, simply check that these definitions meet the defining criteria for the pseudoinverse.

Finding the pseudoinverse of a matrix

Let k be the rank of a matrix A. Then A can be decomposed as , where B is a -matrix and C is a matrix. Then .

If A has full row rank, so that k = m, then B can be chosen to be the identity matrix and the formula reduces to . Similarly, if A has full column rank (that is, k = n), we have

A computationally simpler way to get the pseudoinverse is using the singular value decomposition.[1][4][5]

If is the singular value decomposition of A, then . For a diagonal matrix such as , we get the pseudoinverse by taking the reciprocal of each non-zero element on the diagonal.

Optimized approaches exist for calculating the pseudoinverse of block structured matrices.

If a pseudoinverse is already known for a given matrix, and the pseudoinverse is desired for a related matrix, the pseudoinverse for the related matrix can be computed using specialized algorithms that may need less work. In particular, if the related matrix differs from the original one by only a changed, added or deleted row or column, incremental algorithms exist that exploit the relationship.

Applications

The pseudoinverse provides a least squares solution to a system of linear equations.[6]

Given an overdetermined system

we look for a vector that minimizes

where denotes the Euclidean norm.

The general solution to an inhomogeneous system is the sum of a particular solution of the inhomogeneous system and the general solution of the corresponding homogeneous system .

Lemma: If exists, then the solution can always be written as the sum of the pseudoinverse solution of the inhomogeneous system and a solution of the homogeneous system:

Proof:

Here, the vector is arbitrary (apart from the dimensionality). In both summands, the pseudoinverse appears. If we write it as , the equation looks like this:

The first summand is the pseudoinverse solution. In the sense of the least squares error, it is the best linear approximation to the actual solution. This means that the correction summand has minimal euclidean norm. The second summand represents a solution of the homogeneous system , because is the projection on the kernel (null space) of A, while is the projection onto the image (range) of A (the space spanned by the column vectors of A).

External links

Citations