線形代数 – 低ランク近似

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

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

・個別に記載がない場合、\(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\)とします。

・特異値分解によって得られる特異値は大きさの順に並べます。つまり、
$$\sigma_1 \ge \sigma_2 \ge \cdots \sigma_{\mathrm{min}(m,n)}\ge 0$$

とします。

・どの行列の特異値であるかを明示するため、\(A\)の\(i\)番目の特異値を\(\sigma_i(A)\)のように関数として表す場合があります。

・\(A\)の特異値分解を以下のように定義します。
\begin{align}
A&=\sum_{i=1}^{\mathrm{min}(m,n)} \sigma_i \boldsymbol{u}_i\boldsymbol{v}_i^T\\
\end{align}

・\(A\)の特異値が大きい順に並べ\(k\)番目までを残して得られる行列を\(A_k\)（下記）とします。
\begin{align}
A_k&=\sum_{i=1}^k \sigma_i \boldsymbol{u}_i\boldsymbol{v}_i^T\\
\end{align}

エッカート-ヤング-ミルスキーの定理

証明

\(p=\mathrm{min}(m,n)\)とする。

次元定理より、

$$\mathrm{dim}(\mathrm{N}(B))=p-k$$

行列のランクと列空間の次元は同じであるので、

\(V\)の第\(1\)列から第\(k+1\)列を残した行列を\(V_{k+1}\)とすると、

$$\mathrm{dim}(\mathrm{C}(V_{k+1}))=k+1$$

両者の和と\(\mathbb{R}^p\)の次元の関係は、

\begin{align}
\mathrm{dim}(\mathrm{N}(B))+\mathrm{dim}(\mathrm{C}(V_{k+1}))&=p-k+k+1=p+1\\
&\ge \mathrm{dim}(\mathbb{R}^p)
\end{align}

かつ、

\begin{align}
\mathrm{N}(B),\ \mathrm{C}(V_{k+1})& \subset \mathbb{R}^p
\end{align}

であるので、

$$\mathrm{N}(B)\ne\emptyset $$

したがって、

$$\boldsymbol{x}\in \mathrm{N}(B)\cap\mathrm{C}(V_{k+1}),\ \ \|\boldsymbol{x}\|_2=1$$

となる\(\boldsymbol{x}\)が存在する。

行列のノルムの劣乗法性により、

\begin{align}
\|A-B\|_2^2 &= \|(A-B)\|_2^2 \|\boldsymbol{x}\|_2^2 \\ &\ge \|(A-B)\boldsymbol{x}\|_2^2
\end{align}

\(\boldsymbol{x} \in \mathrm{N}(B)\)より\(B\boldsymbol{x}=\boldsymbol{0}\)であるので、

\begin{align}
\|(A-B)\boldsymbol{x}\|_2^2=\|A\boldsymbol{x}\|_2^2
\end{align}

\(U\)は直交行列なので、

\begin{align}
\|A\boldsymbol{x}\|_2^2
&=(A\boldsymbol{x})^T (A \boldsymbol{x})\\
&=\boldsymbol{x}^T A^T A \boldsymbol{x}\\
&=\boldsymbol{x}^T V \Sigma^T U^T U \Sigma V^T \boldsymbol{x}\\
&=\boldsymbol{x}^T V \Sigma^T \Sigma V^T \boldsymbol{x}\\
\end{align}

\(V\)の列ベクトルは互いに直交し、かつ\(\boldsymbol{x} \in \mathrm{C}(V_{k+1})\)であるので、\(i \gt k+1\)において、

$$\boldsymbol{v}_i^T \boldsymbol{x} = 0$$

したがって、

\begin{align}
\boldsymbol{x}^T V \Sigma^T \Sigma V^T \boldsymbol{x}&=\sum_{i=1}^{k+1} \sigma_i^2 (\boldsymbol{v}_i^T \boldsymbol{x})^2\\
\end{align}

\(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_{k+1}\)より、

\begin{align}
\sum_{i=1}^{k+1} \sigma_i^2 (\boldsymbol{v}_i^T \boldsymbol{x})^2
&\ge \sigma_{k+1}^2 \sum_{i=1}^{k+1} (\boldsymbol{v}_i^T \boldsymbol{x})^2\\
\end{align}

\(\boldsymbol{x}\in \mathrm{C}(V_{k+1})\)より、

\begin{align}
\boldsymbol{x}=\sum_{j=1}^{k+1} c_{j} \boldsymbol{v}_j
\end{align}

と表すことができるので、

$$\boldsymbol{v}_i^T \boldsymbol{v}_j =
\begin{cases}
1 & \text{if } i=j \\
0 & \text{if } i\neq j
\end{cases}$$

より、

\begin{align}
(\boldsymbol{v}_i^T\boldsymbol{x})^2
&=\left(\sum_{j=1}^{k+1} c_{j} \boldsymbol{v}_i^T \boldsymbol{v}_j \right)^2\\
&=c_{i}^2(\boldsymbol{v}_i^T \boldsymbol{v}_i)^2\\
&=c_{i}^2
\end{align}

したがって、

\begin{align}
\sigma_{k+1}^2 \sum_{i=1}^{k+1} (\boldsymbol{v}_i^T \boldsymbol{x})^2 \!&=\!\sigma_{k+1}^2 \sum_{i=1}^{k+1}c_i^2\\
&=\sigma_{k+1}^2
\end{align}

\(A-A_k\)の特異値のうち最大のものは\(\sigma_{k+1}\)なので、

\begin{align}
\sigma_{k+1}^2
&=\|A-A_k\|_2^2
\end{align}

まとめると、

\begin{align}
\|A-B\|_2^2 &\ge \|(A-B)\boldsymbol{x}\|_2^2\\
&=\|A\boldsymbol{x}\|_2^2\\
&=\boldsymbol{x}^T V \Sigma^T \Sigma V^T \boldsymbol{x}\\
&=\sum_{i=1}^{k+1} \sigma_i^2 \|\boldsymbol{v}_i^T \boldsymbol{x}\|_2^2\\
&\ge \sigma_{k+1}^2\\
&=\|A-A_k\|_2^2
\end{align}

以上より、

$$\|A-A_k\|_2\le \|A-B\|_2$$

■

証明

\(p=\mathrm{min}(m,n)\)とする。

\(A=\tilde{A}+\hat{A}\)となるよう\(\tilde{A},\ \hat{A}\)を定義し、\(A\)の左特異ベクトル、右特異ベクトルを\(\boldsymbol{u}_l,\ \boldsymbol{v}_l,\ \)\(\tilde{A}\)の左特異ベクトル、右特異ベクトルを\( \boldsymbol{\tilde{u}}_l,\ \boldsymbol{\tilde{v}}_l,\ \)\(\hat{A}\)の左特異ベクトル、右特異ベクトルを\( \boldsymbol{\hat{u}}_l,\ \boldsymbol{\hat{v}}_l\)とする。

以下のように\(\tilde{A}\)の\(i\)番目の特異値と\(\tilde{A}-\tilde{A}_{i-1}\)の\(1\)番目の特異値は同じである。

\begin{align}
\sigma_i(\tilde{A})&=\sigma_i\left(\sum_{l=i}^p \sigma_l \boldsymbol{\tilde{u}}_l \boldsymbol{\tilde{v}}_l \right)\\
&=\sigma_1\left(\sum_{l=1}^p \sigma_l \boldsymbol{\tilde{u}}_l \boldsymbol{\tilde{v}}_l – \sum_{l=1}^{i-1} \sigma_l \boldsymbol{\tilde{u}}_l \boldsymbol{\tilde{v}}_l\right)\\
&=\sigma_1(\tilde{A}-\tilde{A}_{i-1})
\end{align}

同様に、

\begin{align}
\sigma_j(\hat{A})&=\sigma_j\left(\sum_{l=j}^p \sigma_l \boldsymbol{\hat{u}}_l \boldsymbol{\hat{v}}_l \right)\\
&=\sigma_1\left(\sum_{l=1}^p \sigma_l \boldsymbol{\hat{u}}_l \boldsymbol{\hat{v}}_l – \sum_{l=1}^{j-1} \sigma_l \boldsymbol{\hat{u}}_l \boldsymbol{\hat{v}}_l\right)\\
&=\sigma_1(\hat{A}-\hat{A}_{j-1})
\end{align}

行列のノルムの劣加法性により、

\begin{align}
\sigma_i(\tilde{A})\!\!+\!\!\sigma_j(\hat{A}) \!\!&=\!\! \normalsize {\sigma_1(\tilde{A}\!\!-\!\!\tilde{A}_{i-1})\!\!+\!\!\sigma_1(\hat{A}\!\!-\!\!\hat{A}_{j-1}) }\\&\normalsize{\ge \sigma_1(\tilde{A}\!\!+\!\!\hat{A}\!\!-\!\!\tilde{A}_{i-1}\!\!-\!\!\hat{A}_{j-1}) }\\
&\normalsize{\!= \sigma_1(A\!\!-\!\!\tilde{A}_{i-1}\!\!-\!\!\hat{A}_{j-1}) }
\end{align}

ランクの劣加法性により、

\begin{align}
\mathrm{rank}(\!\tilde{A}_{i-1}\!\!+\!\!\hat{A}_{j-1}\!)\! &\!\le \!\!\mathrm{rank}(\!\tilde{A}_{i-1}\!)\!\!+\!\!\mathrm{rank}(\!\hat{A}_{j-1}\!)\\
&=i+j-2
\end{align}

であるので\(\tilde{A}_{i-1}+\hat{A}_{j-1}\)の特異値の数は多くても\(i+j-2\)。\(\ \ \ ※1\)

\(\tilde{A}-\tilde{A}_{i-1}-\hat{A}_{j-1}\)の特異値は\(\hat{A}\)の特異値の\(1\)番目より、最も多くて\(i+j-2\)番目までを除いたものなので、

\begin{align}
\sigma_1(A\!-\!\tilde{A}_{i-1}\!-\!\hat{A}_{j-1}) \!&\ge\! \sigma_1\!\left(\sum_{l=i+j-1}^p \sigma_l \boldsymbol{u}_l \boldsymbol{v}_l\right)\\
&=\sigma_{i+j-1}(A)\\
\end{align}

以上より、

\begin{align}
\sigma_i(\tilde{A})\!\!+\!\!\sigma_j(\hat{A}) \!\!&=\!\! \normalsize {\sigma_1(\tilde{A}\!\!-\!\!\tilde{A}_{i-1})\!\!+\!\!\sigma_1(\hat{A}\!\!-\!\!\hat{A}_{j-1}) }\\&\normalsize{\ge \sigma_1(\tilde{A}\!\!+\!\!\hat{A}\!\!-\!\!\tilde{A}_{i-1}\!\!-\!\!\hat{A}_{j-1}) }\\
&\normalsize{\!= \sigma_1(A\!\!-\!\!\tilde{A}_{i-1}\!\!-\!\!\hat{A}_{j-1}) }\\
&\ge \sigma_{i+j-1}(A)
\end{align}

\(\tilde{A}=A-B,\ \hat{A}=B\)とすると、\(\sigma_{k+1}(B)=0\)より、\(i \ge 0,\ j=k+1\)において、

$$\sigma_i(A-B) \ge \sigma_{k+i}(A)$$

フロベニウス・ノルムを比較すると、

\begin{align}
\|A-B\|_F^2&=\sum_{l=1}^{p}\sigma_l^2(A-B)\\
&\ge \sum_{l=k+1}^{p} \sigma_l^2(A) \\
&= \|A-A_k\|_F^2
\end{align}

したがって、

\begin{align}
\|A-A_k\|_F\ge \|A-B\|_F
\end{align}

■

\(※1\ \ \)行列のランクと特異値の数は同じ（特異値分解の性質）という性質があります。

定理の低ランク近似への適用

以上、2-ノルムの場合とフロベニウス・ノルムの場合のエッカート-ヤングの定理（エッカート-ヤング-ミルスキーの定理）について述べました。これらが低ランク近似とどのような関係があるのかを考えましょう。

エッカート-ヤング（-ミルスキー）の定理と低ランク近似の関係

低ランク近似とは、与えられた行列を誤差の小さい別の行列で表すことです。

\(2\)つの行列の誤差とは何でしょう。

その\(1\)つの考え方が2-ノルムで、両者の差の行列を特異値分解しその最も大きい特異値で表すことです。

もう\(1\)つの考え方がフロベニウス・ノルムで、両者の差を行列とし、その全ての成分を\(2\)乗し、和の平方根を誤差とすることです。

定理1, 2どちらも、ランク\(k\)の行列のうち最も\(A\)との誤差が小さくなるのは\(A_k\)であることを示しています。

\(A_k\)の定義

\(A_k\)の定義は以下でした。

\begin{align}
A_k&=\sum_{i=1}^k \sigma_i \boldsymbol{u}_i\boldsymbol{v}_i^T\\
\end{align}

これは、\(A\)特異値の数は最大で\(\mathrm{min}(m,n)\)あるところ、\(k\)個だけを残し、左特異ベクトル・右特異ベクトルも対応するものだけが残ることを意味しています。

ただし、\(\sigma_1\ge \sigma_2\ge \cdots \ge \sigma_{\mathrm{min}(m,n)}\)とする点に注意ください。つまり残す特異値は何でもよいわけではなく、最も大きい値のものから\(k\)番目のものまでで、それより小さいものを除外します。

低ランク行列による近似

\(A_k\)で近似する目的にはいくつかありますが、情報量の削減がその一つです。

もちろん\(A\)と\(A_k\)の成分の数は同じです。

しかし、特異値分解にすれば、\(k \ll \mathrm{min}(m,n)\)の場合は\(U_k,\ \Sigma_k,\ V_k\)の成分の数を合わせても\(A\)の成分の数より少なく、データ処理のうえで様々な利点があります。

ランクと特異値の数の関係

低ランク近似とは名の通り低いランクによって近似することですが、\(A\)のランクと正である特異値の数は同じ（特異値分解の性質）なので、これは特異値の数を限定することを意味しています。

低ランク近似の例

低ランク近似により画像を圧縮してみます。

元の画像の解像度は\(600\times 1,000\)です。この画像の各ピクセルが\(A\)の成分であるとします。

以下、元画像と\(k\)を変えて低ランク近似を適用した結果です。

元画像

$$k=100$$

$$k=50$$

$$k=25$$

\(k\)を小さくすればするほど画像は粗くなりますが、データのサイズは小さくなります。このサイズを比較しましょう。

元の画像のピクセル数は、\(m\cdot n\)です。

低ランク近似によって生じるデータの数は、\(U_k,\ \Sigma_k,\ V_k\)の順に足すと、\(m\cdot k+ k+ k\cdot n\)です。

元の画像をBMPとして圧縮率と削減率を計算すると、

\[
\begin{array}{|c|c|c|}
\hline
\text{ランク } k & \text{圧縮率} & \text{削減率} \\
\hline
100 & 26.7\% & 73.3\% \\
50 & 13.3\% & 86.7\% \\
25 & 6.7\% & 93.3\% \\
\hline
\end{array}
\]

となります。静止画の圧縮にはJPEGなどが一般的に用いられますが、低ランク近似でも同様の効果があることがわかります。