HOSVD memo

読んでいた論文に HOSVD の簡単な説明が出てきたのでメモ

HOSVD はテンソル分解の手法

SVDは,行列分解の手法で,
M_{p \times q}=U\Sigma V^t
特異値が大きい順に並んだ,対角行列 \Sigma と行列 U, V に分解する手法
特異値の大きい方から,r< \min(p,q) 個の特異値を選ぶことで,
行列の低ランク近似を行うことができる

HOSVD 4-step

  1. HOSVDでは,分解したいテンソルのモード展開行列を得る
    • モード展開行列は,各軸で切って得た,行列を並べて1つの行列としたもの
      • 参考にしました "www.geocities.jp/kashi_pong/relationalLearningTensors.pdf"
    • モード展開行列は,テンソルの階数によって決まる,3階のテンソルなら3つのモード展開行列を得る
  2. モード展開行列に対して,SVDを適用する
  3. それぞれのモード展開行列の左行列を利用して,密なコアテンソルSを得る
  4. コアテンソルSと左行列を利用して,近似テンソル\hat{A}を得る

論文中では,テンソルが更新されるたびに,これを行うのは,コストが大きいということで
Incremental SVD を利用して,逐次更新を行っていた

Incremental SVD

M_{p,q} = U_{p, r} \Sigma_{r,r} {V_{r, q}}^T
と分解できる  M_{p,q}C_{p,c} の追加要素を追加したときの,SVDを考える

L=U\setminus C=U^TC, H=(I-UU^T)C=C-UL, K=J\setminus H=J^THとおいたとき,
[M C] = [ U\Sigma V^T C] = [U J]\begin{bmatrix} \Sigma && L \\ 0 && K \end{bmatrix}\begin{bmatrix} V && 0 \\ 0 && I \end{bmatrix}^T
右辺,中央の行列をQと置くと,Qは対角行列にならないとまずい

Qを対角行列とするためSVDをすると
Q=U' \Sigma' (V')^T

Qの部分に代入して,
[M C ] = [U J](U' \Sigma' (V')^T) \begin{bmatrix} V && 0 \\ 0 && I \end{bmatrix}^T=U'' \Sigma'' (V'')^T
よって,追加要素を加えた [M C ] の SVD は,
 U''=[U J ] U', \Sigma'' = \Sigma', V'' = \begin{bmatrix} V && 0 \\ 0 && I \end{bmatrix} V'

ここで,

  • U,V は元の行列MをSVDしたもの
  • U', V' はQとおいた行列をSVDしたもの