エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

特異値分解による行列の低ランク近似の基礎をまとめる

数学 線形代数

本記事は以下の過去記事で得た結果を用います．

特異値分解の導出と，左特異ベクトル，特異値，右特異ベクトルとは何かについて考える - エンジニアを目指す浪人のブログ


行列分解の一手法である特異値分解(singular value decomposition ; SVD)を利用することで行列の低ランク近似(low rank approximation)を行うことが可能ですが，どのような意味の近似になっているのかという観点について調べてまとめることにしました．

文献[1]の3章5節をベースにしてまとめますが，行間を埋めるための説明や式変形の途中経過を追加しています．

=================================================================================
特異値分解は複素数を要素にもつ行列に対する概念ですが，本記事で扱う行列，ベクトルの要素はすべて実数であるとします．


[ 1. 特異値分解による低ランク近似 ]

冒頭の過去記事(6.4)の一部を再掲します．特異値分解とは，{\displaystyle n \times d } 行列 {\displaystyle A, \mathrm{rank}{A}=r } をその最良の {\displaystyle r } 次元部分空間すなわち行空間の正規直交基底 {\displaystyle \{ \boldsymbol{v}_1,\ldots,\boldsymbol{v}_r \} } を用いて以下のように展開することです． {\displaystyle \langle \cdot , \cdot \rangle } は通常の内積です．

(1.1){\displaystyle \;\;\; A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1d} \\ a_{21} & a_{22} & \cdots & a_{2d} \\ \vdots & \vdots & \vdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nd} \end{bmatrix}= \begin{bmatrix} \boldsymbol{a}_1^T \\ \boldsymbol{a}_2^T \\ \vdots \\ \boldsymbol{a}_n^T \end{bmatrix} = \begin{bmatrix} \langle \boldsymbol{a}_1,\boldsymbol{v}_1 \rangle \boldsymbol{v}_1^T + \cdots + \langle \boldsymbol{a}_1,\boldsymbol{v}_r \rangle \boldsymbol{v}_r^T \\ \langle \boldsymbol{a}_2,\boldsymbol{v}_1 \rangle \boldsymbol{v}_1^T + \cdots + \langle \boldsymbol{a}_2,\boldsymbol{v}_r \rangle \boldsymbol{v}_r^T \\ \vdots \\ \langle \boldsymbol{a}_n,\boldsymbol{v}_1 \rangle \boldsymbol{v}_1^T + \cdots + \langle \boldsymbol{a}_n,\boldsymbol{v}_r \rangle \boldsymbol{v}_r^T \end{bmatrix} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = (A \boldsymbol{v}_1) \boldsymbol{v}_1^T + \cdots + (A \boldsymbol{v}_r) \boldsymbol{v}_r^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_1 \boldsymbol{u}_1 \boldsymbol{v}_1^T + \cdots + \sigma_r \boldsymbol{u}_r \boldsymbol{v}_r^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{i=1}^r \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = U D V^T }

ここでいきなり結論なのですが，行列 {\displaystyle A } のある {\displaystyle k < r } までの {\displaystyle \{ \boldsymbol{v}_1,\ldots,\boldsymbol{v}_k \} } による展開を考えるために {\displaystyle k+1 } 以降の項を打ち切り，(同じく) {\displaystyle n \times d } 行列 {\displaystyle A_k } で近似することを考えます．

(1.2){\displaystyle \;\;\; A \approx A_k }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = (A \boldsymbol{v}_1) \boldsymbol{v}_1^T + \cdots + (A \boldsymbol{v}_k) \boldsymbol{v}_k^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_1 \boldsymbol{u}_1 \boldsymbol{v}_1^T + \cdots + \sigma_k \boldsymbol{u}_k \boldsymbol{v}_k^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{i=1}^k \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\; = U_k D_k V_k^T }

なお冒頭の過去記事(6.1)(6.2)(6.3)に対応する以下を定義しています．

(1.3){\displaystyle \;\;\; U_k = \begin{bmatrix} \boldsymbol{u}_1 & \boldsymbol{u}_2 & \cdots & \boldsymbol{u}_k \end{bmatrix} = \begin{bmatrix} u_{11} & u_{21} & \cdots & u_{k1} \\ u_{12} & u_{22} & \cdots & u_{k2} \\ \vdots & \vdots & \vdots & \vdots \\ u_{1n} & u_{2n} & \cdots & u_{kn} \end{bmatrix} }

(1.4){\displaystyle \;\;\; D_k = \begin{bmatrix} \sigma_{1} & 0 & \cdots & 0 \\ 0 & \sigma_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_{k} \end{bmatrix} }

(1.5){\displaystyle \;\;\; V_k = \begin{bmatrix} \boldsymbol{v}_1 & \boldsymbol{v}_2 & \cdots & \boldsymbol{v}_k \end{bmatrix} = \begin{bmatrix} v_{11} & v_{21} & \cdots & v_{k1} \\ v_{12} & v_{22} & \cdots & v_{k2} \\ \vdots & \vdots & \vdots & \vdots \\ v_{1d} & v_{2d} & \cdots & v_{kd} \end{bmatrix} }


行列 {\displaystyle \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T } はすべての行が {\displaystyle \mathrm{span} \{ \boldsymbol{v}_i \} } 上のベクトルなのでランク1の行列です．行列 {\displaystyle A_k } は行空間の {\displaystyle k } 個の正規直交基底 {\displaystyle \{ \boldsymbol{v}_1,\ldots,\boldsymbol{v}_k \} } の転置(あるいは列空間の {\displaystyle k } 個の正規直交基底 {\displaystyle \{ \boldsymbol{u}_1,\ldots,\boldsymbol{u}_k \} } )の線形結合なので，{\displaystyle \mathrm{rank}A_k=k } です．行列の低ランク近似とは，まさに(1.2)のように行列 {\displaystyle A } を行列 {\displaystyle A_k } で近似することをいいます．


以上に低ランク近似の方法を機械的に示しました．この近似がどのような意味をもつかについて，具体的に以下の2点について次の章とその次の章にそれぞれまとめます(両者は密接に関連しています)．

・幾何的な解釈
・どのような距離においてどのくらい近くなっているか



[ 2. 幾何的な解釈 ]

準備として，{\displaystyle V_k = \mathrm{span} \{ \boldsymbol{v}_1,\ldots,\boldsymbol{v}_k \} } を考えます．冒頭の過去記事の定理3.1で示したように，{\displaystyle V_k } は {\displaystyle A } の行ベクトルによる点の集合 {\displaystyle \{ \boldsymbol{a}_j \}_{j=1,\cdots,n} } を {\displaystyle \mathbb{R}^d } 上の {\displaystyle n } 個の点とみなすときの"最良"の {\displaystyle k } 次元部分空間です．

以上を考慮した上で本章の目的に進みます．以下の補題は，(1.2)の幾何的な解釈を可能にします．

補題 3.5
{\displaystyle A_k } の各行は，(そのそれぞれに対応する) {\displaystyle A } の各行の {\displaystyle V_k } への射影である．

証明:

{\displaystyle A } の行ベクトルを {\displaystyle d \times 1 } ベクトル {\displaystyle \boldsymbol{a}_j, \ j=1,\ldots,n } とする(行ベクトルを意味するが列ベクトルとして定義する)．{\displaystyle \boldsymbol{v_1},\ldots,\boldsymbol{v_k} } はそれぞれ直交するので，各 {\displaystyle \boldsymbol{a}_j } の {\displaystyle V_k } への射影は {\displaystyle \sum_{i=1}^k \langle \boldsymbol{a}_j , \boldsymbol{v}_i \rangle \boldsymbol{v}_i } である．したがって，{\displaystyle A } の各行の {\displaystyle V_k } への射影はそれぞれの転置を考えて

(2.1){\displaystyle \;\;\; \begin{bmatrix} \sum_{i=1}^k \langle \boldsymbol{a}_1 , \boldsymbol{v}_i \rangle \boldsymbol{v}_i^T \\ \sum_{i=1}^k \langle \boldsymbol{a}_2 , \boldsymbol{v}_i \rangle \boldsymbol{v}_i^T \\ \vdots \\ \sum_{i=1}^k \langle \boldsymbol{a}_n , \boldsymbol{v}_i \rangle \boldsymbol{v}_i^T \end{bmatrix} = \begin{bmatrix} \langle \boldsymbol{a}_1,\boldsymbol{v}_1 \rangle \\ \langle \boldsymbol{a}_2,\boldsymbol{v}_1 \rangle \\ \vdots \\ \langle \boldsymbol{a}_n,\boldsymbol{v}_1 \rangle \end{bmatrix} \boldsymbol{v}_1^T + \cdots + \begin{bmatrix} \langle \boldsymbol{a}_1,\boldsymbol{v}_k \rangle \\ \langle \boldsymbol{a}_2,\boldsymbol{v}_k \rangle \\ \vdots \\ \langle \boldsymbol{a}_n,\boldsymbol{v}_k\rangle \end{bmatrix} \boldsymbol{v}_k^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = (A \boldsymbol{v}_1) \boldsymbol{v}_1^T + \cdots + (A \boldsymbol{v}_k) \boldsymbol{v}_k^T }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A_k }

となる．最後の等号は(1.2)を用いた．(証明終わり)


上の補題より，特異値分解による行列の低ランク近似は，「元の行列 {\displaystyle A } の各行で表わされる点の集合を {\displaystyle V_k } へ射影した点の集合で代用すること」という幾何的な解釈もできることがわかります．



[ 3. どのような距離においてどのくらい近くなっているか ]

準備として，フロベニウスノルム(文献[5]にあります)の幾何的な解釈を考えます．冒頭の過去記事(2.1)を思い出します．定義より，{\displaystyle \left\| A \right\|_F^2 } は {\displaystyle A } の行ベクトルによる点の集合 {\displaystyle \{ \boldsymbol{a}_j \}_{j=1,\cdots,n} } と {\displaystyle \mathbb{R}^d } の原点との(ユークリッド)距離の二乗の総和です．同様に {\displaystyle \left\| A-B \right\|_F^2 } は {\displaystyle A } の各行(で表される点)と {\displaystyle B } の各行(で表される点)との距離の二乗の(すべての行についての)総和と解釈できます．

もう一つの準備として，冒頭の過去記事の補題3.2の解釈を確認します．特異値の二乗 {\displaystyle \sigma_1^2,\ldots,\sigma_r^2 } は {\displaystyle A } の行ベクトルによる点の集合 {\displaystyle \{ \boldsymbol{a}_j \}_{j=1,\cdots,n} } の {\displaystyle \boldsymbol{v}_1,\ldots, \boldsymbol{v}_r } への射影の長さの二乗の総和です．フロベニウスノルムはそれらの総和と等しくなっています．


以上を考慮した上で本章の目的に進みます．以下の定理は，行列 {\displaystyle A_k } がランク {\displaystyle k } 以下の行列の中でフロベニウスノルムの意味で行列 {\displaystyle A } の最良の近似になっていることを主張しています．{\displaystyle k } を小さくする(より小さい次元の空間への射影)ほど近似誤差が大きくなること，特異値が小さい基底は近似誤差への寄与が小さいこともわかります．

定理 3.6
以下が成り立つ．

(3.1){\displaystyle \;\;\; \left\| A-A_k \right\|_F = \min_{ \mathrm{rank}{B} \le k} \left\| A-B \right\|_F = \sqrt{ \sigma_{k+1}^2 + \cdots + \sigma_r^2 } }

証明:
一つ目の等号を示す．
{\displaystyle B } はランク {\displaystyle k \; ( < r=\mathrm{rank}{A} ) } 以下のすべての {\displaystyle n \times d } 行列のうち {\displaystyle \left\| A-B \right\|_F^2} を最小にするものであると仮定する．{\displaystyle B } の行空間を {\displaystyle V } とすると {\displaystyle \mathrm{dim}V \le k } である．{\displaystyle B } の各行はそれぞれ対応する {\displaystyle A } の各行の {\displaystyle V } への射影でなければならない : そうでないならば，{\displaystyle B } の行を(それに対応する) {\displaystyle A } の行の {\displaystyle V } への射影に置き換える．この操作をしても {\displaystyle B } の行空間は {\displaystyle V } のままでありしたがって {\displaystyle \mathrm{rank}{B} \le k } のままであるが {\displaystyle \left\| A-B \right\|_F^2} は小さくなるので仮定に矛盾する．
{\displaystyle B } の各行はそれぞれ対応する {\displaystyle A } の各行の {\displaystyle V } への射影なので， {\displaystyle \left\| A-B \right\|_F^2} は {\displaystyle A } の各行の {\displaystyle V } への距離の二乗の総和である．冒頭の過去記事の定理3.1より，{\displaystyle A_k } の行空間 {\displaystyle V_{k} = \mathrm{span} \{ \boldsymbol{v}_1,\ldots,\boldsymbol{v}_k \} } は {\displaystyle A } の各行からの距離の二乗の総和を最小にする {\displaystyle k } 次元空間なので，{\displaystyle \left\| A-A_k \right\|_F \le \left\| A-B \right\|_F } を得る．

最左辺と最右辺が等しいことを示す．

{\displaystyle \;\;\; \left\| A-A_k \right\|_F^2 = \left\| \sum_{i=1}^r \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T - \sum_{i=1}^k \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T \right\|_F^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| \sum_{i=k+1}^r \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T \right\|_F^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left\| (A \boldsymbol{v}_{k+1}) \boldsymbol{v}_{k+1}^T + \cdots + (A \boldsymbol{v}_r) \boldsymbol{v}_r^T \right\|_F^2 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{i=k+1}^r \sigma_i^2 }

最後の等号は冒頭の過去記事の補題3.2を用いればよい．(証明終わり)


上の定理は，{\displaystyle A } の各行(で表される点)と {\displaystyle A_k } の各行(で表される点)との距離の二乗の(すべての行についての)総和は，打ち切った基底 {\displaystyle \{ \boldsymbol{v}_{k+1},\ldots,\boldsymbol{v}_r \} } に対応する特異値の二乗の総和(すなわち {\displaystyle A } の各行(で表される点)の {\displaystyle \boldsymbol{v}_{k+1},\ldots, \boldsymbol{v}_r } への射影の長さの二乗の総和)に等しいという幾何的な解釈もでき，これは前章の 「元の行列 {\displaystyle A } の各行で表わされる点の集合を {\displaystyle V_k } へ射影した点の集合で代用すること」の誤差を評価したものといえます．

=================================================================================

以上，特異値分解による行列の低ランク近似の基礎をまとめました．



参考文献
[1] Carnegie Mellon University Avrim Blum先生らによるノート http://www.cs.cornell.edu/jeh/book.pdf
[2] Stanford University Tim Roughgarden先生らによるノート http://theory.stanford.edu/~tim/s15/l/l9.pdf
[3] University of California at Merced Ming-Hsuan Yang先生のノート http://faculty.ucmerced.edu/mhyang/course/eecs275/lectures/lecture5.pdf
[4] Coding The Matrix: Linear Algebra Through Computer ScienceApplicationsのノート http://codingthematrix.com/slides/The_SVD.pdf
[5] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm
[6] Wikipedia Low-rank approximation のページ https://en.wikipedia.org/wiki/Low-rank_approximation