流れに従ひて己を失はず.

日々の研究について書きます

同次連立一次方程式の非自明解を特異値分解から解く

mn列でランクrである行列 \boldsymbol{A} と,n次元のベクトル \boldsymbol{x} について,以下の等式が成立するとき,\boldsymbol{x}の非自明解(\boldsymbol{x} \neq 0)特異値分解から求める.

{\displaystyle
\boldsymbol{A}\boldsymbol{x} = 0. 
}

まず,\boldsymbol{x}は大きさが不定なので,条件として以下を加える.

{\displaystyle
\|\boldsymbol{x}\| = 1. 
}

ところで,この\boldsymbol{x}は以下の解と言いかえることができる.

{\displaystyle
\underset{\left\| x\right\| =1}{min} \left\| \boldsymbol{A}\boldsymbol{x}\right\|.     
}

また,\boldsymbol{A}特異値分解の結果を以下で表す.

{\displaystyle
 \boldsymbol{A} = \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V^{\mathrm{T}}}.   
}

図で書くとこう.
f:id:Yasutchi:20200516010800j:plain

\boldsymbol{U}はユニタリ行列であり,ユニタリ行列による変換は等長変換であることに注意して,\left\| \boldsymbol{A}\boldsymbol{x}\right\|は以下のように変形できる.

{\displaystyle
\begin{align}
 \left\| \boldsymbol{A}\boldsymbol{x}\right\| &=  \left\| \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V^{\mathrm{T}}}\boldsymbol{x}\right\| \\
&=  \left\| \boldsymbol{\Sigma}\boldsymbol{V^{\mathrm{T}}}\boldsymbol{x}\right\| \\
&=  \left\| \boldsymbol{\Sigma}\boldsymbol{y}\right\|. 
\end{align}
}

ただし,

{\displaystyle
 \boldsymbol{y} = \boldsymbol{V^{\mathrm{T}}}\boldsymbol{x},
}
としている.ここで,\boldsymbol{V}がユニタリ行列であることによる等長変換から,以下が成立.
{\displaystyle
\left\| y \right\| = \left\| \boldsymbol{V^{\mathrm{T}}}\boldsymbol{x} \right\| = \left\| x \right\| = 1.
}


以上から,

{\displaystyle
\underset{\left\| x\right\| =1}{min} \left\| \boldsymbol{A}\boldsymbol{x}\right\| = \underset{\left\| y\right\| =1}{min} \left\| \boldsymbol{\Sigma}\boldsymbol{y}\right\|.
}

ここで,\boldsymbol{A}の特異値を\sigma_1, \sigma_2,...,\sigma_rとし,\boldsymbol{y^{\mathrm{T}}} = [ y_1,y_2,...,y_n]とおくと,

{\displaystyle
 \left\| \boldsymbol{\Sigma}\boldsymbol{y} \right\| =  \sigma_1^2 y_1^2 + \sigma_2^2 y_2^2 + ... +  \sigma_r^2 y_r^2,
}
となる.

これを最小化する\boldsymbol{y} (ただし\left\| y \right\| = 1)の各成分y_i

{\displaystyle
  y_i = \left\{ \begin{array}{ll}
    0 & (i=1,2,...,r) \\
    \alpha_i & (i=r+1,r+2,...,n) \\
    &ただし,\alpha_{r+1}^2 + \alpha_{r+2}^2 +...+\alpha_n^2  = 1,
  \end{array} \right.
}
となる.

ここで,\boldsymbol{V}の各列をベクトル\boldsymbol{v_i}(i = 1,2,...,n)と表すと,\boldsymbol{V}がユニタリ行列であるから

{\displaystyle
\begin{align}
\boldsymbol{x} &= \boldsymbol{V}\boldsymbol{V^{\mathrm{T}}}\boldsymbol{x} = \boldsymbol{V}\boldsymbol{y} \\
&= \alpha_{r+1}\boldsymbol{v}_{r+1} + \alpha_{r+2}\boldsymbol{v}_{r+2} +...+\alpha_n\boldsymbol{v}_n.
\end{align}
}

参考:
https://www2.cs.duke.edu/courses/fall15/compsci527/notes/linear-systems.pdf
http://daily-tech.hatenablog.com/entry/2018/03/18/180439