logo

完全な特異値分解の存在証明 📂行列代数

完全な特異値分解の存在証明

概要

固有値の対角化 は正方行列であるという制限があったが、特異値分解 (SVD) にはそのような制約はなかった。

このような便利な分解法が全ての行列に通用するか、つまり分解の存在を明らかにすることは非常に重要な問題だと言える。

定理

３つの自然数 m≥n≥r=rankAm \ge n \ge r = \text{rank} A に対して、行列 A∈Rm×nA \in \mathbb{R}^{m \times n} はSVDを持つ。

証明

任意のベクトル x≠0\mathbf{x} \ne \mathbb{0} に対して xTATAx=∣∣Ax∣∣2>0\mathbf{x}^{T} A^{T} A \mathbf{x} = || A \mathbf{x} || ^2 > 0 であるから、ATAA^{T} A の固有値 σi2\sigma_{i}^{2} は i≤ri \le r において正、i>ri > r において 00 である。便宜のため σ1≥σ2≥⋯≥σr>0=σr+1=⋯=σn \sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{r}>0 = \sigma_{r+1} = \cdots = \sigma_{n} と置き、対角行列 S:=diag(σ1,σ2,⋯ ,σr)S := \text{diag} ( \sigma_{1} , \sigma_{2} , \cdots , \sigma_{r}) を定義する。互いに直交正規である v1,v2,⋯ ,vn\mathbf{v}_{1} , \mathbf{v}_{2} , \cdots , \mathbf{v}_{n} がそれぞれ σ1,σ2,⋯ ,σn\sigma_{1} , \sigma_{2} , \cdots , \sigma_{n} に対応するとすると ATAvi=σi2vi A^{T} A \mathbf{v}_{i} = \sigma_{i}^2 \mathbf{v}_{i} 次に V1:=[v1v2⋯vr]V2:=[vr+1vr+2⋯vn] V_1 := \begin{bmatrix} \mathbf{v}_{1} & \mathbf{v}_{2} & \cdots & \mathbf{v}_{r} \end{bmatrix} \\ V_2 := \begin{bmatrix} \mathbf{v}_{r+1} & \mathbf{v}_{r+2} & \cdots & \mathbf{v}_{n} \end{bmatrix} を構成すると V:=[V1V2] V := \begin{bmatrix} V_{1} & V_{2} \end{bmatrix} は直交行列である。V1V_{1} に対して ATAV1=V1S2A^{T} A V_{1} = V_{1} S^2 であり、双方に V1TV_{1}^{T} を掛けると V1TATAV1=V1TV1S2=S2 V_{1}^{T} A^{T} A V_{1} = V_{1}^{T} V_{1} S^2 = S^2 ここで U1:=AV1S−1U_{1} : = A V_{1} S^{-1} とすると U1TAV1=(AV1S−1)TAV1=S−1(AV1)TAV1=S−1⋅S2=S U_{1}^{T} A V_{1} = ( A V_{1} S^{-1} )^{T} A V_{1} = S^{-1} (A V_{1})^{T} A V_{1} = S^{-1} \cdot S^2 = S V2V_{2} に対して σr+1=⋯=σn=0\sigma_{r+1} = \cdots = \sigma_{n} = 0 であるから ATAV2=V2O=0 A^{T} A V_{2} = V_{2} O = \mathbb{0} であり、双方に V2TV_{2}^{T} を掛けると V2TATAV2=∥AV2∥2=0 V_{2}^{T} A^{T} A V_{2} = \| A V_{2} \|^2 = 0

これで U:=[U1U2] U : = \begin{bmatrix} U_{1} & U_{2} \end{bmatrix} が直交行列になるように U2U_{2} を定義すると U2TU1=0U_{2}^{T} U_{1} = 0 であり、AV1=U1SAV_{1} = U_{1} S の双方に U2TU_{2}^{T} を掛けると U2TAV1=U2TU1S=0 U_{2}^{T} AV_{1} = U_{2}^{T} U_{1} S = 0 一方 U1TU1=(AV1S−1)T(AV1S−1)=SV1TATAVS−1=I U_{1}^{T} U_{1} = ( A V_{1} S^{-1} ) ^{T} ( A V_{1} S^{-1} ) = S V_{1}^{T} A^{T} A V S^{-1} = I であるから U1∈Rm×rU_{1} \in \mathbb{R}^{m \times r} は直交正規ベクトルで構成されている。しかし U1U_{1} が直交行列であることを示したわけではないので U1U1T=IU_{1} U_{1}^{T} = I は分からず、AV1=U1SA V_{1} = U_{1} S をする必要があるのは次のとおり。 UTAV1=[U1TU2T]AV1=[U1TAV1U2TAV1]=[SO]  ⟺  AV1=U[SO]=[U1U2][SO]=U1S \begin{align*} && U^{T} A V_{1} = \begin{bmatrix} U_{1}^{T} \\ U_{2}^{T} \end{bmatrix} A V_{1} = \begin{bmatrix} U_{1}^{T} A V_{1} \\ U_{2}^{T} A V_{1} \end{bmatrix} = \begin{bmatrix} S \\ O \end{bmatrix} \\ \iff & AV_{1} = U \begin{bmatrix} S \\ O \end{bmatrix} = \begin{bmatrix} U_{1} & U_{2} \end{bmatrix} \begin{bmatrix} S \\ O \end{bmatrix} = U_{1} S \end{align*}

最後に Σ:=[SOOO]∈Rm×m\Sigma : = \begin{bmatrix} S & O \\ O & O \end{bmatrix} \in \mathbb{R}^{m \times m} を定義すると、 AV=A[V1V2]=[AV1AV2]=[U1SO]=[U1U2][SOOO]=UΣ \begin{align*} AV =& A \begin{bmatrix} V_{1} & V_{2} \end{bmatrix} \\ =& \begin{bmatrix} A V_{1} & A V_{2} \end{bmatrix} \\ =& \begin{bmatrix} U_{1} S & O \end{bmatrix} \\ =& \begin{bmatrix} U_{1} & U_{2} \end{bmatrix} \begin{bmatrix} S & O \\ O & O \end{bmatrix} \\ =& U \Sigma \end{align*} 結果として A=UΣVT=U1SV1TA = U \Sigma V^{T} = U_{1} S V_{1}^{T}、すなわちSVDを得る。

■

一般化

定理の条件は A∈Rm×nA \in \mathbb{R}^{m \times n} だが、実際には A∈Cm×nA \in \mathbb{C}^{m \times n} に一般化可能である。