Moore–Penrose inverse

Template:Short description In mathematics, and in particular linear algebra, the Moore–Penrose inverse Template:Tmath of a matrix Template:Tmath, often called the pseudoinverse, is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. The terms pseudoinverse and generalized inverse are sometimes used as synonyms for the Moore–Penrose inverse of a matrix, but sometimes applied to other elements of algebraic structures which share some but not all properties expected for an inverse element.

A common use of the pseudoinverse is to compute a "best fit" (least squares) approximate solution to a system of linear equations that lacks an exact solution (see below under § Applications). Another use is to find the minimum (Euclidean) norm solution to a system of linear equations with multiple solutions. The pseudoinverse facilitates the statement and proof of results in linear algebra.

The pseudoinverse is defined for all rectangular matrices whose entries are real or complex numbers. Given a rectangular matrix with real or complex entries, its pseudoinverse is unique. It can be computed using the singular value decomposition. In the special case where Template:Tmath is a normal matrix (for example, a Hermitian matrix), the pseudoinverse Template:Tmath annihilates the kernel of Template:Tmath and acts as a traditional inverse of Template:Tmath on the subspace orthogonal to the kernel.

Notation

In the following discussion, the following conventions are adopted.

• Template:Tmath will denote one of the fields of real or complex numbers, denoted Template:Tmath, Template:Tmath, respectively. The vector space of Template:Tmath matrices over Template:Tmath is denoted by Template:Tmath.
• For Template:Tmath, the transpose is denoted Template:Tmath and the Hermitian transpose (also called conjugate transpose) is denoted Template:Tmath. If $𝕂=ℝ$, then $A^{*}=A^{𝖳}$.
• For Template:Tmath, Template:Tmath (standing for "range") denotes the column space (image) of Template:Tmath (the space spanned by the column vectors of Template:Tmath) and Template:Tmath denotes the kernel (null space) of Template:Tmath.
• For any positive integer Template:Tmath, the Template:Tmath identity matrix is denoted Template:Tmath.

Definition

For $A\in {𝕂}^{m\times n}$, a pseudoinverse of Template:Mvar is defined as a matrix Template:Tmath satisfying all of the following four criteria, known as the Moore–Penrose conditions:

1. Template:Tmath need not be the general identity matrix, but it maps all column vectors of Template:Mvar to themselves: $$A{A}^{+}A=A.$$
2. Template:Tmath acts like a weak inverse: $$A^{+}A{A}^{+}=A^{+}.$$
3. Template:Tmath is Hermitian: $${\left(A{A}^{+}\right)}^{*}=A{A}^{+}.$$
4. Template:Tmath is also Hermitian: $${\left(A^{+}A\right)}^{*}=A^{+}A.$$

Note that $A^{+}A$ and $A{A}^{+}$ are idempotent operators, as follows from $(A{A}^{+}{)}^2=A{A}^{+}$ and $(A^{+}A{)}^2=A^{+}A$. More specifically, $A^{+}A$ projects onto the image of $A^T$ (equivalently, the span of the rows of $A$), and $A{A}^{+}$ projects onto the image of $A$ (equivalently, the span of the columns of $A$). In fact, the above four conditions are fully equivalent to $A^{+}A$ and $A{A}^{+}$ being such orthogonal projections: $A{A}^{+}$ projecting onto the image of $A$ implies $(A{A}^{+})A=A$, and $A^{+}A$ projecting onto the image of $A^T$ implies $(A^{+}A)A^T=A^T$.

The pseudoinverse $A^{+}$ exists for any matrix $A\in {𝕂}^{m\times n}$. If furthermore $A$ is full rank, that is, its rank is Template:Tmath, then Template:Tmath can be given a particularly simple algebraic expression. In particular:

• When Template:Tmath has linearly independent columns (equivalently, Template:Tmath is injective, and thus Template:Tmath is invertible), Template:Tmath can be computed as$$A^{+}={\left(A^{*}A\right)}^{-1}{A}^{*}.$$This particular pseudoinverse is a left inverse, that is, $A^{+}A=I$.
• If, on the other hand, $A$ has linearly independent rows (equivalently, $A$ is surjective, and thus Template:Tmath is invertible), Template:Tmath can be computed as$$A^{+}=A^{*}{\left(A{A}^{*}\right)}^{-1}.$$This is a right inverse, as $A{A}^{+}=I$.

In the more general case, the pseudoinverse can be expressed leveraging the singular value decomposition. Any matrix can be decomposed as $A=UD{V}^{*}$ for some isometries $U,V$ and diagonal nonnegative real matrix $D$. The pseudoinverse can then be written as $A^{+}=V{D}^{+}{U}^{*}$, where $D^{+}$ is the pseudoinverse of $D$ and can be obtained by transposing the matrix and replacing the nonzero values with their multiplicative inverses.Template:Sfn That this matrix satisfies the above requirement is directly verified observing that $A{A}^{+}=U{U}^{*}$ and $A^{+}A=V{V}^{*}$, which are the projections onto image and support of $A$, respectively.

Properties

Existence and uniqueness

As discussed above, for any matrix Template:Tmath there is one and only one pseudoinverse Template:Tmath.

A matrix satisfying only the first of the conditions given above, namely $A{A}^{+}A=A$, is known as a generalized inverse. If the matrix also satisfies the second condition, namely $A^{+}A{A}^{+}=A^{+}$, it is called a generalized reflexive inverse. Generalized inverses always exist but are not in general unique. Uniqueness is a consequence of the last two conditions.

Basic properties

Proofs for the properties below can be found at b:Topics in Abstract Algebra/Linear algebra.

• If Template:Tmath has real entries, then so does Template:Tmath.
• If Template:Tmath is invertible, its pseudoinverse is its inverse. That is, $A^{+}=A^{-1}$.Template:Rp
• The pseudoinverse of the pseudoinverse is the original matrix: ${\left(A^{+}\right)}^{+}=A$.Template:Rp
• Pseudoinversion commutes with transposition, complex conjugation, and taking the conjugate transpose:Template:Rp $${\left(A^{𝖳}\right)}^{+}={\left(A^{+}\right)}^{𝖳},{\left(\bar{A}\right)}^{+}=\overline{A^{+}},{\left(A^{*}\right)}^{+}={\left(A^{+}\right)}^{*}.$$
• The pseudoinverse of a scalar multiple of Template:Tmath is the reciprocal multiple of Template:Tmath:$${\left(\alpha A\right)}^{+}={\alpha }^{-1}{A}^{+}$$ for Template:Tmath; otherwise, ${\left(0A\right)}^{+}=0A^{+}=0A^{𝖳}$, or $0^{+}=0^{𝖳}$.
• The kernel and image of the pseudoinverse coincide with those of the conjugate transpose: $\ker \left(A^{+}\right)=\ker \left(A^{*}\right)$ and $\mathrm{ran}\left(A^{+}\right)=\mathrm{ran}\left(A^{*}\right)$.

Identities

The following identity formula can be used to cancel or expand certain subexpressions involving pseudoinverses: $$A=A{A}^{*}{A}^{+*}=A^{+*}{A}^{*}A.$$ Equivalently, substituting $A^{+}$ for $A$ gives $$A^{+}=A^{+}{A}^{+*}{A}^{*}=A^{*}{A}^{+*}{A}^{+},$$ while substituting $A^{*}$ for $A$ gives $$A^{*}=A^{*}A{A}^{+}=A^{+}A{A}^{*}.$$

Reduction to Hermitian case

The computation of the pseudoinverse is reducible to its construction in the Hermitian case. This is possible through the equivalences: $$A^{+}={\left(A^{*}A\right)}^{+}{A}^{*},$$ $$A^{+}=A^{*}{\left(A{A}^{*}\right)}^{+},$$

as Template:Tmath and Template:Tmath are Hermitian.

Pseudoinverse of products

The equality Template:Tmath does not hold in general. Rather, suppose Template:Tmath. Then the following are equivalent:

1. $(AB{)}^{+}=B^{+}{A}^{+}$
2. $A^{+}AB{B}^{*}{A}^{*}=B{B}^{*}{A}^{*}$ and $B{B}^{+}{A}^{*}AB=A^{*}AB$
3. ${\left(A^{+}AB{B}^{*}\right)}^{*}=A^{+}AB{B}^{*}$ and ${\left(A^{*}AB{B}^{+}\right)}^{*}=A^{*}AB{B}^{+}$
4. $A^{+}AB{B}^{*}{A}^{*}AB{B}^{+}=B{B}^{*}{A}^{*}A$
5. $A^{+}AB=B(AB{)}^{+}AB$ and $B{B}^{+}{A}^{*}=A^{*}AB(AB{)}^{+}$.

The following are sufficient conditions for Template:Tmath:

1. Template:Tmath has orthonormal columns (then $A^{*}A=A^{+}A=I_n$), or
2. Template:Tmath has orthonormal rows (then $B{B}^{*}=B{B}^{+}=I_n$), or
3. Template:Tmath has linearly independent columns (then $A^{+}A=I$ ) and Template:Tmath has linearly independent rows (then $B{B}^{+}=I$),   or
4. $B=A^{*}$, or
5. $B=A^{+}$.

The following is a necessary condition for Template:Tmath:

1. $(A^{+}A)(B{B}^{+})=(B{B}^{+})(A^{+}A)$

The fourth sufficient condition yields the equalities $$\begin{array}{cc}{\left(A{A}^{*}\right)}^{+}& =A^{+*}{A}^{+},\\ {\left(A^{*}A\right)}^{+}& =A^{+}{A}^{+*}.\end{array}$$

Here is a counterexample where Template:Tmath:

$$(\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)\left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right){)}^{+}={\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)}^{+}=\left(\begin{array}{cc}\frac{1}{2}& 0\\ \frac{1}{2}& 0\end{array}\right)\ne \left(\begin{array}{cc}\frac{1}{4}& 0\\ \frac{1}{4}& 0\end{array}\right)=\left(\begin{array}{cc}0& \frac{1}{2}\\ 0& \frac{1}{2}\end{array}\right)\left(\begin{array}{cc}\frac{1}{2}& 0\\ \frac{1}{2}& 0\end{array}\right)={\left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right)}^{+}{\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)}^{+}$$

Projectors

$P=A{A}^{+}$ and $Q=A^{+}A$ are orthogonal projection operators, that is, they are Hermitian ($P=P^{*}$, $Q=Q^{*}$) and idempotent ($P^2=P$ and $Q^2=Q$). The following hold:

• $PA=AQ=A$ and $A^{+}P=Q{A}^{+}=A^{+}$
• Template:Tmath is the orthogonal projector onto the range of Template:Tmath (which equals the orthogonal complement of the kernel of Template:Tmath).
• Template:Tmath is the orthogonal projector onto the range of Template:Tmath (which equals the orthogonal complement of the kernel of Template:Tmath).
• $I-Q=I-A^{+}A$ is the orthogonal projector onto the kernel of Template:Tmath.
• $I-P=I-A{A}^{+}$ is the orthogonal projector onto the kernel of Template:Tmath.

The last two properties imply the following identities:

• $A(I-A^{+}A)=(I-A{A}^{+})A=0$
• $A^{*}(I-A{A}^{+})=(I-A^{+}A)A^{*}=0$

Another property is the following: if Template:Tmath is Hermitian and idempotent (true if and only if it represents an orthogonal projection), then, for any matrix Template:Tmath the following equation holds: $$A(BA{)}^{+}=(BA{)}^{+}$$

This can be proven by defining matrices $C=BA$, $D=A(BA{)}^{+}$, and checking that Template:Tmath is indeed a pseudoinverse for Template:Tmath by verifying that the defining properties of the pseudoinverse hold, when Template:Tmath is Hermitian and idempotent.

From the last property it follows that, if Template:Tmath is Hermitian and idempotent, for any matrix Template:Tmath $$(AB{)}^{+}A=(AB{)}^{+}$$

Finally, if Template:Tmath is an orthogonal projection matrix, then its pseudoinverse trivially coincides with the matrix itself, that is, $A^{+}=A$.

Geometric construction

If we view the matrix as a linear map Template:Tmath over the field Template:Tmath then Template:Tmath can be decomposed as follows. We write Template:Tmath for the direct sum, Template:Tmath for the orthogonal complement, Template:Tmath for the kernel of a map, and Template:Tmath for the image of a map. Notice that ${𝕂}^n={(\ker A)}^{\perp }\oplus \ker A$ and ${𝕂}^m=\mathrm{ran}A\oplus {(\mathrm{ran}A)}^{\perp }$. The restriction $A:{(\ker A)}^{\perp }\to \mathrm{ran}A$ is then an isomorphism. This implies that Template:Tmath on Template:Tmath is the inverse of this isomorphism, and is zero on ${(\mathrm{ran}A)}^{\perp }.$

In other words: To find Template:Tmath for given Template:Tmath in Template:Tmath, first project Template:Tmath orthogonally onto the range of Template:Tmath, finding a point Template:Tmath in the range. Then form Template:Tmath, that is, find those vectors in Template:Tmath that Template:Tmath sends to Template:Tmath. This will be an affine subspace of Template:Tmath parallel to the kernel of Template:Tmath. The element of this subspace that has the smallest length (that is, is closest to the origin) is the answer Template:Tmath we are looking for. It can be found by taking an arbitrary member of Template:Tmath and projecting it orthogonally onto the orthogonal complement of the kernel of Template:Tmath.

This description is closely related to the minimum-norm solution to a linear system.

Limit relations

The pseudoinverse are limits: $$A^{+}=\underset{\delta \searrow 0}{\lim }{(A^{*}A+\delta I)}^{-1}{A}^{*}=\underset{\delta \searrow 0}{\lim }{A}^{*}{(A{A}^{*}+\delta I)}^{-1}$$ (see Tikhonov regularization). These limits exist even if Template:Tmath or Template:Tmath do not exist.Template:Rp

Continuity

In contrast to ordinary matrix inversion, the process of taking pseudoinverses is not continuous: if the sequence Template:Tmath converges to the matrix Template:Tmath (in the maximum norm or Frobenius norm, say), then Template:Tmath need not converge to Template:Tmath. However, if all the matrices Template:Tmath have the same rank as Template:Tmath, Template:Tmath will converge to Template:Tmath.

Derivative

Let $x\mapsto A(x)$ be a real-valued differentiable matrix function with constant rank at a point Template:Tmath. The derivative of $x\mapsto A^{+}(x)$ at $x_0$ may be calculated in terms of the derivative of $A$ at $x_0$: $${\frac{\mathrm{d}}{\mathrm{d}x}|}_{x=x_0}{A}^{+}=-A^{+}\left(\frac{\mathrm{d}A}{\mathrm{d}x}\right)A^{+}+A^{+}{A}^{+\mathrm{\top }}\left(\frac{\mathrm{d}{A}^{\mathrm{\top }}}{\mathrm{d}x}\right)(I-A{A}^{+})+(I-A^{+}A)\left(\frac{\mathrm{d}{A}^{\mathrm{\top }}}{\mathrm{d}x}\right)A^{+\mathrm{\top }}{A}^{+},$$ where the functions $A$, $A^{+}$ and derivatives on the right side are evaluated at $x_0$ (that is, $A:=A(x_0)$, $A^{+}:=A^{+}(x_0)$, etc.). For a complex matrix, the transpose is replaced with the conjugate transpose. For a real-valued symmetric matrix, the Magnus-Neudecker derivative is established.

Examples

Since for invertible matrices the pseudoinverse equals the usual inverse, only examples of non-invertible matrices are considered below.

• For $A=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right),$ the pseudoinverse is $A^{+}=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right).$ The uniqueness of this pseudoinverse can be seen from the requirement $A^{+}=A^{+}A{A}^{+}$, since multiplication by a zero matrix would always produce a zero matrix.
• For $A=\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right),$ the pseudoinverse is $A^{+}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ 0& 0\end{array}\right)$.

Indeed, $A{A}^{+}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$, and thus $A{A}^{+}A=\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right)=A$. Similarly, $A^{+}A=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$, and thus $A^{+}A{A}^{+}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ 0& 0\end{array}\right)=A^{+}$.

Note that Template:Tmath is neither injective nor surjective, and thus the pseudoinverse cannot be computed via $A^{+}={\left(A^{*}A\right)}^{-1}{A}^{*}$ nor $A^{+}=A^{*}{\left(A{A}^{*}\right)}^{-1}$, as $A^{*}A$ and $A{A}^{*}$ are both singular, and furthermore $A^{+}$ is neither a left nor a right inverse.

Nonetheless, the pseudoinverse can be computed via SVD observing that $A=\sqrt{2}\left(\frac{{𝐞}_1+{𝐞}_2}{\sqrt{2}}\right){𝐞}_1^{*}$, and thus $A^{+}=\frac{1}{\sqrt{2}}{𝐞}_1{\left(\frac{{𝐞}_1+{𝐞}_2}{\sqrt{2}}\right)}^{*}$.

• For $A=\left(\begin{array}{cc}1& 0\\ -1& 0\end{array}\right),$ $A^{+}=\left(\begin{array}{cc}\frac{1}{2}& -\frac{1}{2}\\ 0& 0\end{array}\right).$
• For $A=\left(\begin{array}{cc}1& 0\\ 2& 0\end{array}\right),$ $A^{+}=\left(\begin{array}{cc}\frac{1}{5}& \frac{2}{5}\\ 0& 0\end{array}\right)$. The denominators are here $5=1^2+2^2$.
• For $A=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right),$ $A^{+}=\left(\begin{array}{cc}\frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}\end{array}\right).$
• For $A=\left(\begin{array}{cc}1& 0\\ 0& 1\\ 0& 1\end{array}\right),$ the pseudoinverse is $A^{+}=\left(\begin{array}{ccc}1& 0& 0\\ 0& \frac{1}{2}& \frac{1}{2}\end{array}\right)$.

For this matrix, the left inverse exists and thus equals $A^{+}$, indeed, $A^{+}A=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right).$

Special cases

Scalars

It is also possible to define a pseudoinverse for scalars and vectors. This amounts to treating these as matrices. The pseudoinverse of a scalar Template:Tmath is zero if Template:Tmath is zero and the reciprocal of Template:Tmath otherwise: $$x^{+}=\{\begin{array}{cc}0,& \text{if }x=0;\\ x^{-1},& \text{otherwise}.\end{array}$$

Vectors

The pseudoinverse of the null (all zero) vector is the transposed null vector. The pseudoinverse of a non-null vector is the conjugate transposed vector divided by its squared magnitude:

$${\overrightarrow{x}}^{+}=\{\begin{array}{cc}{\overrightarrow{0}}^{𝖳},& \text{if }\overrightarrow{x}=\overrightarrow{0};\\ \frac{{\overrightarrow{x}}^{*}}{({\overrightarrow{x}}^{*}\overrightarrow{x})},& \text{otherwise}.\end{array}$$

Diagonal matrices

The pseudoinverse of a squared diagonal matrix is obtained by taking the reciprocal of the nonzero diagonal elements. Formally, if $D$ is a squared diagonal matrix with $D=\tilde{D}\oplus {\mathrm{𝟎}}_{k\times k}$ and $\tilde{D}>0$, then $D^{+}={\tilde{D}}^{-1}\oplus {\mathrm{𝟎}}_{k\times k}$. More generally, if $A$ is any $m\times n$ rectangular matrix whose only nonzero elements are on the diagonal, meaning $A_{ij}={\delta }_{ij}{a}_i$, $a_i\in 𝕂$, then $A^{+}$ is a $n\times m$ rectangular matrix whose diagonal elements are the reciprocal of the original ones, that is, $A_{ii}\ne 0⟹A_{ii}^{+}=\frac{1}{A_{ii}}$.

Linearly independent columns

If the rank of Template:Tmath is identical to the number of columns, Template:Tmath, (for Template:Tmath,) there are Template:Tmath linearly independent columns, and Template:Tmath is invertible. In this case, an explicit formula is:Template:Sfn $$A^{+}={\left(A^{*}A\right)}^{-1}{A}^{*}.$$

It follows that Template:Tmath is then a left inverse of Template:Tmath:   $A^{+}A=I_n$.

Linearly independent rows

If the rank of Template:Tmath is identical to the number of rows, Template:Tmath, (for Template:Tmath,) there are Template:Tmath linearly independent rows, and Template:Tmath is invertible. In this case, an explicit formula is: $$A^{+}=A^{*}{\left(A{A}^{*}\right)}^{-1}.$$

It follows that Template:Tmath is a right inverse of Template:Tmath:   $A{A}^{+}=I_m$.

Orthonormal columns or rows

This is a special case of either full column rank or full row rank (treated above). If Template:Tmath has orthonormal columns ($A^{*}A=I_n$) or orthonormal rows ($A{A}^{*}=I_m$), then: $$A^{+}=A^{*}.$$

Normal matrices

If Template:Tmath is normal, that is, it commutes with its conjugate transpose, then its pseudoinverse can be computed by diagonalizing it, mapping all nonzero eigenvalues to their inverses, and mapping zero eigenvalues to zero. A corollary is that Template:Tmath commuting with its transpose implies that it commutes with its pseudoinverse.

EP matrices

A (square) matrix Template:Tmath is said to be an EP matrix if it commutes with its pseudoinverse. In such cases (and only in such cases), it is possible to obtain the pseudoinverse as a polynomial in Template:Tmath. A polynomial $p(t)$ such that $A^{+}=p(A)$ can be easily obtained from the characteristic polynomial of Template:Tmath or, more generally, from any annihilating polynomial of Template:Tmath.

Orthogonal projection matrices

This is a special case of a normal matrix with eigenvalues 0 and 1. If Template:Tmath is an orthogonal projection matrix, that is, $A=A^{*}$ and $A^2=A$, then the pseudoinverse trivially coincides with the matrix itself: $$A^{+}=A.$$

Circulant matrices

For a circulant matrix Template:Tmath, the singular value decomposition is given by the Fourier transform, that is, the singular values are the Fourier coefficients. Let Template:Tmath be the Discrete Fourier Transform (DFT) matrix; then $$\begin{array}{cc}C& =ℱ\cdot \mathrm{\Sigma }\cdot {ℱ}^{*},\\ C^{+}& =ℱ\cdot {\mathrm{\Sigma }}^{+}\cdot {ℱ}^{*}.\end{array}$$

Construction

Rank decomposition

Let Template:Tmath denote the rank of Template:Tmath. Then Template:Tmath can be (rank) decomposed as $A=BC$ where Template:Tmath and Template:Tmath are of rank Template:Tmath. Then $A^{+}=C^{+}{B}^{+}=C^{*}{\left(C{C}^{*}\right)}^{-1}{\left(B^{*}B\right)}^{-1}{B}^{*}$.

The QR method

For $𝕂\in \{ℝ,ℂ\}$ computing the product Template:Tmath or Template:Tmath and their inverses explicitly is often a source of numerical rounding errors and computational cost in practice. An alternative approach using the QR decomposition of Template:Tmath may be used instead.

Consider the case when Template:Tmath is of full column rank, so that $A^{+}={\left(A^{*}A\right)}^{-1}{A}^{*}$. Then the Cholesky decomposition $A^{*}A=R^{*}R$, where Template:Tmath is an upper triangular matrix, may be used. Multiplication by the inverse is then done easily by solving a system with multiple right-hand sides, $$A^{+}={\left(A^{*}A\right)}^{-1}{A}^{*}\iff \left(A^{*}A\right)A^{+}=A^{*}\iff R^{*}R{A}^{+}=A^{*}$$

which may be solved by forward substitution followed by back substitution.

The Cholesky decomposition may be computed without forming Template:Tmath explicitly, by alternatively using the QR decomposition of $A=QR$, where $Q$ has orthonormal columns, $Q^{*}Q=I$, and Template:Tmath is upper triangular. Then $$A^{*}A=(QR{)}^{*}(QR)=R^{*}{Q}^{*}QR=R^{*}R,$$

so Template:Tmath is the Cholesky factor of Template:Tmath.

The case of full row rank is treated similarly by using the formula $A^{+}=A^{*}{\left(A{A}^{*}\right)}^{-1}$ and using a similar argument, swapping the roles of Template:Tmath and Template:Tmath.

Using polynomials in matrices

For an arbitrary Template:Tmath, one has that $A^{*}A$ is normal and, as a consequence, an EP matrix. One can then find a polynomial $p(t)$ such that $(A^{*}A{)}^{+}=p(A^{*}A)$. In this case one has that the pseudoinverse of Template:Tmath is given by $$A^{+}=p(A^{*}A)A^{*}=A^{*}p(A{A}^{*}).$$

Singular value decomposition (SVD)

A computationally simple and accurate way to compute the pseudoinverse is by using the singular value decomposition.Template:Sfn If $A=U\mathrm{\Sigma }{V}^{*}$ is the singular value decomposition of Template:Tmath, then $A^{+}=V{\mathrm{\Sigma }}^{+}{U}^{*}$. For a rectangular diagonal matrix such as Template:Tmath, we get the pseudoinverse by taking the reciprocal of each non-zero element on the diagonal, leaving the zeros in place. In numerical computation, only elements larger than some small tolerance are taken to be nonzero, and the others are replaced by zeros. For example, in the MATLAB or GNU Octave function Template:Mono, the tolerance is taken to be Template:Math, where ε is the machine epsilon.

The computational cost of this method is dominated by the cost of computing the SVD, which is several times higher than matrix–matrix multiplication, even if a state-of-the art implementation (such as that of LAPACK) is used.

The above procedure shows why taking the pseudoinverse is not a continuous operation: if the original matrix Template:Tmath has a singular value 0 (a diagonal entry of the matrix Template:Tmath above), then modifying Template:Tmath slightly may turn this zero into a tiny positive number, thereby affecting the pseudoinverse dramatically as we now have to take the reciprocal of a tiny number.

Block matrices

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

The iterative method of Ben-Israel and Cohen

Another method for computing the pseudoinverse (cf. Drazin inverse) uses the recursion $$A_{i+1}=2A_i-A_{i}A{A}_i,$$

which is sometimes referred to as hyper-power sequence. This recursion produces a sequence converging quadratically to the pseudoinverse of Template:Tmath if it is started with an appropriate Template:Tmath satisfying $A_{0}A={\left(A_{0}A\right)}^{*}$. The choice $A_0=\alpha A^{*}$ (where $0<\alpha <2/{\sigma }_1^2(A)$, with Template:Tmath denoting the largest singular value of Template:Tmath) has been argued not to be competitive to the method using the SVD mentioned above, because even for moderately ill-conditioned matrices it takes a long time before Template:Tmath enters the region of quadratic convergence. However, if started with Template:Tmath already close to the Moore–Penrose inverse and $A_{0}A={\left(A_{0}A\right)}^{*}$, for example $A_0:={(A^{*}A+\delta I)}^{-1}{A}^{*}$, convergence is fast (quadratic).

Updating the pseudoinverse

For the cases where Template:Tmath has full row or column rank, and the inverse of the correlation matrix (Template:Tmath for Template:Tmath with full row rank or Template:Tmath for full column rank) is already known, the pseudoinverse for matrices related to Template:Tmath can be computed by applying the Sherman–Morrison–Woodbury formula to update the inverse of the correlation matrix, which 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.

Similarly, it is possible to update the Cholesky factor when a row or column is added, without creating the inverse of the correlation matrix explicitly. However, updating the pseudoinverse in the general rank-deficient case is much more complicated.

Software libraries

High-quality implementations of SVD, QR, and back substitution are available in standard libraries, such as LAPACK. Writing one's own implementation of SVD is a major programming project that requires a significant numerical expertise. In special circumstances, such as parallel computing or embedded computing, however, alternative implementations by QR or even the use of an explicit inverse might be preferable, and custom implementations may be unavoidable.

The Python package NumPy provides a pseudoinverse calculation through its functions matrix.I and linalg.pinv; its pinv uses the SVD-based algorithm. SciPy adds a function scipy.linalg.pinv that uses a least-squares solver.

The MASS package for R provides a calculation of the Moore–Penrose inverse through the ginv function. The ginv function calculates a pseudoinverse using the singular value decomposition provided by the svd function in the base R package. An alternative is to employ the pinv function available in the pracma package.

The Octave programming language provides a pseudoinverse through the standard package function pinv and the pseudo_inverse() method.

In Julia (programming language), the LinearAlgebra package of the standard library provides an implementation of the Moore–Penrose inverse pinv() implemented via singular-value decomposition.

Applications

Linear least-squares

The pseudoinverse provides a least squares solution to a system of linear equations. For Template:Tmath, given a system of linear equations $$Ax=b,$$

in general, a vector Template:Tmath that solves the system may not exist, or if one does exist, it may not be unique. More specifically, a solution exists if and only if $b$ is in the image of $A$, and is unique if and only if $A$ is injective. The pseudoinverse solves the "least-squares" problem as follows:

• Template:Tmath, we have ${\Vert Ax-b\Vert }_2\ge {\Vert Az-b\Vert }_2$ where $z=A^{+}b$ and $\Vert \cdot {\Vert }_2$ denotes the Euclidean norm. This weak inequality holds with equality if and only if $x=A^{+}b+(I-A^{+}A)w$ for any vector Template:Tmath; this provides an infinitude of minimizing solutions unless Template:Tmath has full column rank, in which case Template:Tmath is a zero matrix. The solution with minimum Euclidean norm is Template:Tmath

This result is easily extended to systems with multiple right-hand sides, when the Euclidean norm is replaced by the Frobenius norm. Let Template:Tmath.

• Template:Tmath, we have $\Vert AX-B{\Vert }_{\mathrm{F}}\ge \Vert AZ-B{\Vert }_{\mathrm{F}}$ where $Z=A^{+}B$ and $\Vert \cdot {\Vert }_{\mathrm{F}}$ denotes the Frobenius norm.

Obtaining all solutions of a linear system

If the linear system

$$Ax=b$$

has any solutions, they are all given by

$$x=A^{+}b+[I-A^{+}A]w$$

for arbitrary vector Template:Tmath. Solution(s) exist if and only if $A{A}^{+}b=b$. If the latter holds, then the solution is unique if and only if Template:Tmath has full column rank, in which case Template:Tmath is a zero matrix. If solutions exist but Template:Tmath does not have full column rank, then we have an indeterminate system, all of whose infinitude of solutions are given by this last equation.

Minimum norm solution to a linear system

For linear systems $Ax=b,$ with non-unique solutions (such as under-determined systems), the pseudoinverse may be used to construct the solution of minimum Euclidean norm $\Vert x{\Vert }_2$ among all solutions.

• If $Ax=b$ is satisfiable, the vector $z=A^{+}b$ is a solution, and satisfies $\Vert z{\Vert }_2\le \Vert x{\Vert }_2$ for all solutions.

This result is easily extended to systems with multiple right-hand sides, when the Euclidean norm is replaced by the Frobenius norm. Let Template:Tmath.

• If $AX=B$ is satisfiable, the matrix $Z=A^{+}B$ is a solution, and satisfies $\Vert Z{\Vert }_{\mathrm{F}}\le \Vert X{\Vert }_{\mathrm{F}}$ for all solutions.

Condition number

Using the pseudoinverse and a matrix norm, one can define a condition number for any matrix: $$\text{cond}(A)=\Vert A\Vert \Vert A^{+}\Vert .$$

A large condition number implies that the problem of finding least-squares solutions to the corresponding system of linear equations is ill-conditioned in the sense that small errors in the entries of Template:Tmath can lead to huge errors in the entries of the solution.

Generalizations

The weighted pseudoinverse generalizes the Moore-Penrose inverse between metric spaces with weight matrices in the domain and range. These weights are the identity for the standard Moore-Penrose inverse, which assumes an orthonormal basis in both spaces.

In order to solve more general least-squares problems, one can define Moore–Penrose inverses for all continuous linear operators Template:Tmath between two Hilbert spaces Template:Tmath and Template:Tmath, using the same four conditions as in our definition above. It turns out that not every continuous linear operator has a continuous linear pseudoinverse in this sense. Those that do are precisely the ones whose range is closed in Template:Tmath.

A notion of pseudoinverse exists for matrices over an arbitrary field equipped with an arbitrary involutive automorphism. In this more general setting, a given matrix doesn't always have a pseudoinverse. The necessary and sufficient condition for a pseudoinverse to exist is that $\mathrm{rank}(A)=\mathrm{rank}\left(A^{*}A\right)=\mathrm{rank}\left(A{A}^{*}\right)$, where $A^{*}$ denotes the result of applying the involution operation to the transpose of $A$. When it does exist, it is unique. Example: Consider the field of complex numbers equipped with the identity involution (as opposed to the involution considered elsewhere in the article); do there exist matrices that fail to have pseudoinverses in this sense? Consider the matrix $A={\left[\begin{array}{cc}1& i\end{array}\right]}^{𝖳}$. Observe that $\mathrm{rank}\left(A{A}^{𝖳}\right)=1$ while $\mathrm{rank}\left(A^{𝖳}A\right)=0$. So this matrix doesn't have a pseudoinverse in this sense.

In abstract algebra, a Moore–Penrose inverse may be defined on a *-regular semigroup. This abstract definition coincides with the one in linear algebra.

See also

• Drazin inverse
• Hat matrix
• Inverse element
• Linear least squares (mathematics)
• Pseudo-determinant
• Von Neumann regular ring

References

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book

External links

• Template:PlanetMath
• Interactive program & tutorial of Moore–Penrose Pseudoinverse
• Template:PlanetMath
• Template:MathWorld
• Template:MathWorld
• The Moore–Penrose Pseudoinverse. A Tutorial Review of the Theory
• Online Moore–Penrose Inverse calculator