SVD と擬似逆行列ぎじぎゃくぎょうれつpseudoinverse-基本演習きほんえんしゅう

SVD and pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ - Basic Exercises

1演習えんしゅう方針ほうしん

特異値分解とくいちぶんかいsingular value decompositionは、行列ぎょうれつmatrixを入力側にゅうりょくがわの直交方向ちょっこうほうこう、非負ひふの伸縮率しんしゅくりつ、出力側しゅつりょくがわの直交方向ちょっこうほうこうに分解ぶんかいする。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは、0 でない特異値とくいちsingular valueだけを逆数ぎゃくすうにし、0 の特異値とくいちsingular valueは逆ぎゃくにしない。

1Exercise plan

Singular value decomposition特異値分解とくいちぶんかい decomposes a matrix行列ぎょうれつ into orthogonal input directions, nonnegative stretch factors, and orthogonal output directions. The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ inverts only the nonzero singular values特異値とくいち and leaves zero singular values at 0.

2問題もんだい 1

つぎの空欄くうらんを埋うめよ。

「特異値分解とくいちぶんかいsingular value decompositionは、長方行列ちょうほうぎょうれつを、入力側にゅうりょくがわの直交基底ちょっこうきてい、非負ひふの伸縮率しんしゅくりつ、出力側しゅつりょくがわの直交基底ちょっこうきていに分解ぶんかいする。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは、0 でない特異値とくいちsingular valueを ____ し、0 の特異値とくいちsingular valueは ____ ことで、最小二乗解さいしょうにじょうかいleast-squares solutionや最小さいしょうノルム解かいminimum-norm solutionを記述きじゅつする。」

2.1解答例かいとうれい

「逆数ぎゃくすうに」し、「そのまま $0$0 として扱あつかう」。

2.2解説かいせつ

0 の特異値とくいちsingular valueを逆数ぎゃくすうにしようとすると 0 による除算じょざんdivisionになる。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseでは、潰つぶれた方向ほうこうを無理むりに復元ふくげんしない。

2Problem 1

Fill in the blanks.

"Singular value decomposition特異値分解とくいちぶんかい decomposes a rectangular matrix into an orthogonal basis on the input side, nonnegative stretch factors, and an orthogonal basis on the output side. The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ ____ the nonzero singular values特異値とくいち and ____ the zero singular values, thereby describing least-squares solutions最小二乗解さいしょうにじょうかい and minimum-norm solutions最小ノルム解."

2.1Answer example

"takes reciprocals of" and "keeps them as $0$0."

2.2Explanation

Taking the reciprocal of a zero singular value特異値とくいち would require division by 0. The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ does not force recovery of directions that have been collapsed.

3問題もんだい 2

のコンパクトSVDcompact SVDを 1 つ求もとめよ。

3.1解答例かいとうれい

なので、特異値とくいちsingular valueは $4,3$4,3 である。右みぎ特異とくいベクトルsingular vectorを

と選えらぶと、

である。したがって $A=U_r{\mathrm{\Sigma }}_r{V}_{r^T}$A=U_r\Sigma_rV_r^T、ただし

である。

3.2解説かいせつ

コンパクトSVDcompact SVDでは、0 でない特異値とくいちsingular valueに対応たいおうする方向ほうこうだけを残のこす。階数かいすうrankや列空間れつくうかんcolumn spaceを読よむには、この形かたちが扱あつかいやすい。

3Problem 2

Find one compact SVD[コンパクトSVD] of

3.1Answer example

so the singular values特異値とくいち are $4,3$4,3. Choose right singular vectors特異とくいベクトル

Then

Thus $A=U_r{\mathrm{\Sigma }}_r{V}_{r^T}$A=U_r\Sigma_rV_r^T, where

3.2Explanation

A compact SVD[コンパクトSVD] keeps only the directions corresponding to nonzero singular values. This form is convenient for reading the rank階数かいすう and the column space列空間れつくうかん.

4問題もんだい 3

について、特異値とくいちsingular value、核かくkernel、像ぞうimageを求もとめ、最大さいだいの特異値とくいちsingular valueだけを残のこす階数かいすうrank 1 近似きんじが何なにを保存ほぞんし何なにを捨すてるかを説明せつめいせよ。

4.1解答例かいとうれい

$A^{T}A$A^TA は

なので、特異値とくいちsingular valueは $3,1,0$3,1,0 である。また、

である。最大さいだいの特異値とくいちsingular valueだけを残のこす階数かいすうrank 1 近似きんじは

である。

4.2解説かいせつ

$A_1$A_1 は最もっとも強つよく残のこる $e_1$e_1 方向ほうこうを保存ほぞんし、$e_2$e_2 方向ほうこうの弱よわい成分せいぶんcomponentと $e_3$e_3 方向ほうこうの核かくkernelを捨すてる。SVD による近似きんじは、方向ほうこうごとの重要度じゅうようどを特異値とくいちsingular valueで測はかる。

4Problem 3

For

find the singular values特異値とくいち, the kernel核かく, and the image像ぞう. Explain what is preserved and what is discarded by the rank階数かいすう 1 approximation that keeps only the largest singular value.

4.1Answer example

Since $A^{T}A$A^TA is

the singular values are $3,1,0$3,1,0. Also,

The rank 1 approximation keeping only the largest singular value is

4.2Explanation

$A_1$A_1 preserves the strongest surviving direction, the $e_1$e_1 direction, and discards the weaker $e_2$e_2 component together with the kernel核かく direction $e_3$e_3. SVD-based approximation measures importance by singular values.

5問題もんだい 4

について、非零ひれい特異値とくいちsingular valueを使つかって $B^{+}$B^+ を求もとめ、$B{B}^{+}$BB^+ と $B^{+}B$B^+B が何なにへの射影しゃえいprojectionかを説明せつめいせよ。

5.1解答例かいとうれい

$B=u{v}^T$B=uv^T と書かける。ただし

である。$\parallel u\parallel =\sqrt{5}$\|u\|=\sqrt5、$\parallel v\parallel =\sqrt{2}$\|v\|=\sqrt2 なので、非零ひれい特異値とくいちsingular valueは $\sqrt{10}$\sqrt{10} である。したがって

である。$B{B}^{+}$BB^+ は $\mathrm{span}\left(u\right)$\operatorname{span}(u) への直交射影ちょっこうしゃえいorthogonal projectionであり、$B^{+}B$B^+B は $\mathrm{span}\left(v\right)$\operatorname{span}(v) への直交射影ちょっこうしゃえいorthogonal projectionである。

5.2解説かいせつ

擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは、潰つぶれていない方向ほうこうだけを逆向ぎゃくむきに戻もどす。$B{B}^{+}$BB^+ と $B^{+}B$B^+B は恒等変換こうとうへんかんidentity transformationではなく、残のこっている情報じょうほうの空間くうかんへの射影しゃえいprojectionである。

5Problem 4

For

use the nonzero singular value特異値とくいち to find $B^{+}$B^+, and explain what $B{B}^{+}$BB^+ and $B^{+}B$B^+B project onto.

5.1Answer example

Write $B=u{v}^T$B=uv^T, where

Since $\parallel u\parallel =\sqrt{5}$\|u\|=\sqrt5 and $\parallel v\parallel =\sqrt{2}$\|v\|=\sqrt2, the nonzero singular value is $\sqrt{10}$\sqrt{10}. Therefore

$B{B}^{+}$BB^+ is the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{span}\left(u\right)$\operatorname{span}(u), and $B^{+}B$B^+B is the orthogonal projection onto $\mathrm{span}\left(v\right)$\operatorname{span}(v).

5.2Explanation

The pseudoinverse擬似逆行列ぎじぎゃくぎょうれつ reverses only directions that were not collapsed. $B{B}^{+}$BB^+ and $B^{+}B$B^+B are not identity transformations; they are projections射影しゃえい onto the spaces where information remains.

6問題もんだい 5

について、$A^{+}$A^+ を使つかって最小二乗解さいしょうにじょうかいleast-squares solutionを求もとめよ。

6.1解答例かいとうれい

なので、

である。近似きんじベクトルは $Ax=(1,1{)}^T$Ax=(1,1)^T、残差ざんさresidualは

である。$A^{T}r=0$A^Tr=0 なので、残差ざんさresidualは列空間れつくうかんcolumn spaceに直交ちょっこうorthogonalする。

6.2解説かいせつ

過剰決定系かじょうけっていけいoverdetermined systemでは、$Ax=b$Ax=b が厳密げんみつには解とけない場合ばあいがある。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは、列空間れつくうかんcolumn spaceへの射影しゃえいprojectionに対応たいおうする最小二乗解さいしょうにじょうかいleast-squares solutionを返かえす。

6Problem 5

For

use $A^{+}$A^+ to find the least-squares solution最小二乗解さいしょうにじょうかい.

6.1Answer example

so $x=A^{+}b=1$x=A^+b=1. The approximating vector is $Ax=(1,1{)}^T$Ax=(1,1)^T, and the residual残差ざんさ is

Since $A^{T}r=0$A^Tr=0, the residual is orthogonal直交ちょっこう to the column space列空間れつくうかん.

6.2Explanation

In an overdetermined system過剰決定系かじょうけっていけい, $Ax=b$Ax=b may have no exact solution. The pseudoinverse returns the least-squares solution corresponding to projection onto the column space.

7問題もんだい 6

について、$Ax=b$Ax=b の解かいsolutionが無限むげんにあることを確認かくにんし、$A^{+}b$A^+b が最小さいしょうノルム解かいminimum-norm solutionになることを説明せつめいせよ。

7.1解答例かいとうれい

なので、

である。$Ax=b$Ax=b は $x_1+x_2=2$x_1+x_2=2 なので、一般解いっぱんかいは

である。この解かいの長ながさの二乗にじょうは

なので、$t=1$t=1 のとき最小さいしょうになる。

7.2解説かいせつ

劣決定系れつけっていけいunderdetermined systemでは、解かいが無限むげんに存在そんざいする場合ばあいがある。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは、その中なかから長ながさが最小さいしょうの解かいを選えらぶ。

7Problem 6

For

confirm that $Ax=b$Ax=b has infinitely many solutions解かい, and explain why $A^{+}b$A^+b is the minimum-norm solution最小ノルム解.

7.1Answer example

so

The equation $Ax=b$Ax=b is $x_1+x_2=2$x_1+x_2=2, so

The squared norm is

which is minimized at $t=1$t=1.

7.2Explanation

In an underdetermined system劣決定系れつけっていけい, there may be infinitely many solutions. The pseudoinverse chooses the one of minimum length.

8問題もんだい 7

について、$C^{*}C$C^*C を計算けいさんし、特異値とくいちsingular valueを求もとめよ。

8.1解答例かいとうれい

なので

である。この行列ぎょうれつmatrixの固有値こゆうちeigenvalueは $2,0$2,0 である。したがって $C$C の特異値とくいちsingular valueは

である。

8.2解説かいせつ

複素行列ふくそぎょうれつcomplex matrixでは $A^{T}A$A^TA ではなく $A^{*}A$A^*A を使つかう。共役転置きょうやくてんちconjugate transposeを使つかうことで、$A^{*}A$A^*A はエルミート行列ぎょうれつHermitian matrixかつ非負定値ひふていちpositive semidefiniteになる。

8Problem 7

For

compute $C^{*}C$C^*C and find the singular values特異値とくいち.

8.1Answer example

so

The eigenvalues固有値こゆうち of this matrix are $2,0$2,0. Therefore the singular values of $C$C are

8.2Explanation

For a complex matrix複素行列ふくそぎょうれつ, use $A^{*}A$A^*A rather than $A^{T}A$A^TA. The conjugate transpose共役転置きょうやくてんち makes $A^{*}A$A^*A Hermitianエルミート行列ぎょうれつ and positive semidefinite非負定値ひふていち.

9関連演習かんれんえんしゅう

9Related exercises

10関連講義かんれんこうぎ

10Related lectures

11補強問題ほきょうもんだい：擬似逆行列ぎじぎゃくぎょうれつpseudoinverseの射影性しゃえいせいと最小性さいしょうせい

11.1問題もんだい 8

$A=U_r{\mathrm{\Sigma }}_r{V}_{r^T}$A=U_r\Sigma_rV_r^T を、正せいの対角成分たいかくせいぶん ${\sigma }_1,\dots ,{\sigma }_r$\sigma_1,\ldots,\sigma_r をもつコンパクトSVDcompact SVDとする。

と定義ていぎするとき、$A{A}^{+}$AA^+ が $\mathrm{Im}A$\operatorname{Im}A への直交射影ちょっこうしゃえいorthogonal projectionであり、$A^{+}A$A^+A が $(\ker A{)}^{\perp }$(\ker A)^\perp への直交射影ちょっこうしゃえいorthogonal projectionであることを示しめせ。

11.2解答例かいとうれい

$U_{r^T}{U}_r=I$U_r^TU_r=I、$V_{r^T}{V}_r=I$V_r^TV_r=I を使つかうと、

である。$U_r$U_r の列れつは $\mathrm{Im}A$\operatorname{Im}A の正規直交基底せいきちょっこうきていなので、$U_r{U}_{r^T}$U_rU_r^T は $\mathrm{Im}A$\operatorname{Im}A への直交射影ちょっこうしゃえいorthogonal projectionである。同様どうように、

である。$V_r$V_r の列れつは 0 でない特異値とくいちsingular valueをもつ入力方向にゅうりょくほうこう、すなわち $(\ker A{)}^{\perp }$(\ker A)^\perp を張はる。したがって $A^{+}A$A^+A は $(\ker A{)}^{\perp }$(\ker A)^\perp への直交射影ちょっこうしゃえいorthogonal projectionである。

11.3解説かいせつ

この定理ていりは、擬似逆行列ぎじぎゃくぎょうれつpseudoinverseが一般いっぱんには両側逆りょうがわぎゃくではない理由りゆうを説明せつめいする。潰つぶれていない方向ほうこうでは逆ぎゃくとして働はたらき、全体ぜんたいでは射影しゃえいprojectionになる。

11.4問題もんだい 9

について、$A^{+}b$A^+b を求もとめ、最小二乗解さいしょうにじょうかいleast-squares solutionをすべて記述きじゅつし、その中なかの最小さいしょうノルム解かいminimum-norm solutionを特定とくていせよ。

11.5解答例かいとうれい

ここでは

なので、

である。$Ax=(2x_1,0{)}^T$Ax=(2x_1,0)^T が $b=(4,3{)}^T$b=(4,3)^T に最もっとも近ちかくなるには $2x_1=4$2x_1=4、すなわち $x_1=2$x_1=2 であればよい。$x_2$x_2 は $Ax$Ax に影響えいきょうしないので、最小二乗解さいしょうにじょうかいleast-squares solutionは

である。この長ながさの二乗にじょうは $\parallel x{\parallel }^2=4+t^2$\|x\|^2=4+t^2 なので、$t=0$t=0 で最小さいしょうになる。したがって $A^{+}b=(2,0{)}^T$A^+b=(2,0)^T が最小さいしょうノルム解かいminimum-norm solutionである。

11.6解説かいせつ

第だい 2 成分せいぶんの誤差ごさは列空間れつくうかんcolumn spaceでは消けせない。擬似逆行列ぎじぎゃくぎょうれつpseudoinverseは合あわせられる成分せいぶんを合あわせ、核かくkernelの成分せいぶんを 0 にしてノルムを最小さいしょうにする。

11.7問題もんだい 10

問題もんだい 9 の $A$A について、つぎの Penrose 条件じょうけんを確認かくにんせよ。

11.8解答例かいとうれい

なので、

であり、

である。また $\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$\begin{pmatrix}1&0\\0&0\end{pmatrix} は対称行列たいしょうぎょうれつsymmetric matrixなので、2 つの転置条件てんちじょうけんも成立せいりつする。

11.9解説かいせつ

Penrose 条件じょうけんは Moore-Penrose の擬似逆行列ぎじぎゃくぎょうれつpseudoinverseを特徴付とくちょうづける条件じょうけんである。この対角例たいかくれいでは、残のこる方向ほうこうだけを保たもち、潰つぶれた方向ほうこうは 0 のままにすることとして読よめる。

11Supplementary proof and application problems

11.1Problem 8

Let $A=U_r{\mathrm{\Sigma }}_r{V}_{r^T}$A=U_r\Sigma_rV_r^T be a compact SVD with positive diagonal entries ${\sigma }_1,\dots ,{\sigma }_r$\sigma_1,\ldots,\sigma_r. Define

Show that $A{A}^{+}$AA^+ is the orthogonal projection直交射影ちょっこうしゃえい onto $\mathrm{Im}A$\operatorname{Im}A and that $A^{+}A$A^+A is the orthogonal projection onto $(\ker A{)}^{\perp }$(\ker A)^\perp.

11.2Answer example

Using $U_{r^T}{U}_r=I$U_r^TU_r=I and $V_{r^T}{V}_r=I$V_r^TV_r=I,

The columns of $U_r$U_r form an orthonormal basis of $\mathrm{Im}A$\operatorname{Im}A, so $U_r{U}_{r^T}$U_rU_r^T is the orthogonal projection onto $\mathrm{Im}A$\operatorname{Im}A. Similarly,

The columns of $V_r$V_r span the input directions with nonzero singular values, namely $(\ker A{)}^{\perp }$(\ker A)^\perp. Hence $A^{+}A$A^+A is the orthogonal projection onto $(\ker A{)}^{\perp }$(\ker A)^\perp.

11.3Explanation

This theorem explains why the pseudoinverse is not a two-sided inverse in general. It becomes an inverse only on directions that survive and becomes a projection on the whole space.

11.4Problem 9

For

find $A^{+}b$A^+b, describe all least-squares solutions, and identify the minimum-norm one.

11.5Answer example

Here

so

The vector $Ax=(2x_1,0{)}^T$Ax=(2x_1,0)^T is closest to $b=(4,3{)}^T$b=(4,3)^T when $2x_1=4$2x_1=4, so $x_1=2$x_1=2. The second variable does not affect $Ax$Ax, so all least-squares solutions are

The norm $\parallel x{\parallel }^2=4+t^2$\|x\|^2=4+t^2 is minimized at $t=0$t=0, so $A^{+}b=(2,0{)}^T$A^+b=(2,0)^T is the minimum-norm least-squares solution.

11.6Explanation

The column-space error in the second coordinate cannot be removed. The pseudoinverse fixes the part that can be fitted and sets the kernel component to 0 to minimize the norm.

11.7Problem 10

For the matrix in Problem 9, verify the four Penrose equations

11.8Answer example

Since

we have

and

The matrix $\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$\begin{pmatrix}1&0\\0&0\end{pmatrix} is symmetric, so both transpose conditions also hold.

11.9Explanation

The Penrose equations are a compact way to characterize the Moore-Penrose pseudoinverse. In this diagonal example, they reduce to the statement that surviving directions are kept and collapsed directions remain zero.