グラフ信号処理 グラフ周波数領域におけるサンプリング

はじめに

グラフ信号処理の日本語文献はグラフフーリエ変換やグラフニューラルネットワークなどの文献が多いですが，サンプリングも重要な議論のひとつです．そこで，本記事ではグラフ周波数領域におけるサンプリングについて解説します．

手続き的な面について詳細に記述するので，理論については後述の参考文献を確認してください．
筆者も勉強中なので間違いなどありましたらご指摘いただけると幸いです．

環境

• MATLAB R2023b
• GSP toolbox : https://epfl-lts2.github.io/gspbox-html/index.html

GSP toolbox はグラフ信号処理で使えるMATLABのtoolboxです．

理論

元のグラフを$G$とし，サンプリング先のグラフを$G_1$とします．また，元信号を$\boldsymbol{f}\in\mathbb{R}^N$とします．$N$はグラフ$G$の頂点数です．今回はグラフ周波数領域におけるサンプリングをするので，元信号をグラフ周波数領域に飛ばします．
$$
\boldsymbol{\hat{f}} = \mathrm{GFT}_G(\boldsymbol{f}) = \boldsymbol{U}^\top \boldsymbol{f}.
$$
$\boldsymbol{U}$はグラフ$G$のグラフフーリエ基底です．グラフ周波数領域でサンプリングフィルタ$g(\boldsymbol{\Lambda})$を通した後，スペクトル折り畳み行列$\boldsymbol{D} _\mathrm{samp}=[\boldsymbol{I} _{M} \ \boldsymbol{I} _{M} \cdots]$をかけることでサンプリングを行います．なお，$M$はグラフ$G_1$の頂点数です．
$$
\boldsymbol{c} = \boldsymbol{D} _\mathrm{samp} \ g(\boldsymbol{\Lambda})
\ \boldsymbol{\hat{f}}.
$$

サンプリングにより$\boldsymbol{c}$の次元は$M$になりました．最後に，逆グラフフーリエ変換で信号を$G_1$上に飛ばせば完了です．
$$
\boldsymbol{f}_1 = \mathrm{IGFT} _{G_1}(\boldsymbol{c}) = \boldsymbol{U}_1 \boldsymbol{c}.
$$
$\boldsymbol{U}_1$はグラフ$G_1$のグラフフーリエ基底です．今回用いたグラフフーリエ変換，逆グラフフーリエ変換は使用している基底が別のグラフに由来することに注意してください．

具体例

頂点数32のパスグラフで具体例を示します．

N = 32;
G = gsp_path(N);
f = sin((1:N)/N*2*pi)';
figure
gsp_plot_signal(G,f)

グラフの形状とグラフ信号は下図の通り．
パスグラフ上に正弦波信号があるものとします．

この信号をグラフフーリエ変換し，グラフ周波数領域に飛ばします．

G = gsp_compute_fourier_basis(G);
f_hat = gsp_gft(G,f);
figure
gsp_plot_signal_spectral(G,f_hat)

低周波数の信号が大きく，高周波数の信号は小さいことがわかります．

この信号を新たなグラフ$G_1$上の信号としてサンプリングします．今回$G_1$として頂点数16のパスグラフを採用します．

G1 = gsp_path(N/2);

簡単のため，サンプリングフィルタとして単位行列を採用します．すなわち，
$$
\hat{g}(\boldsymbol{\Lambda}) = \boldsymbol{I}_{32}.
$$

また，頂点数32のグラフから頂点数16のグラフにサンプリングするため，スペクトル折り畳み行列は，

$$
\boldsymbol{D}_ \mathrm{samp} = \left[ \boldsymbol{I}_ {16} \ \boldsymbol{I}_{16} \right].
$$

以上より，サンプリングされたグラフ周波数領域の信号は，

g_hat = eye(N);
D_samp = [eye(N/2) eye(N/2)];
c = D_samp*g_hat*f_hat;
f1 = gsp_igft(G1,c);
figure
gsp_plot_signal_spectral(G1,c)

となり，グラフ周波数領域ではおおよそ類似した信号になります．

加えて，グラフの頂点領域では，

figure
gsp_plot_signal(G1,f1)

正弦波状の信号が得られます．

参考文献

• グラフ信号処理の基礎と応用 https://www.coronasha.co.jp/np/isbn/9784339014051/