線形代数 – 特異値分解の性質

\(※\ \ \)本ページの記載内容に関し、以下注意ください。

・\(A,\ U,\ V\)を実行列として述べます。複素行列の場合も同様の性質がありますが、それらについては転置行列を随伴行列に、直交行列をユニタリ行列に置き換えてください。

・長方行列であっても\((1,1),(2,2),\cdots \)以外の成分がすべて\(0\)である場合、これを対角行列とよぶことにします。

・個別に記載がない場合、\(A\in \mathbb{R}^{m\times n},\ U\in \mathbb{R}^{m\times m},\ \Sigma \in \mathbb{R}^{m\times n},\ V\in \mathbb{R}^{n\times n},\ \)特異値分解を\(A=U\Sigma V^T,\ U\)の第\(i\)列を\(\boldsymbol{u}_i,\ \Sigma\)の\((i,i)\)成分を\(\sigma_i,\ V\)の第\(i\)列を\(\boldsymbol{v}_i\)とします（添え字の範囲は都度指定します）。

・定理2の通り、特異値は全て非負の実数であるので、「特異値は正である」とした場合は「特異値は\(0\)でない」と同じ意味です。

証明

\(A=U\Sigma V^T\)の両辺に左から\(U^T\)を掛けて転置すると、

\begin{align}
(U^TA)^T&=(U^T U \Sigma V^T)^T\\
A^T U&=V\Sigma^T
\end{align}

両辺の第\(i\)列は、

$$A^T\boldsymbol{u}_i=\sigma_i \boldsymbol{v}_i$$

\(A=U\Sigma V^T\)の両辺に両辺に右から\(V\)を掛けると、
\begin{align}
A V &= U \Sigma V^TV\\
AV &= U\Sigma\\
\end{align}

両辺の第\(i\)列は、

$$A\boldsymbol{v}_i=\sigma_i \boldsymbol{u}_i$$

■

証明

\(m\gt n\)の場合、

$$A A^T \boldsymbol{u}_i=\boldsymbol{0} \ \ \ \ ※1$$

両辺に左から\(\boldsymbol{u}_i^T\)を掛けて、

$$\boldsymbol{u}_i^T A A^T \boldsymbol{u}_i=(A^T \boldsymbol{u}_i)^T(A^T \boldsymbol{u}_i)=0$$

したがって、

$$A^T \boldsymbol{u}_i=\boldsymbol{0}$$

\(m\lt n\)の場合、

$$A^TA \boldsymbol{v}_j=\boldsymbol{0}\ \ \ \ ※1$$

両辺に左から\(\boldsymbol{v}_j\)を掛けて、

$$\boldsymbol{v}_j^T A^T A \boldsymbol{v}_j=(A \boldsymbol{v}_j)^T(A \boldsymbol{v}_j)=0$$

したがって、

$$A \boldsymbol{v}_j=\boldsymbol{0}$$

■

補足

\(※1\ \ \)系2.2を参照ください。

証明

特異値・特異ベクトルの定義より、

\begin{align}
A A^T &=(U \Sigma V^T)(U \Sigma V^T)^T\\
&=U \Sigma V^T V \Sigma^T U^T\\
&=U \Sigma \Sigma^T U^T
\end{align}

両辺に右から\(U\)を掛けて、

$$AA^T U = U \Sigma \Sigma^T U^T U= U \Sigma \Sigma^T$$

両辺の第\(i\)列は、

$$AA^T \boldsymbol{u}_i=\sigma_i ^2 \boldsymbol{u}_i$$

同様に、

\begin{align}
A^T A &=(U \Sigma V^T)^T(U \Sigma V^T)\\
&=V \Sigma^T U U \Sigma V^T\\
&=V \Sigma^T \Sigma V^T
\end{align}

両辺に右から\(V\)を掛けて、

$$A^TA V = V \Sigma^T \Sigma V^T V= V \Sigma^T \Sigma $$

両辺の第\(i\)列は、

$$A^T A \boldsymbol{v}_i=\sigma_i ^2 \boldsymbol{v}_i$$

■

証明

\(m\gt n\)の場合について示す。

\(\sigma_1,\ \sigma_2,\cdots,\sigma_r\)を正とする。

\(A A^T\)の固有値のうち、正であるものの数も\(r\)なので、

$$\mathrm{rank}(A A^T)=r\ \ \ ※1$$

次元定理より、

$$\mathrm{dim} (\mathrm{N}(A A^T))=m-r$$

零空間の次元が\(m-r\)であるので、\(k=r+1,\ r+2,\cdots,m\)における\(\boldsymbol{u}_k\)を零空間の直交基底として、

$$A A^T \boldsymbol{u}_k=\boldsymbol{0}$$

と表すことができる。

\(i=n+1,n+2,\cdots,m\)は\(k\)の範囲に含まれるので、

$$A A^T \boldsymbol{u}_i=\boldsymbol{0}$$

\(m \lt n\)の場合も同様。

■

補足

\(※1\ \ \)固有値・固有ベクトルの性質を参照ください。

証明1

\(A\boldsymbol{u}_1=\sigma_1\boldsymbol{v}_1\)が成立し、\(\sigma_1\)が最大かつ\(\boldsymbol{u}_1,\ \boldsymbol{v}_1\)が正規化された組み合わせを選ぶ。

さらに\(U_1=\begin{pmatrix}\boldsymbol{u_1}&\tilde{U_1}\end{pmatrix},\ \ V_1=\begin{pmatrix}\boldsymbol{v_1}&\tilde{V_1}\end{pmatrix}\)が直交行列となるよう\(\tilde{U_1},\ \tilde{V_1}\)を決める。

\(\Sigma_1 = U_1^T A V_1\)として、以下のように\(A\)から対角行列を抽出する。

前提に従い\(\Sigma_1\)を計算すると、

\begin{align}
\Sigma_1&=U_1^T A V_1\\
&=\begin{pmatrix} \boldsymbol{u}^T_1\\ \tilde{U_1}^T\end{pmatrix} A \begin{pmatrix}\boldsymbol{v}_1&\tilde{V_1}\end{pmatrix}\\
&=\begin{pmatrix}\boldsymbol{u}_1^T\\ \tilde{U_1}^T\end{pmatrix}\begin{pmatrix}\sigma_1 \boldsymbol{u}_1& A \tilde{V_1}\end{pmatrix}\\
&=\begin{pmatrix}\sigma_1 \boldsymbol{u}_1^T \boldsymbol{u}_1 & \boldsymbol{v}_1^T A \tilde{V_1}\\
\sigma_1 \tilde{U_1}^T \boldsymbol{u}_1& \tilde{U_1}^T A \tilde{V_1}\end{pmatrix}\\
&=\begin{pmatrix}\sigma_1& \boldsymbol{w}^T\\ \boldsymbol{0}& A_1\end{pmatrix}\tag{1}
\end{align}

ただし\(\boldsymbol{w} \in \mathbb{R}^{m-1},\ A_1 \in \mathbb{R}^{m-1\times n-1}\)とする。

\(U_1,\ V_1\)は直交行列であるので、

\begin{align}
\|\Sigma_1\|_2&=\|U_1^TAV_1\|_2\\
&=\|A\|_2\\
&=\sigma_1 \ \ \ \ ※1\ ※2\\
\end{align}

また、\(\boldsymbol{x}\in \mathbb{R}^n\)により、

\begin{align}
\|\Sigma_1\|_2\|\boldsymbol{x}\|_2&\ge\|\Sigma_1\boldsymbol{x}\|_2\\
\end{align}

と表されるので、

$$\boldsymbol{x}= \begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}$$

として、

\begin{align}
\|\Sigma_1\|_2^2\|\boldsymbol{x}\|_2^2&=\sigma_1^2\left\|\begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=\sigma_1^2 (\sigma_1^2 +\|\boldsymbol{w}\|_2^2)\\
&\ge \|\Sigma_1\boldsymbol{x}\|_2^2\\
&= \left\|\begin{pmatrix}\sigma_1&\boldsymbol{w}^T\\ \boldsymbol{0}&A_1\end{pmatrix} \begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=\left\| \begin{pmatrix}\sigma_1^2+\boldsymbol{w}^t\boldsymbol{w} \\ A_1\boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=(\sigma_1^2 +\|\boldsymbol{w}\|_2)^2+\|A_1\boldsymbol{w}\|_2^2\\
\end{align}

の関係が得られるが、不等式が成立するためには、

$$\boldsymbol{w}=\boldsymbol{0}$$

である必要がある。これを\((1)\)に代入し、

$$\Sigma_1=\begin{pmatrix}\sigma_1& \boldsymbol{0}\\ \boldsymbol{0}& A_1\end{pmatrix}$$

冒頭と同様に\(A_1=U_2 \Sigma_2 V_2^T\)となるよう\(U_2,\ \Sigma_2, V_2\)を選ぶと、

\begin{align}
A&=U_1 \Sigma_1 V_1^T\\
&=U_1 \begin{pmatrix}\sigma_1& \boldsymbol{0}\\ \boldsymbol{0}& A_1\end{pmatrix} V_1^T\\
&=U_1 \begin{pmatrix}\sigma_1& \boldsymbol{0}\\ \boldsymbol{0}& U_2 \Sigma_2 V_2^T \end{pmatrix} V_1^T\\
&=U_1 \!\begin{pmatrix}1 \!&\! \boldsymbol{0}\\ \boldsymbol{0} \!&\! U_2\end{pmatrix}\!
\begin{pmatrix}\sigma_1 \!&\! \boldsymbol{0}\\ \boldsymbol{0} \!&\! \Sigma_2\end{pmatrix}\! \begin{pmatrix}1 \!&\! \boldsymbol{0}\\ \boldsymbol{0} \!&\! V_2^T\end{pmatrix}V_1^T\\
\end{align}

これを繰り返し中央に残る行列を\(\Sigma\)とすると、

\(m\gt n\)の場合、

$$\Sigma=\begin{pmatrix}\mathrm{diag}(\sigma_1,\sigma_2,\cdots,\sigma_n)\\ \large{0}\end{pmatrix}$$

\(m\lt n\)の場合、

$$\Sigma=\begin{pmatrix}\mathrm{diag}(\sigma_1,\sigma_2,\cdots,\sigma_m)& \large{0}\end{pmatrix}$$

となる。

さらに直交行列どうしの積は直交行列であるので、左右の行列をまとめそれぞれ\(U,\ V^T\)とすると、これらは直交行列である。

したがって、\(A=U \Sigma V^T\)としたときの\(U,\ V\)を適当な直交行列として選ぶことにより\(\Sigma\)を対角行列とすることができる。

■

補足

\(※1\ \ \)\(\|\Sigma\|_2\)や\(\|A\|_2\)などを行列ノルム（matrix norm）または行列のノルムとよびます。

定義にはいくつかの条件がありますが、\(B,\ C\)を行列とすると、

\begin{align}
\|B\|\|C\|&\ge \|BC\|
\end{align}

であることがその一つです。

\(\|B\|_2\)を2ノルムとよび、\(B\)の固有値のうち最も大きい値のものが\(\sigma_1\)であるとき、

$$\|B\|_2=\sigma_1$$

となります。

\(P,\ Q\)を直交行列とすると、以下が成り立ちます。

$$\|PB\|_2=\|BQ\|_2=\|B\|_2$$

\(※2\ \ \)行列ノルムを使わずに以下のように\(\boldsymbol{w}=\boldsymbol{0}\)であることを示すこともできます。

*********************************************

\begin{align}
\Sigma_1^T\Sigma_1&= (UAV^T )^T(UAV^T )\\
&= V A^T U^T U A V^T \\
&= V A^T A V^T \\
\end{align}

より、\(\Sigma_1^T \Sigma_1 \)は\(A^T A\)と相似であるので\(\Sigma ^T \Sigma\)の固有値のうち最も大きいものは\(\sigma_1^2\)である。

\(\boldsymbol{x}\in \mathbb{R}^n\backslash \{ \boldsymbol{0} \} \)により、

$$\frac{\boldsymbol{x}^T \Sigma_1^T \Sigma_1 \boldsymbol{x}}{\boldsymbol{x}^T \boldsymbol{x}} \le \sigma_1^2\ \ \ \ ※3$$

と表されるので、

$$\boldsymbol{x}= \begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}$$

とすると、

\begin{align}
\sigma_1^2 \|\boldsymbol{x}\|_2^2&=\sigma_1^2 \left\|\begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=\sigma_1^2(\sigma_1^2+\|\boldsymbol{w}\|_2^2)\\
&\ge \|\Sigma_1\boldsymbol{x}\|_2^2\\
&= \left\|\begin{pmatrix}\sigma_1&\boldsymbol{w}^T\\ \boldsymbol{0}&A_1\end{pmatrix} \begin{pmatrix}\sigma_1 \\ \boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=\left\| \begin{pmatrix}\sigma_1^2+\boldsymbol{w}^t\boldsymbol{w} \\ A_1\boldsymbol{w}\end{pmatrix}\right\|_2^2\\
&=(\sigma_1^2 +\|\boldsymbol{w}\|_2^2)^2+\|A_1\boldsymbol{w}\|_2^2\\
\end{align}

の関係が得られるが、

\(\sigma_1 \gt 0\)のときは不等式が成立するためには\(\boldsymbol{w}=\boldsymbol{0}\)である必要がある。

\(\sigma_1=0\)のときは\(\boldsymbol{w}\neq \boldsymbol{0}\)では不等式は成立せず、\(\boldsymbol{w}= \boldsymbol{0}\)では\(\boldsymbol{x}=\boldsymbol{0}\)となるのでこのような制約がない。つまり、やはり\(\boldsymbol{w}=\boldsymbol{0}\)である必要がある。

したがって\(\sigma_1\)の値にかかわらず、

$$\boldsymbol{w}=\boldsymbol{0}$$

である。

*********************************************

\(※3\ \ \)末項の補題1を参照ください。

証明2

\(\Sigma\)の対角成分のうち正であるものを\(\sigma_1,\sigma_2,\cdots,\sigma_r\)、\(0\)であるものを\(\sigma_{r+1},\sigma_{r+2},\cdots,\sigma_{\mathrm{min}(m,n)}\)とする。

\(i,j=1,2,\cdots,r\)において\(A\boldsymbol{v}_i=\sigma_i\boldsymbol{u}_i\)を満たし、かつ\(\boldsymbol{v}_1,\ \boldsymbol{v}_2,\cdots,\boldsymbol{v}_r\)が互いに直交する場合の\(\boldsymbol{u}_i\)と\(\boldsymbol{u}_j\)の関係が、

\begin{align}
\langle \boldsymbol{u}_i,\ \boldsymbol{u}_j \rangle&=\boldsymbol{u}_i^T \boldsymbol{u}_j\\
&= \frac{(A \boldsymbol{v}_i)^T (A\boldsymbol{v}_j)}{\sigma_i\sigma_j}\\
&= \frac{ \boldsymbol{v}_i^T (A^T A \boldsymbol{v}_j)}{\sigma_i\sigma_j}\\
&= \frac{\boldsymbol{v}_i^T (\sigma_j^2\boldsymbol{v}_j)}{\sigma_i\sigma_j} \\
&= \frac{\sigma_j}{\sigma_i}\boldsymbol{v}_i^T \boldsymbol{v}_j \\
&=\delta_{ij}\ \ \ ※1
\end{align}

となることにより\(\boldsymbol{u}_1,\boldsymbol{u}_2,\cdots,\boldsymbol{u}_r\)は互いに直交する。また、\(A\)の列空間の基底であるので列空間の正規直交基底となるよう選ぶことができる。\(\ \ \ ※2\)

\(k=r+1,r+2,\cdots,m\)において、

$$A\boldsymbol{u}_k=\boldsymbol{0}$$

が成り立つので、\(\boldsymbol{u}_{r+1},\boldsymbol{u}_{r+2},\cdots,\boldsymbol{u}_m\)は\(A\)の左零空間の基底であるので左零空間の正規直交基底となるよう選ぶことができる。\(\ \ \ ※2\)

列空間と左零空間は直交補空間であるのでこれらの基底は全て互いに直交する。\(\ \ \ ※3\)

したがって\(\Sigma\)が対角行列、\(V\)が直交行列のとき\(A=U\Sigma V^T\)と表され、かつ直交行列である\(U\)が存在する。

補足

\(※1\ \ \)\(\delta_{ij}\)は以下の意味です。

$$\delta_{ij}=\begin{cases} 1\ \ \ i=j\\ 0\ \ \ i\neq j\\ \end{cases}$$

上の式からは直接は\(\delta_{ij}\frac{\sigma_j}{\sigma_i}\)が得られますが、これは\(i=j\)のときに成り立つので\(\delta_{ij}\)とすることができます。

\(※2\ \ \)系3および定理1.2を参照ください。

\(※3\ \ \)行空間・列空間・零空間の定義を参照ください。

証明

\(i=1,\ 2,\cdots,\mathrm{min}(m,n)\)において、

$$A\boldsymbol{v}_i=\sigma_i \boldsymbol{u}_i$$

より、

\begin{align}
\langle A\boldsymbol{v}_i,A\boldsymbol{v}_i\rangle&=\langle\sigma_i \boldsymbol{u}_i,\sigma_i \boldsymbol{u}_i\rangle\\
&=\sigma_i ^2 \langle \boldsymbol{u}_i,\boldsymbol{u}_i\rangle\\
&=\sigma_i ^2 \\
\end{align}

が成り立つので\(\sigma_i^2\)は非負の実数である。したがって\(\sigma_i\)を非負の実数とすることができる。

■

補足

\(A\)が複素行列の場合も

\begin{align}
\langle A\boldsymbol{v}_i,A\boldsymbol{v}_i\rangle&=\langle\sigma_i \boldsymbol{u}_i,\sigma_i \boldsymbol{u}_i\rangle\\
&=(\sigma_i \boldsymbol{u}_i)^* (\sigma_i \boldsymbol{u}_i)\\
&=\sigma_i^2
\end{align}

より\(\sigma_i^2\)は非負の実数なので\(\sigma_i\)を非負の実数とすることができます。

証明

\(U\)の列ベクトルの数は\(m\)で互いに直交するので、

$$\mathrm{rank}(U)=\mathrm{rank}(U^T)=m$$

同様に、

$$\mathrm{rank}(V)=\mathrm{rank}(V^T)=n$$

\(0\)である特異値を含めた数は\(\mathrm{min}(m,n)\)であり、\(0\)である特異値を除いた数は\(\mathrm{rank}(\Sigma)\)なので、

$$\mathrm{rank}(\Sigma) \le \mathrm{min}(\mathrm{rank}(U),\mathrm{rank}(V^T))$$

したがって、

\begin{align}
\mathrm{rank}(A)&=\mathrm{rank}(U\Sigma V^T)\\
&\le \mathrm{min}(\mathrm{rank}(U),\mathrm{rank}(\Sigma),\mathrm{rank}(V^T))\\
&= \mathrm{rank}(\Sigma)\ \ \ \ ※1
\end{align}

\(A\)はフルランクとは限らないので、

$$\mathrm{rank}(A) \le \mathrm{min}(\mathrm{rank}(U^T),\mathrm{rank}(V))$$

したがって、

\begin{align}
\mathrm{rank}(\Sigma)&=\mathrm{rank}(U^TU\Sigma V^TV)\\
&=\mathrm{rank}(U^T A V)\\
&\le \mathrm{min}(\mathrm{rank}(U^T),\mathrm{rank}(A),\mathrm{rank}(V))\\
&=\mathrm{rank}(A)
\end{align}

以上より、

$$\mathrm{rank}(A)=\mathrm{rank}(\Sigma)$$

\(\mathrm{rank}(\Sigma)\)は正の特異値の数であるので、これが\(\mathrm{rank}(A)\)に等しい。

■

補足

\(※1\ \ \)行列の積のランクはそれぞれのランクより大きくはならないという性質があります（下記）。

$$\mathrm{rank}(BC) \le \mathrm{min}(\mathrm{rank}(B), \mathrm{rank}(C))$$

ランク（階数）を参照ください。

\(※\ \ \)\(A\)の左零空間は\(A^T\)の零空間と同じ意味です。

証明

(i)\(i=1,\ 2,\cdots,r\)における\(\boldsymbol{u}_i\)は以下のように\(A\)の列ベクトルの線形結合で表されるので\(A\)の列空間の基底である。

$$\boldsymbol{u}_i=\frac{1}{\sigma_i} A \boldsymbol{v}_i$$

(ii)\(j=r+1,\ r+2,\cdots,m\)における\(\boldsymbol{u}_j\)は対応する特異値が\(0\)あるいは存在しないので、以下のように\(A\)の左零空間の基底である。

$$A^T\boldsymbol{u}_j=\boldsymbol{0}$$

(iii)\(i=1,\ 2,\cdots,r\)における\(\boldsymbol{v}_i\)は以下のように\(A\)の行ベクトルの線形結合で表されるので\(A\)の行空間の基底である。

$$\boldsymbol{v}_i=\frac{1}{\sigma_i} A^T \boldsymbol{u}_i$$

(iv)\(k=r+1,\ r+2,\cdots,n\)における\(\boldsymbol{v}_k\)は対応する特異値が\(0\)あるいは存在しないので、以下のように\(A\)の零空間の基底である。

$$A\boldsymbol{v}_k=\boldsymbol{0}$$

■

補足

対応する特異値が存在しないベクトルについては系1.2を参照ください。

証明

実対称行列は直交行列によって対角化可能であるのでこれを\(Q\)として、

$$B=QDQ^{-1}$$

で表し\(D\)の対角成分を\(\lambda_1,\ \lambda_2,\cdots,\lambda_n\)とする。さらに

$$\boldsymbol{x}=Q\boldsymbol{y}$$

と置き換えその成分を\(y_1,\ y_2,\cdots,y_n\)とし計算すると、

\begin{align}
\frac{\boldsymbol{x}^T B \boldsymbol{x}}{\boldsymbol{x}^T\boldsymbol{x}}
&=\frac{(Q\boldsymbol{y})^T QDQ^{-1} (Q\boldsymbol{y})}{(Q\boldsymbol{y})^T(Q\boldsymbol{y})}\\
&=\frac{\boldsymbol{y}^T Q^T QDQ^{-1} Q \boldsymbol{y}}{\boldsymbol{y}^T Q^T Q \boldsymbol{y}}\\
&=\frac{\boldsymbol{y}^T D \boldsymbol{y}}{\boldsymbol{y}^T \boldsymbol{y}}\\
&=\frac{\sum_{i=1}^n y_i \lambda_i y_i}{\sum_{i=1}^n y_i y_i}\\
&=\frac{\sum_{i=1}^n \lambda_i y_i^2}{\sum_{i=1}^n y_i^2}\\
\end{align}

最も大きい固有値を\(\lambda_{max}\)としたときに上の式が最も大きくなるのは全ての固有値が\(\lambda_{max}\)のときなので、

\begin{align}
\frac{\boldsymbol{x}^T B \boldsymbol{x}}{\boldsymbol{x}^T\boldsymbol{x}}
&\le \frac{\sum_{i=1}^n \lambda_{max} y_i^2}{\sum_{i=1}^n y_i^2}\\
&=\lambda_{max}
\end{align}

\(\lambda_{min}\)との関係についても同様。

■

補足

定理1の証明1の補足で、

$$\frac{\boldsymbol{x}^T \Sigma_1^T \Sigma_1 \boldsymbol{x}}{\boldsymbol{x}^T \boldsymbol{x}} \le \sigma_1^2$$

として説明しましたが、\(\Sigma_1^T \Sigma_1\)は実対称行列であるのでこれを\(B,\ \)\(\sigma_1^2\)を\(\lambda_{max}\)に置き換えてこの補題を適用することにより証明されます。複素行列の場合も\(\Sigma_1^* \Sigma_1\)は実対称行列なので同様です。

\(\frac{\boldsymbol{x}^T B \boldsymbol{x}}{\boldsymbol{x}^T\boldsymbol{x}}\)をレイリー商（Rayleigh quotient）とよびます。