行列の conversion

今日は話が変わって、行列補完(matrix completion) のための conversion の話。詳しくは添付の図を参照のこと。

1: SDP で A_0 と A_i(i = 1,2,...,n)から aggregated sparsity pattern を作成する(行列 A*)

2: ここからは matlab あるいは octave を使う

3: A* の要素では非零要素 * を 1 (対角部分は大きめに 100) として、以下の A のような行列を作る。
A =

100 1 0 0 0
1 100 1 1 0
0 1 100 0 1
0 1 0 100 1
0 0 1 1 100

4: A を Cholesky 分解して転置する
octave:21> B = transpose(chol(A));
octave:22> B
B =

10.00000 0.00000 0.00000 0.00000 0.00000
0.10000 9.99950 0.00000 0.00000 0.00000
0.00000 0.10001 9.99950 0.00000 0.00000
0.00000 0.10001 -0.00100 9.99950 0.00000
0.00000 0.00000 0.10001 0.10002 9.99900

5: ここから先は行列 B の非零要素のみに注目する.
行列 B の一列目を見る.
1 行目, 2行目が非零要素なので、max. clique は {1,2}

6: 二列目を見る. max. clique は {2,3,4}

7: 三列目を見る. max. clique は {3,4,5}

8: 四列目を見る. clique {4,5} は max. clique {3,4,5} に含まれる

9: 五列目を見る. clique {5} は max. clique {3,4,5} に含まれる

というわけで、添付の図のように max. clique は {1,2},{2,3,4},{3,4,5} となる.