Basics of the pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ

1Introduction

The key point of this lecture is that the pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ extends the idea of an inverse matrix逆行列ぎゃくぎょうれつ to matrices that are rectangular or rank階数かいすう-deficient, and it does so by selecting least-squares and least-norm solutions.

An inverse matrix逆行列ぎゃくぎょうれつ exists only for square matrices that lose no information. But rectangular or rank階数かいすう-deficient matrices still occur constantly in approximation and data problems. The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ gives a canonical linear-algebraic way to handle them.

2Terms and definitions

The Moore-Penrose pseudoinverseムーア・ペンローズ擬似逆行列ぎじぎゃくぎょうれつ is defined from SVD. In the real case, if

then

In the complex case, if

then

Here ${\mathrm{\Sigma }}^{+}$\Sigma^+ is formed by replacing each nonzero singular value特異値とくいち ${\sigma }_i$\sigma_i by $1/{\sigma }_i$1/\sigma_i and transposing the rectangular diagonal shape.

3Plan

Use SVD to decompose the action of $A$A into orthogonal/unitary changes of coordinates and nonnegative stretching. Reverse only the nonzero stretching directions. Directions with zero singular value特異値とくいち have lost information, so they cannot be inverted.

4Intuitive explanation

The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ reverses what can be reversed. If $A$A multiplies a direction by $3$3, then $A^{+}$A^+ multiplies that direction by $1/3$1/3. If $A$A collapses a direction to zero, the information is gone, and $A^{+}$A^+ does not attempt to reconstruct it.

5Precise explanation

5.11. Agreement with the inverse

If $A$A is invertible可逆かぎゃく, all singular values特異値とくいち are positive and ${\mathrm{\Sigma }}^{+}={\mathrm{\Sigma }}^{-1}$\Sigma^+=\Sigma^{-1}. Therefore

Thus the pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ is a genuine extension of the inverse.

5.22. Least squares and least norm

If $Ax=b$Ax=b has no solution, then

minimizes $\parallel Ax-b\parallel$\|Ax-b\| among all $x$x, and among all minimizers it has the smallest norm. If $Ax=b$Ax=b does have solutions, $A^{+}b$A^+b is the solution with smallest norm.

To see this through SVD, write $A=U\mathrm{\Sigma }{V}^{*}$A=U\Sigma V^* and set $U^{*}b=c$U^*b=c. The minimization becomes

For ${\sigma }_i>0$\sigma_i>0, the best choice is $y_i=c_i/{\sigma }_i$y_i=c_i/\sigma_i. For ${\sigma }_i=0$\sigma_i=0, changing $y_i$y_i cannot reduce the residual, so the least-norm choice is $y_i=0$y_i=0. This is exactly

5.33. rank階数かいすう-condition formulas

If the columns of $A$A are linearly independent, then

in the real case, and

in the complex case.

If the rows of $A$A are linearly independent, then

in the real case, and

in the complex case.

5.44. Penrose conditions

The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ is also uniquely characterized by the four Penrose equations:

The first two equations say that the map behaves like an inverse on the parts where inversion is possible. The last two say that the resulting projections are orthogonal projections.

5.55. Projection meaning of $A{A}^{+}$AA^+ and $A^{+}A$A^+A

If the compact SVD is

then

is the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A), and

is the orthogonal projection直交射影ちょっこうしゃえい onto the row space行空間ぎょうくうかん. In the real case, replace $*$* by $T$T.

Thus $A{A}^{+}b$AA^+b is the reachable part of $b$b inside the column space列空間れつくうかん, while $A^{+}A$A^+A removes unnecessary nullspace components from a coefficient vector.

6Concrete examples

For

the singular values特異値とくいち are $2$2 and $0$0, so

The lost second component is not reconstructed.

For the rectangular matrix長方行列ちょうほうぎょうれつ

we have

For $b=(1,3{)}^T$b=(1,3)^T,

Then $Ax=(2,2{)}^T$Ax=(2,2)^T is the orthogonal projection直交射影ちょっこうしゃえい of $b$b onto $\mathrm{span}\left\{\right(1,1{)}^T\}$\operatorname{span}\{(1,1)^T\}. This is the operation of averaging the two measurements $1$1 and $3$3.

7Projection viewpoint and numerical warning

The pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ is closely related to projection. The matrix $A{A}^{+}$AA^+ can be interpreted as the orthogonal projection直交射影ちょっこうしゃえい onto the column space列空間れつくうかん, and $A^{+}A$A^+A can be interpreted as the orthogonal projection onto the row space行空間ぎょうくうかん.

If a singular value特異値とくいち is nonzero but extremely small, its reciprocal is extremely large. Then $A^{+}$A^+ can amplify small errors in $b$b. In practice, truncated SVD or Tikhonov regularization is often used to suppress the effect of very small singular values特異値とくいち.

In truncated SVD one uses

after keeping only selected singular values. In Tikhonov regularization, the factor ${\sigma }_{i^{-1}}$\sigma_i^{-1} is replaced by ${\sigma }_i/({\sigma }_{i^2}+\lambda )$\sigma_i/(\sigma_i^2+\lambda).

8Criteria

• The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ is defined from SVD.
• Only nonzero singular values特異値とくいち are inverted.
• For invertible可逆かぎゃく matrices, it equals the ordinary inverse.
• The Penrose conditions characterize it uniquely.
• In inconsistent systems, it gives a least-squares solution最小二乗解さいしょうにじょうかい.
• In underdetermined or nonunique systems, it gives the least-norm solution最小さいしょうノルム解かい.

9Scope and limitations

The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ exists for every real or complex matrix. However, when singular values特異値とくいち are extremely small, the exact pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ may be numerically unstable. In that case, truncated SVD or regularization should be considered.

10Theorem: what $A^{+}b$A^+b selects

The pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ has the following meaning for $Ax=b$Ax=b.

• If $Ax=b$Ax=b has solutions, $A^{+}b$A^+b is the solution with minimum normノルム.
• If $Ax=b$Ax=b has no solution, $A^{+}b$A^+b is the minimum-norm solution among the minimizers of $\parallel Ax-b\parallel$\|Ax-b\|.

Using the SVD $A=U\mathrm{\Sigma }{V}^{*}$A=U\Sigma V^* and writing $U^{*}b=c$U^*b=c, the problem becomes

Since $\mathrm{\Sigma }$\Sigma only stretches along diagonal directions, directions with ${\sigma }_i>0$\sigma_i>0 force $y_i=c_i/{\sigma }_i$y_i=c_i/\sigma_i. Directions with ${\sigma }_i=0$\sigma_i=0 cannot reduce the residual, so the minimum-norm choice sets those $y_i$y_i to $0$0. This gives

11Projection meaning

$A{A}^{+}$AA^+ is the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{Col}\left(A\right)$\operatorname{Col}(A). Thus $A{A}^{+}b$AA^+b is the reachable part of $b$b, namely the closest point to $b$b in the column space列空間れつくうかん of $A$A.

On the other hand, $A^{+}A$A^+A is the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{Row}\left(A\right)$\operatorname{Row}(A). It removes the unnecessary component in the $\ker \left(A\right)$\ker(A) direction from $x$x and selects the minimum-norm representative.

12Calculation example: pseudoinverse of a rectangular matrix

Let

This maps $\mathbb{R}$\mathbb R to $R^2$\mathbb R^2 by sending $x$x to $(x,x)$(x,x). The column is independent, so

For $b=(1,3{)}^T$b=(1,3)^T,

and $Ax=(2,2{)}^T$Ax=(2,2)^T is the orthogonal projection直交射影ちょっこうしゃえい of $b$b onto $\mathrm{span}\left\{\right(1,1{)}^T\}$\operatorname{span}\{(1,1)^T\}. This is the same operation as averaging the two values $1$1 and $3$3.

13Pitfall: small singular values特異値とくいち

If ${\sigma }_i$\sigma_i is nonzero but very small, $1/{\sigma }_i$1/\sigma_i is very large and can greatly amplify small errors in $b$b. Therefore the theoretical $A^{+}$A^+ is not always the best numerical choice. In practice, truncated SVD or Tikhonov regularization is used to suppress reciprocals of small singular values特異値とくいち.

14Final forms

15In one sentence

The pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ gives the canonical inverse-like operation based on projection, least squares, and least-norm selection when an ordinary inverse is unavailable.

16Exercise link

17Related links