擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixの基本きほん

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

1導入どうにゅう

この講義こうぎで重要じゅうようなのは、擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは、逆行列ぎゃくぎょうれつinverse matrixが存在そんざいしない行列ぎょうれつmatrixに対たいしても、最小二乗解さいしょうにじょうかいと最小さいしょうノルム解かいを統一的とういつてきに与あたえる道具どうぐであるということである。

逆行列ぎゃくぎょうれつinverse matrixは正方行列せいほうぎょうれつsquare matrixで、しかも情報じょうほうを失うしなわない場合ばあいにだけ存在そんざいする。しかし、長方行列ちょうほうぎょうれつや階数落かいすうおちの行列ぎょうれつmatrixにおいても、近似解きんじかいや代表解だいひょうかいを必要ひつようとする状況じょうきょうは多おおい。擬似逆行列ぎじぎゃくぎょうれつ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.

2用語ようごと定義ていぎ

ムーア・ペンローズ擬似逆行列ぎじぎゃくぎょうれつMoore-Penrose pseudoinverse とは、行列ぎょうれつmatrix $$A$$A の特異値分解とくいちぶんかいsingular value decompositionSVDから定義ていぎされる行列ぎょうれつmatrixである。実行列じつぎょうれつでは

に対たいして

で定義ていぎする。複素行列ふくそぎょうれつでは

に対たいして

で定義ていぎする。ここで $${\mathrm{\Sigma }}^{+}$$\Sigma^+ は、$$\mathrm{\Sigma }$$\Sigma の非零特異値ひぜろとくいち $${\sigma }_i$$\sigma_i を $$1/{\sigma }_i$$1/\sigma_i に置換ちかんし、転置てんちした形かたちの行列ぎょうれつmatrixである。

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.

3方針ほうしん

方針ほうしんは、特異値分解とくいちぶんかいsingular value decompositionSVDにより行列ぎょうれつmatrixの作用さようを直交変換ちょっこうへんかんと伸縮しんしゅくへ分解ぶんかいし、非零ひぜろの伸縮方向しんしゅくほうこうだけを反転はんてんすることである。零特異値ぜろとくいちの方向ほうこうは情報じょうほうが消失しょうしつするため、逆変換ぎゃくへんかんを定義ていぎしない。

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.

4直感的ちょっかんてきな説明せつめい

擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは、可能かのうな範囲はんいで逆向ぎゃくむきの操作そうさoperationを実行じっこうする行列ぎょうれつmatrixである。

$$A$$A がある方向ほうこうを 3 倍ばいするなら、$$A^{+}$$A^+ はその方向ほうこうを $$1/3$$1/3 倍ばいする。$$A$$A がある方向ほうこうを 0 に潰つぶすなら、その情報じょうほうは復元不能ふくげんふのうであるため、$$A^{+}$$A^+ はその方向ほうこうを復元ふくげんしない。

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.

5厳密げんみつな説明せつめい

5.11. 正則行列せいそくぎょうれつでは逆行列ぎゃくぎょうれつinverse matrixに一致いっちする

$$A$$A が正則せいそくなら、すべての特異値とくいちsingular valueが正せいである。この場合ばあい、$${\mathrm{\Sigma }}^{+}$$\Sigma^+ は $${\mathrm{\Sigma }}^{-1}$$\Sigma^{-1} に一致いっちし、

である。擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは逆行列ぎゃくぎょうれつinverse matrixの拡張かくちょうである。

5.22. 最小二乗解さいしょうにじょうかい

連立一次方程式れんりついちじほうていしきsystem of linear equations

が解かいを持もたない場合ばあい、$$A^{+}b$$A^+b は

を最小化さいしょうかする解かいのうち、ノルムが最小さいしょうのものを与あたえる。

5.33. 階数条件かいすうじょうけんによる公式こうしき

$$A$$A の列れつcolumnが一次独立いちじどくりつlinear independenceなら、

である。これは正規方程式せいきほうていしきから得えられる最小二乗公式さいしょうにじょうこうしきである。

$$A$$A の行ぎょうrowが一次独立いちじどくりつlinear independenceなら、

である。この場合ばあいは、解かいが複数ふくすう存在そんざいするときに最小さいしょうノルム解かいを選択せんたくする。

複素ふくそcomplexの場合ばあいは、これらの式しきの $$A^T$$A^T を $$A^{*}$$A^* に置換ちかんする。列れつcolumnが一次独立いちじどくりつlinear independenceなら

であり、行ぎょうrowが一次独立いちじどくりつlinear independenceなら

である。

5.44. ペンローズの 4 条件じょうけん

擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは SVD による構成こうせいだけでなく、次つぎの 4 条件じょうけんによって一意いちいに特徴とくちょうづけられる。

これらをペンローズの条件じょうけんという。前半ぜんはん 2 式しきは「可能かのうな範囲はんいで逆操作ぎゃくそうさとして機能きのうする」ことを表あらわし、後半こうはん 2 式しきは得えられる射影しゃえいprojectionが直交射影ちょっこうしゃえいorthogonal projectionであることを保証ほしょうする。

5.55. 射影しゃえいprojectionとしての $$A{A}^{+}$$AA^+ と $$A^{+}A$$A^+A

$$A$$A のコンパクト SVD を

とすると、

であり、これは $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) への直交射影ちょっこうしゃえいorthogonal projectionである。また

であり、これは行空間ぎょうくうかんrow spaceへの直交射影ちょっこうしゃえいorthogonal projectionである。実行列じつぎょうれつでは $$*$$* を $$T$$T に置換ちかんする。

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.

6具体例ぐたいていれい

とする。この行列ぎょうれつmatrixは第二成分だいにせいぶんを消去しょうきょするため、正則せいそくではない。特異値とくいちsingular valueは $$2,0$$2,0 である。したがって

である。失うしなわれた第二成分だいにせいぶんは復元ふくげんされない。

この例れいでは

である。どちらも第一成分だいいちせいぶんの軸じくへの直交射影ちょっこうしゃえいorthogonal projectionであり、消去しょうきょされた第二成分だいにせいぶんを復元ふくげんしない。

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.

7射影しゃえいprojectionとしての見方みかたと数値計算上すうちけいさんじょうの注意ちゅうい

擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは、射影しゃえいprojectionとも密接みっせつに関係かんけいする。$$A{A}^{+}$$AA^+ は列空間れつくうかんcolumn spaceへの直交射影ちょっこうしゃえいorthogonal projection、$$A^{+}A$$A^+A は行空間ぎょうくうかんrow spaceへの直交射影ちょっこうしゃえいorthogonal projectionとして解釈かいしゃくできる。

数値計算すうちけいさんでは、極端きょくたんに小ちいさい特異値とくいちsingular valueをそのまま逆数ぎゃくすうにすると誤差ごさが増幅ぞうふくされる。そのため、小ちいさい特異値とくいちsingular valueを除外じょがいする切断せつだん SVD

や、$${\sigma }_{i^{-1}}$$\sigma_i^{-1} の代かわりに $${\sigma }_i/({\sigma }_{i^2}+\lambda )$$\sigma_i/(\sigma_i^2+\lambda) を用もちいる正則化せいそくかが利用りようされる。

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).

8判定基準はんていきじゅん

• 擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは特異値分解とくいちぶんかいsingular value decompositionSVDから定義ていぎされる。
• 非零特異値ひぜろとくいちだけを逆数ぎゃくすうにする。
• 正則行列せいそくぎょうれつでは通常つうじょうの逆行列ぎゃくぎょうれつinverse matrixと一致いっちする。
• ペンローズの 4 条件じょうけんにより一意いちいに定さだまる。
• 解かいが存在そんざいしない場合ばあいは最小二乗解さいしょうにじょうかいを与あたえる。
• 解かいが複数ふくすう存在そんざいする場合ばあいは最小さいしょうノルム解かいを選択せんたくする。

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最小さいしょうノルム解かい.

9どこまで成立せいりつするか

擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは任意にんいの実行列じつぎょうれつ・複素行列ふくそぎょうれつに定義ていぎできる。ただし特異値とくいちsingular valueが極端きょくたんに小ちいさい場合ばあい、逆数ぎゃくすうが大おおきくなり、数値的不安定性すうちてきふあんていせいが生しょうじる。この場合ばあいは切断特異値分解せつだんとくいちぶんかいや正則化せいそくかを検討けんとうする。

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.

10命題めいだい：$$A^{+}b$$A^+b が選えらぶ解かい

擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは、$$Ax=b$$Ax=b の状況じょうきょうに応おうじて次つぎの意味いみを持もつ。

• $$Ax=b$$Ax=b が解かいを持もつ場合ばあい、$$A^{+}b$$A^+b はその解かいの中なかでノルムnormが最小さいしょうのものを与あたえる。
• $$Ax=b$$Ax=b が解かいを持もたない場合ばあい、$$A^{+}b$$A^+b は $$\parallel Ax-b\parallel$$\|Ax-b\| を最小さいしょうにする解かいの中なかでノルムnormが最小さいしょうのものを与あたえる。

SVD で $$A=U\mathrm{\Sigma }{V}^{*}$$A=U\Sigma V^* と書かき、$$U^{*}b=c$$U^*b=c と置おくと、問題もんだいは

へ変換へんかんされる。$$\mathrm{\Sigma }$$\Sigma は対角方向たいかくほうこうの伸縮しんしゅくだけなので、$${\sigma }_i>0$$\sigma_i>0 の方向ほうこうでは $$y_i=c_i/{\sigma }_i$$y_i=c_i/\sigma_i と決きまり、$${\sigma }_i=0$$\sigma_i=0 の方向ほうこうでは $$y_i$$y_i は残差ざんさを減へらせない。そこで最小さいしょうノルムにするため $$y_i=0$$y_i=0 を選えらぶ。この選択せんたくが

である。

11射影しゃえいの意味いみを確認かくにんする

$$A{A}^{+}$$AA^+ は $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) への直交射影ちょっこうしゃえいorthogonal projectionである。したがって $$A{A}^{+}b$$AA^+b は $$b$$b の到達可能とうたつかのうな部分ぶぶん、つまり $$A$$A の列空間れつくうかんcolumn spaceに最もっとも近ちかい点てんを表あらわす。

一方いっぽう、$$A^{+}A$$A^+A は $$\mathrm{Row}\left(A\right)$$\operatorname{Row}(A) への直交射影ちょっこうしゃえいorthogonal projectionである。これは $$x$$x から $$\ker \left(A\right)$$\ker(A) 方向ほうこうの余分よぶんな成分せいぶんを除のぞき、最小さいしょうノルムの代表元だいひょうげんを選えらぶ操作そうさである。

12計算例けいさんれい：長方行列ちょうほうぎょうれつの擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrix

とする。これは $$\mathbb{R}$$\mathbb R から $$R^2$$\mathbb R^2 への写像しゃぞうで、$$x$$x を $$(x,x)$$(x,x) に送おくる。列れつcolumnは一次独立いちじどくりつなので

$$b=(1,3{)}^T$$b=(1,3)^T に対たいして

であり、$$Ax=(2,2{)}^T$$Ax=(2,2)^T が $$b$$b の $$\mathrm{span}\left\{\right(1,1{)}^T\}$$\operatorname{span}\{(1,1)^T\} への直交射影ちょっこうしゃえいorthogonal projectionになる。これは 2 点てん $$1,3$$1,3 の平均へいきんを取とる操作そうさと同おなじである。

13落おとし穴あな：小ちいさい特異値とくいちsingular value

$${\sigma }_i$$\sigma_i が 0 ではないが非常ひじょうに小ちいさい場合ばあい、$$1/{\sigma }_i$$1/\sigma_i は非常ひじょうに大おおきくなり、$$b$$b の小ちいさな誤差ごさを大おおきく増幅ぞうふくする。このため、理論上りろんじょうの $$A^{+}$$A^+ がいつも数値的すうちてきに良よい選択せんたくとは限かぎらない。実務じつむでは切断せつだん SVD や Tikhonov 正則化せいそくかを使つかい、小ちいさな特異値とくいちsingular valueの逆数ぎゃくすうを抑おさえる。

14最終形さいしゅうけい

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

15一言ひとことでいうと

• 擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixは、逆行列ぎゃくぎょうれつinverse matrixを持もたない行列ぎょうれつmatrixに対たいして、射影しゃえいprojectionと最小化さいしょうかに基もとづく代表的だいひょうてきな逆操作ぎゃくそうさを与あたえる。

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.

16演習えんしゅうリンク

16Exercise link

17関連かんれんリンク

17Related links