はじめてのグラフ信号サンプリング

学生時代に作った資料が発掘されたのでここに供養しておきます

Transcript

1. はじめての グラフ信号サンプリング 朝倉 一希
2. 表記 2 スカラー 𝑎 ベクトル 𝐚 行列 𝐀 転置行列 𝐀⊤ Moore-Penrose の擬似逆行列 𝐀† 虚数単位 𝑗 複素共役 / エルミート転置 ⋅∗ アダマール積 𝐀 ∘ 𝐁 クロネッカーのデルタ 𝛿𝑎=𝑏 ≔ ቊ 1 ∶ 𝑎 = 𝑏 0 ∶ 𝑎 ≠ 𝑏 指示関数 𝟙𝐴 𝑥 ≔ ቊ 1 ∶ 𝑥 ∈ 𝐴 0 ∶ 𝑥 ∉ 𝐴
3. 行列積の図式 𝐀𝐁 = 𝐂 を以下のように表現することがある 3 × 𝑏11 ⋯ 𝑏1𝑝 ⋮ ⋮ 𝑏𝑛1 ⋯ 𝑏𝑛𝑝 𝑎11 ⋯ 𝑎1𝑛 ⋮ ⋮ 𝑎𝑚1 ⋯ 𝑎𝑚𝑛 𝑐11 ⋯ 𝑐1𝑝 ⋮ ⋮ 𝑐𝑚1 ⋯ 𝑐𝑚𝑝 と の内積 𝑛 𝑛 𝑝 𝑚 ＝ ＝
4. 取り上げたサーベイ論文 Sampling Signals on Graphs: From Theory to Applications Yuichi Tanaka, Yonina C. Eldar, Antonio Ortega, and Gene Cheung 4 本記事の流れに沿って、引用文献など から情報を補いながら解説する
5. 内容 • グラフの表現方法 • 基底展開 • グラフ信号とフーリエ変換 • グラフ信号のフィルタリング • サンプリングの一般化 • サンプリングのためのグラフ信号モデル • グラフ信号のサンプリング • サンプリング集合の選択 • グラフ信号サンプリングの応用 5 グラフ信号処理の基礎・前提知識 グラフ信号サンプリング
6. 前提知識 • 線形代数学 ⇨ [LAS.M102] 線形代数学第一・演習／[LAS.M106] 線形代数学第二 ⇨ Stephan Boyd, Lieven Vandenberghe: "Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares" • 微分積分学 ⇨ [LAS.M101] 微分積分学第一・演習／[LAS.M105] 微分積分学第二 • 複素解析、フーリエ解析 ⇨ [CSC.T351] システム解析 • 確率、統計 ⇨ [CSC.T242] 確率論・統計学／[CSC.T352] パターン認識 6
7. グラフの表現方法 7
8. グラフ グラフ…頂点と、それらを結ぶ辺で構成されたデータ構造 有限無向グラフ 𝒢 = 𝒱, ℰ 𝒱 : 頂点集合 vertexes ℰ : 辺集合 edges [例] 𝒱 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 ℰ = 𝑒12 , 𝑒15 , 𝑒23 , 𝑒25 , 𝑒34 , 𝑒45 , 𝑒46 8
9. 隣接行列 隣接行列 adjacency matrix 𝐖 𝐖 𝑚𝑛 = ቊ𝑤𝑚𝑛 : 𝑣𝑚 と 𝑣𝑛 は接続している 0 : otherwise [例] 𝐖 = 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 9
10. 次数行列 次数行列 degree matrix 𝐃 𝐃 𝑚𝑚 = ෍ 𝑛 𝐖 𝑚𝑛 [例] 𝐃 = 2 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 1 10
11. グラフラプラシアン グラフラプラシアン graph Laplacian 𝐋 𝐋 ≔ 𝐃 − 𝐀 [例] 𝐃 = 2 −1 0 0 −1 0 −1 3 −1 0 −1 0 0 −1 2 −1 0 0 0 0 −1 3 −1 −1 −1 −1 0 −1 3 0 0 0 0 −1 0 1 11
12. グラフラプラシアンによる1次変換 グラフの各頂点に紐づいた特徴量 𝐟 ∈ ℝ𝑁= 𝒱 1次変換 𝐋𝐟 𝐋𝐟 𝑖 = ෍ 𝑗=1 𝑁 𝑑𝑖𝑗 𝑓𝑗 − ෍ 𝑗=1 𝑁 𝑤𝑖𝑗 𝑓𝑗 = 𝑑𝑖𝑖 𝑓𝑖 − ෍ 𝑗=1 𝑁 𝑤𝑖𝑗 𝑓𝑗 = ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑖 − ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑗 = ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑖 − 𝑓𝑗 → 「近傍の頂点 𝑣𝑗 ∈ 𝒩 𝑣𝑖 の特徴量との差」の重み付き和 12
13. グラフラプラシアンの2次形式 2次形式 𝐟⊤𝐋𝐟 𝐟⊤𝐋𝐟 = 𝐟⊤ 𝐋𝐟 = ෍ 𝑖=1 𝑁 𝑓𝑖 ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑖 − 𝑓𝑗 = ෍ 𝑖=1 𝑁 ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑖 2 − 𝑓𝑖 𝑓𝑗 = ෍ 𝑖=1 𝑁 ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 1 2 𝑓𝑖 2 − 𝑓𝑖 𝑓𝑗 + 1 2 𝑓𝑗 2 = 1 2 ෍ 𝑖=1 𝑁 ෍ 𝑣𝑗∈𝒩 𝑣𝑖 𝑤𝑖𝑗 𝑓𝑖 − 𝑓𝑗 2 → 「近傍の頂点の特徴量との差の重み付き二乗和」の和 特徴量が隣接する頂点のものとどれほど異なっているか（滑らかさ） 13
14. グラフラプラシアンの性質 グラフラプラシアンは以下の性質を満たす • 𝐋 は実対称行列 • 𝐋 は半正定値行列 i.e. 𝐱⊤𝐋𝐱 ≥ 0 • 𝐋 の固有値は非負 • 𝐋 の各行 / 列の和は0 • 𝐋 は固有値として 0 を持つ ∵ 𝐋𝟏 = 0𝟏 14
15. [補足] 固有値分解 実対称行列 𝐀 の固有値 𝜆𝑖 ・固有ベクトル 𝐱𝑖 は以下の式を満たす 𝐀𝐱𝑖 = 𝜆𝑖 𝐱𝑖 𝐀 𝐱1 ⋯ 𝐱𝑁 = 𝐱1 ⋯ 𝐱𝑁 𝜆1 0 ⋱ 0 𝜆𝑁 𝐀 は実対称行列なので 𝐱𝑖 ⊥ 𝐱𝑗 𝑖 ≠ 𝑗 正規化（ 𝐱𝑖 = 1）すると 𝐱1 ⋯ 𝐱𝑁 = 𝐔 （直交行列）となる 𝐀𝐔 = 𝐔𝚲 𝐀 = 𝐔𝚲𝐔−1 = 𝐔𝚲𝐔⊤ ⇨ 固有値分解 eigendecomposition 15 𝐔⊤𝐔 = 𝐔𝐔⊤ = 𝐈
16. グラフラプラシアンの固有値分解 𝐋 は実対称行列なので、固有値分解可能 𝐋 = 𝐔𝚲𝐔⊤ 𝐔: 固有ベクトル行列（直交行列） 𝚲: 対角行列 𝚲 = diag 𝜆1 , … , 𝜆𝑁 𝜆𝑖 : グラフ周波数 graph frequency 𝜆𝑖 が大きいなら、対応する固有ベクトル 𝐮𝑖 は大きく振動する 16 Image Source: https://www.ieice.org/ess/sita/forum/article/2018/201803050730.pdf
17. 基底展開 17
18. [補足] ベクトル空間 ベクトル空間…線形演算（加算・スカラー倍）が定義された集合 和の条件 𝐱, 𝐲 ∈ 𝑋 に対して、和 𝐱 + 𝐲 ∈ 𝑋 が定まり、以下の法則を満たす 結合則 𝐱 + 𝐲 + 𝐳 = 𝒙 + (𝐲 + 𝐳) 可換則 𝐱 + 𝐲 = 𝐲 + 𝐳 単位元の存在 すべての 𝐱 で 𝐱 + 𝟎 = 𝐱 となる共通の元 𝟎 ∈ 𝑋 が存在 逆元の存在 任意の 𝐱 に対し 𝐱 + −𝐱 = 𝟎 となる逆元 −𝐱 ∈ 𝑋 が存在 スカラー倍の条件 18
19. [補足] ベクトル空間 ベクトル空間…線形演算（加算・スカラー倍）が定義された集合 和の条件 スカラー倍の条件 𝛼 ∈ ℝ, 𝐱 ∈ 𝑋 に対してスカラー倍 𝛼𝐱 ∈ 𝑋 が定まり、以下の法則を満たす 分配則 𝛼 𝐱 + 𝐲 = 𝛼𝐱 + 𝛼𝐲 𝛼 + 𝛽 𝐱 = 𝛼𝐱 + 𝛽𝐱 結合則 𝛼 𝛽𝐱 = 𝛼𝛽 𝐱 単位元 ∀𝐱 ∈ 𝑋, 1𝐱 = 𝐱 19
20. 内積空間 内積空間…内積 𝐱, 𝐲 ∈ ℝ が定義されたベクトル空間 内積の3条件 𝐱, 𝐲, 𝐳 ∈ 𝑋 𝛼, 𝛽 ∈ ℝ 対称性 𝐱, 𝐲 = ⟨𝐲, 𝐳⟩ 非負値性 𝐱, 𝐱 ≥ 0 ただし、等号成立は 𝐱 = 𝟎 のときのみ 線形性 𝛼𝐱 + 𝛽𝐲, 𝐳 = 𝛼 𝐱, 𝐳 + 𝛽⟨𝐲, 𝐳⟩ 𝐱, 𝐲 = 0 → 「𝐱 と 𝐲 は直交する」 20
21. 正規直交展開と係数 𝐱 = σ𝑛 𝑎 𝑛 𝐱𝑛 （ 𝐱𝑛 は正規直交基底）と表現できるとする 𝐱𝑘 , 𝐱 = 𝐱𝑘 , ෍ 𝑛 𝑎 𝑛 𝐱𝑛 = ෍ 𝑛 𝑎 𝑛 𝐱𝑘 , 𝐱𝑛 = 𝑎 𝑘 → 展開係数は元のベクトルと基底の内積で求められる 21 ∵内積の線形性 𝛼𝐱 + 𝛽𝐲, 𝐳 = 𝛼 𝐱, 𝐳 + 𝛽⟨𝐲, 𝐳⟩ ∵基底の正規直交性 𝐱𝑘 , 𝐱𝑛 = 𝛿𝑘=𝑛
22. 正規直交展開の例 𝐚 = 𝐞𝑥 , 𝐚 𝐞𝑥 + 𝐞𝑦 , 𝐚 𝐞𝑦 22 射影 𝑥 𝑦 𝐞𝑥 𝐞𝑦 𝐚
23. 正規直交でない場合 一般の基底 𝐱𝑛 に対して、双対基底 biorthogonal basis ෤ 𝐱𝑛 を考える ෤ 𝐱𝑛 , 𝐱𝑘 = 𝛿𝑛=𝑘 なるベクトル集合 ෤ 𝑥𝑛 これは常に存在することが示せる 基底展開は以下のように表せる 𝐱 = ෍ 𝑛 ෤ 𝐱𝑛 , 𝐱 𝐱𝑛 = ෍ 𝑛 𝐱𝑛 , 𝐱 ෤ 𝐱𝑛 直交基底の場合、双対基底はスケールが変わるだけ ෤ 𝐱𝑛 = 𝐱𝑛 𝐱𝑛 2 23
24. 双対基底の求め方 ෤ 𝐱𝑛 , 𝐱𝑘 = 𝛿𝑛=𝑘 は ෩ 𝐗∗𝐗 = 𝐈 と表せる 𝐗 = 𝐱1 ⋯ 𝐱𝑛 , ෩ 𝐗 = ෤ 𝐱1 ⋯ ෤ 𝐱𝑛 双対基底は ෩ 𝐗 = 𝐗 𝐗∗𝐗 −1 を満たす ෩ 𝐗∗𝐗 = 𝐈 より 𝐗෩ 𝐗∗ = 𝐈 も成り立つ 両辺に右から 𝐗 を掛けると 𝐗෩ 𝐗∗𝐗 = 𝐗 両辺に左から 𝐗෩ 𝐗∗ −1 を掛けると 𝐗෩ 𝐗∗ −1 𝐗෩ 𝐗∗ 𝐗 = 𝐗 𝐗∗𝐗 −1 24 𝐱1 ⋯ 𝐱𝑛 ෤ 𝐱1 ∗ ෤ 𝐱1 , 𝐱1 ⋯ ෤ 𝐱1 , 𝐱𝑛 ⋮ ⋮ ⋮ ෤ 𝐱𝑛 ∗ ෤ 𝐱𝑛 , 𝐱1 ⋯ ෤ 𝐱𝑛 , 𝐱𝑛
25. 基底の条件 ベクトル空間 𝑉 の 𝐱1 , ⋯ , 𝐱𝑛 を基底と呼べる条件 線形独立性 各ベクトルが線形独立 𝑎1 𝐱1 + ⋯ + 𝑎𝑛 𝐱𝑛 = 𝟎 ⟺ 𝑎1 = ⋯ = 𝑎𝑛 = 0 → 展開表現が一意 全域性 ∀𝐱 ∈ 𝑉, ∃𝑎1 , … , 𝑎𝑛 ∈ ℂ, 𝐱 = 𝑎1 𝐱1 + ⋯ + 𝑎𝑛 𝐱𝑛 → 空間内の任意のベクトルに対して展開可能 25
26. 基底として望ましい性質 基底展開の安定 ＝係数のノルムが小さいなら、展開元のベクトルのノルムも小さい 26 「基底の条件」を満たせばどんな基底でも良いの？ いいえ。工学の世界ではノイズに強いことも大事
27. リース基底 係数 𝐚 のエネルギーが展開元 𝐱 のエネルギーを保存すれば良い 𝐱 2 = 𝐚 2 正規直交基底はこの条件を満たす 条件が厳しすぎて、応用が効かない リース基底 Riesz basis 𝛼 𝐚 2 ≤ 𝐱 2 ≤ 𝛽 𝐚 2 𝛼 > 0, 𝛽 < ∞ 𝐱 のエネルギーは 𝐚 のエネルギーによってboundされる 27 拡張
28. まとめ 28 基底展開 … 基底の線形結合による表現 線形独立性・全域性を満たすベクトル集合 𝐱 = ෍ 𝑛 ෤ 𝐱𝑛 , 𝐱 𝐱𝑛 係数は双対基底との内積で与えられる 正規直交基底なら、その双対基底は自身と同じ
29. グラフ信号とフーリエ変換 29
30. グラフ信号 グラフ信号 𝑥: 𝒱 → ℝ グラフの各頂点上に信号が乗っている ベクトル表現 𝐱 ∈ ℝ𝑁 𝑁 = 𝒱 通常の信号と違い、滑らかさの解釈にはグラフの構造情報が必要 30 Image Source: グラフ信号処理の基礎理論と最近の成果 https://www.ieice.org/ess/sita/forum/article/2018/201803050730.pdf
31. フーリエ変換 フーリエ変換 𝐹 𝜔 ≔ න ℝ 𝑓 𝑡 𝑒−𝑗𝜔𝑡d𝑡 フーリエ逆変換 𝑓 𝑡 ≔ 1 2𝜋 න ℝ 𝐹 𝜔 𝑒𝑗𝜔𝑡d𝜔 これらをの関数解析の目線で見直してみる 31
32. 関数を内積空間として見る ある区間 Ω 上の関数 𝑥 𝑡 , 𝑦 𝑡 について、以下の積分を考える 𝑥, 𝑦 = න Ω 𝑥 𝑡 𝑦∗ 𝑡 d𝑡 𝑥, 𝑦 が二乗可積分 𝐿2 Ω というクラスに属するなら、⟨𝑥, 𝑦⟩ は内積 න Ω 𝑓 𝑥 2d𝑥 < ∞ 32 𝐱, 𝐲 = 𝐱⊤𝐲 = ෍ 𝑖 𝑥𝑖 𝑦𝑖
33. 複素指数関数群を用いた展開 𝑥 𝑡 ∈ 𝐿2 − 𝑇0 2 , 𝑇0 2 𝜔0 = 2𝜋 𝑇0 とすると、以下のように展開可能 𝑥 𝑡 = ෍ 𝑘=−∞ ∞ 1 𝑇0 𝑒𝑗𝜔0𝑘𝑡, 𝑥 𝑒𝑗𝜔0𝑘𝑡 基底: 𝑒𝑗𝜔0𝑘𝑡 𝑘=−∞ ∞ 双対基底: 1 𝑇0 𝑒𝑗𝜔0𝑘𝑡 𝑘=−∞ ∞ න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0𝑚𝑡 𝑒𝑗𝜔0𝑛𝑡 ∗ d𝑡 = න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0(𝑚−𝑛)𝑡d𝑡 = 𝑇0 𝛿𝑚=𝑛 33
34. [補足] 複素指数関数群の直交性 𝑚 = 𝑛 のとき න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0 𝑚−𝑛 𝑡d𝑡 = න −𝑇0/2 𝑇0/2 d𝑡 = 𝑡 ቚ −𝑇0/2 𝑇0/2 = 𝑇0 𝑚 ≠ 𝑛 のとき න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0 𝑚−𝑛 𝑡d𝑡 = 1 𝑗𝜔0 𝑚 − 𝑛 𝑒𝑗𝜔0 𝑚−𝑛 𝑡 ቚ −𝑇0/2 𝑇0/2 = 1 𝑗𝜔0 𝑚 − 𝑛 𝑒𝑗 𝑚−𝑛 𝜋 − 𝑒−𝑗 𝑚−𝑛 𝜋 = 1 𝑗𝜔0 𝑚 − 𝑛 −1 𝑚−𝑛 − −1 𝑚−𝑛 = 0 34 複素平面の単位円上で 偏角が 𝜋 の整数倍 Re Im 1 −1 O
35. 複素指数関数群を用いた展開 𝑥 𝑡 ∈ 𝐿2 − 𝑇0 2 , 𝑇0 2 𝜔0 = 2𝜋 𝑇0 とすると、以下のように展開可能 𝑥 𝑡 = ෍ 𝑘=−∞ ∞ 1 𝑇0 𝑒𝑗𝜔0𝑘𝑡, 𝑥 𝑒𝑗𝜔0𝑘𝑡 基底: 𝑒𝑗𝜔0𝑘𝑡 𝑘=−∞ ∞ 双対基底: 1 𝑇0 𝑒𝑗𝜔0𝑘𝑡 𝑘=−∞ ∞ න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0𝑚𝑡 𝑒𝑗𝜔0𝑛𝑡 ∗ d𝑡 = න −𝑇0/2 𝑇0/2 𝑒𝑗𝜔0(𝑚−𝑛)𝑡d𝑡 = 𝑇0 𝛿𝑚=𝑛 35 𝑥 𝑡 = ෍ 𝑘=−∞ ∞ 𝑐𝑘 𝑒𝑗𝜔0𝑘𝑡 𝑐𝑘 = 1 𝑇0 𝑒𝑗𝜔0𝑘𝑡, 𝑥 = 1 𝑇0 න − 𝑇0 2 𝑇0 2 𝑒−𝑗𝜔0𝑘𝑡𝑥 𝑡 d𝑡 フーリエ級数展開の定義
36. フーリエ変換と直交展開 𝐹 𝜔 ≔ 𝑒𝑗𝜔𝑡, 𝑓 = න ℝ 𝑓 𝑡 𝑒−𝑗𝜔𝑡d𝑡 𝑓 𝑡 ≔ 1 2𝜋 න ℝ 𝐹 𝜔 𝑒𝑗𝜔𝑡d𝜔 フーリエ変換も 𝑒𝑗𝜔𝑡 を基底とした展開と解釈可能 𝑒𝑗𝜔𝑡 は1次元のラプラシアン Δ の固有関数 − 𝜕 𝜕𝑡2 𝑒𝑗𝜔𝑡 = 𝜔2𝑒𝑗𝜔𝑡 36
37. グラフ信号の直交基底展開 グラフ信号は、グラフラプラシアンの固有ベクトル 𝐮1 , … , 𝐮𝑁−1 を基底として表現可能 𝐱 = ෍ 𝑖=0 𝑁−1 ො 𝑥𝑖 𝐮𝑖 = 𝐔ො 𝐱 固有ベクトルの正規直交性から、係数は内積で与えられる ො 𝑥𝑖 = 𝐮𝑖 , 𝐱 = 𝐮𝑖 ⊤𝐱 = ෍ 𝑛=0 𝑁−1 𝑢𝑖 𝑛 𝑥[𝑛] ො 𝐱 = 𝐔⊤𝐱 37
38. グラフ信号の直交基底展開 グラフ信号は、グラフラプラシアンの固有ベクトル 𝐮1 , … , 𝐮𝑁−1 を基底として表現可能 𝐱 = ෍ 𝑖=0 𝑁−1 ො 𝑥𝑖 𝐮𝑖 = 𝐔ො 𝐱 固有ベクトルの正規直交性から、係数は内積で与えられる ො 𝑥𝑖 = 𝐮𝑖 , 𝐱 = 𝐮𝑖 ⊤𝐱 = ෍ 𝑛=0 𝑁−1 𝑢𝑖 𝑛 𝑥[𝑛] ො 𝐱 = 𝐔⊤𝐱 38 ⇨ グラフフーリエ変換 GFT: Graph Fourier Transform ⇨ 逆グラフフーリエ変換 IGFT: Inverse Graph Fourier Transform
39. まとめ 39 頂点領域 グラフ周波数領域 グラフフーリエ変換 ො 𝐱 = 𝐔⊤𝐱 𝐱 = 𝐔ො 𝐱 逆グラフフーリエ変換 時間（空間）領域 周波数領域 フーリエ変換 フーリエ逆変換
40. グラフ信号のフィルタリング 40
41. 頂点領域のフィルタ 線形グラフフィルタ 𝐲 = 𝐆𝐱 𝐆 ∈ ℝ𝑁×𝑁 頂点領域のフィルタリング 𝑦 𝑘 = 𝑎𝑘𝑘 𝑥 𝑘 + ෍ 𝑙∈ ෩ 𝒩𝑘 𝑎𝑘𝑙 𝑥 𝑙 ෩ 𝒩𝑘 : 頂点 𝑘 の周辺頂点の添字の集合 （𝑘 と1本の辺で直接繋がっていなくてもよい） 周辺頂点以外の係数を 0 とすれば、 𝐲 = 𝐀𝐱 と線形フィルタで実現可 41
42. グラフ周波数領域のフィルタ グラフ周波数領域のフィルタリング 𝐲 = 𝐆𝐱 = 𝐔 ො 𝑔 𝚲 𝐔⊤𝐱 ො 𝑔 𝚲 = ො 𝑔 𝜆1 0 ⋱ 0 ො 𝑔 𝜆𝑁 グラフ周波数領域の信号 ො 𝑥𝑖 とフィルタ応答 ො 𝑔 𝜆𝑖 の積 42 IGFT GFT
43. 両領域のフィルタの関係(1) グラフ周波数領域のフィルタが 𝜆 の 𝑃 次多項式だと仮定 ො 𝑔 𝜆 = ෍ 𝑝=0 𝑃 𝑐𝑝 𝜆𝑝 ො 𝑥 𝑖 = 𝐮𝑖 ⊤𝐱 = ෍ 𝑙=1 𝑁 𝑢𝑖 𝑙 𝑥 𝑙 ො 𝑦 𝑖 = ො 𝑔 𝜆𝑖 ො 𝑥 𝑖 = ෍ 𝑝=0 𝑃 𝛼𝑝 𝜆 𝑖 𝑝 ෍ 𝑙=1 𝑁 𝑢𝑖 𝑙 𝑥 𝑙 43
44. 両領域のフィルタの関係(2) 𝑦 𝑘 = ෍ 𝑖=1 𝑁 𝑢𝑖 𝑘 ො 𝑦 𝑖 = ෍ 𝑖=1 𝑁 𝑢𝑖 𝑘 ෍ 𝑝=0 𝑃 𝛼𝑝 𝜆 𝑖 𝑝 ෍ 𝑙=1 𝑁 𝑢𝑖 𝑙 𝑥 𝑙 = ෍ 𝑙=1 𝑁 𝑥 𝑙 ෍ 𝑝=0 𝑃 𝛼𝑝 ෍ 𝑖=1 𝑁 𝑢𝑖 𝑘 𝜆 𝑖 𝑝𝑢𝑖 𝑙 = ෍ 𝑙=1 𝑁 𝑥 𝑙 ෍ 𝑝=0 𝑃 𝛼𝑝 𝐋𝑝 𝑘𝑙 44 ∵固有値分解の冪乗 𝐋𝑝 = 𝐔𝚲𝑝𝐔⊤
45. 両領域のフィルタの関係(3) 𝑦 𝑘 = ෍ 𝑙=1 𝑁 𝑥 𝑙 ෍ 𝑝=0 𝑃 𝛼𝑝 𝐋𝑝 𝑘𝑙 頂点 𝑘 と 𝑙 間の最短経路距離が 𝑝 より大きいとき、 𝐋𝑝 𝑘𝑙 = 0 グラフ周波数領域のフィルタリングは、頂点領域のフィルタリングの 係数を 𝑎𝑘𝑙 ≔ σ𝑝=0 𝐾 𝛼𝑝 𝐋𝑝 𝑘𝑙 としたものと一致 → スペクトル領域のフィルタカーネルが 𝑃 次多項式で表せるとき、フィルタ リングされた信号 𝑦 𝑘 は頂点 𝑘 の周辺 𝑃-hop の信号の線形結合 45
46. まとめ 46 頂点領域フィルタ 𝐲 = 𝐀𝐱 グラフ周波数領域フィルタ 𝐲 = 𝐔 ො 𝑔 𝚲 𝐔⊤𝐱 グラフ周波数領域のフィルタも頂点領域のフィルタで表せる → 計算量が大きい固有値分解の回避
47. サンプリングの一般化 47
48. 通常の信号の帯域制限サンプリング Shannon-Nyquistの標本化定理 ∀ 𝜔 ≥ 𝜋 𝑇 , 𝑋 𝜔 = 0 が成り立つなら、 𝑥 𝑡 ∈ 𝐿2 ℝ は 𝑥 𝑛𝑇 から復元可能 𝑥 𝑡 = ෍ 𝑛∈ℤ 𝑥 𝑛𝑇 sinc 𝑡 − 𝑛𝑇 𝑇 where sinc 𝑡 = sin 𝜋𝑡 𝜋𝑡 48 Image Source: http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/sampling.html
49. 標本化定理と基底展開 前ページの復元の式を、帯域制限された信号の部分空間に対応する 基底展開と捉えることが可能 𝑥 𝑡 = ෍ 𝑛∈ℤ 𝑥 𝑛𝑇 sinc 𝑡 − 𝑛𝑇 𝑇 = ෍ 𝑛=−∞ ∞ 𝑐 𝑛 ℎ𝑛 𝑡 基底 ℎ𝑛 𝑡 = sinc 𝑡−𝑛𝑇 𝑇 ⇨ 直交基底（双対基底は ෨ ℎ𝑛 𝑡 = 1 𝑇 sinc 𝑡−𝑛𝑇 𝑇 ） 係数 𝑐 𝑛 = ෨ ℎ𝑛 𝑡 , 𝑥 𝑡 = 𝑥 𝑛𝑇 … 時間領域におけるサンプル 49
50. [補足] sinc関数の直交性 𝑚 = 𝑛 のとき ׬ −𝜋/𝑇 𝜋/𝑇 𝑒−𝑗 𝑚−𝑛 𝑇𝜔d𝜔 = 𝜔ȁ −𝜋/𝑇 𝜋/𝑇 = 2𝜋 𝑇 𝑚 ≠ 𝑛 のとき ׬ −𝜋/𝑇 𝜋/𝑇 𝑒−𝑗 𝑚−𝑛 𝑇𝜔𝑑𝜔 = 𝑗 𝑚−𝑛 𝑇 𝑒−𝑗 𝑚−𝑛 𝑇𝜔 ȁ −𝜋/𝑇 𝜋/𝑇 = 𝑗 𝑚−𝑛 𝑇 𝑒−𝑗 𝑚−𝑛 𝜋 − 𝑒𝑗 𝑚−𝑛 𝜋 = 𝑗 𝑚−𝑛 𝑇 −1 𝑚−𝑛 − −1 𝑚−𝑛 = 0 ∴ ℎ𝑛 𝑡 , ℎ𝑚 𝑡 = 𝑇𝛿𝑛=𝑚 50 ∵Parsevalの等式 ׬ −∞ ∞ 𝑥 𝑡 𝑦 𝑡 d𝑡 = 1 2𝜋 ׬ −∞ ∞ 𝑋 𝜔 𝑌 𝜔 d𝜔 𝐻 𝜔 ≔ ℱ sinc 𝑡/𝑇 時間シフト ℱ 𝑥 𝑡 − 𝑡0 = 𝑒−𝑗𝜔𝑡0𝑋 𝜔 ℎ𝑛 𝑡 , ℎ𝑚 𝑡 = න −∞ ∞ sinc 𝑡 − 𝑛𝑇 𝑇 sinc 𝑡 − 𝑚𝑇 𝑇 d𝑡 = 1 2𝜋 න −∞ ∞ 𝐻 𝜔 2𝑒−𝑗𝜔 𝑚−𝑛 𝑇d𝜔 = 𝑇2 2𝜋 න −𝜋/𝑇 𝜋/𝑇 𝑒−𝑗 𝑚−𝑛 𝑇𝜔d𝜔 ∵ 2領域の相似性 ℱ 𝑥 𝑎𝑡 = 1/ 𝑎 𝑋 𝜔/𝑎 sinc関数と矩形関数の関係 ℱ sinc 𝑡 = 𝟙 𝜔 ≤𝜋 𝜔
51. [補足] 係数とサンプルの関係 𝑐 𝑛 = ෨ ℎ𝑛 𝑡 , 𝑥 𝑡 = 1 𝑇 න −∞ ∞ 𝑥 𝑡 sinc 𝑡 − 𝑛𝑇 𝑇 d𝑡 = 1 𝑇 ⋅ 𝑇 2𝜋 න − 𝜋 𝑇 𝜋 𝑇 𝑋 𝜔 𝑒𝑗𝜔𝑛𝑇𝑑𝜔 = 1 2𝜋 න −∞ ∞ 𝑋 𝜔 𝑒𝑗𝜔𝑛𝑇𝑑𝜔 = 𝑥 𝑡 = 𝑛𝑇 51 ∵ 𝐿2 ℝ の内積 𝑥, 𝑦 = ׬ ℝ 𝑥 𝑡 𝑦 𝑡 d𝑡 ∵フーリエ逆変換の定義 𝑓 𝑡 ≔ 1 2𝜋 ׬ ℝ 𝐹 𝜔 𝑒𝑗𝜔𝑡d𝜔 ∵ 帯域制限条件 ∀ 𝜔 ≥ 𝜋/𝑇, 𝑋 𝜔 = 0 ∵前ページ同様 Parsevalの等式・時間シフト・ 2領域の相似性 sinc関数と矩形関数の関係
52. 一般化サンプリング 信号が属する部分空間の情報を利用した一般化サンプリング ▶ サンプルの取得 𝐜 = 𝑆∗𝐱 = 𝐬1 ∗ ⋮ 𝐬𝑁 ∗ 𝐱 = 𝐬1 , 𝐱 ⋮ 𝐬𝑁 , 𝐱 𝐱 ∈ ℋ （ヒルベルト空間） 𝐬𝑛 : リース基底 ▶ 一般化した信号の復元 ෤ 𝐱 = 𝑊𝐻𝐜 = 𝐰1 ⋯ 𝐰𝑁 𝐇𝐜 ෤ 𝐱 ∈ 𝒲 ⊂ ℋ {𝐰𝑛 }: 𝒲 の基底 𝐻: 補正変換 52 ※理解しやすさのために行列表現しているが、 𝑁 が無限になることもあり得る
53. まとめ 53 （一般化した）サンプリングとその復元 ＝ 基底展開 𝑆∗ 𝐻 𝑊 𝐱 ෤ 𝐱 𝑐 𝑛 𝑑 𝑛 サンプリング変換 補正変換 復元変換 サンプリング 復元 𝐜 = 𝑆∗𝐱 ෤ 𝐱 = 𝑊𝐻𝐜
54. サンプリングのための グラフ信号モデル 54
55. グラフ信号の部分空間モデル グラフ信号 𝐱 ∈ ℝ𝑁 が 𝐚𝑘 𝑘=1 𝐾 𝐾 ≤ 𝑁 が張る部分空間 𝒜 ⊂ ℝ𝑁 に あるとする … 前提知識 𝐱 ≔ ෍ 𝑘=1 𝑁 𝑑𝑘 𝐚𝑘 = 𝐀𝐝 サンプリング 𝐜 ≔ 𝐒⊤𝐱 ∈ ℝ𝑀 𝑀 ≤ 𝑁 復元 ෤ 𝐱 = 𝐀 𝐒⊤𝐀 †𝐒⊤𝐱 = 𝐖𝐇𝐜 ℝ𝑁 = 𝒜⨁𝒮⊥ なら 𝐒⊤𝐀 † = 𝐒⊤𝐀 −1 となり、完全な復元が可能 55 生成行列 𝐀 ∈ ℝ𝑁×𝐾 サンプリング演算子 𝐒 ∈ ℝ𝑁×𝑀 補正変換 𝐇 = 𝐒⊤𝐀 †
56. [補足] 部分空間モデルの信号復元 𝐒⊤𝐱 = 𝐒⊤𝐀𝐝 ሚ 𝐝 = 𝐒⊤𝐀 †𝐒⊤𝐱 ෤ 𝐱 = 𝐀 ሚ 𝐝 = 𝐀 𝐒⊤𝐀 †𝐒⊤𝐱 𝐒⊤𝐀 が正則なら、 ሚ 𝐝 は厳密解となる → ℝ𝑁 = 𝒜⨁𝒮⊥ 56 𝐒⊤𝐀 ∈ ℝ𝑀×𝐾 は 𝐾 < 𝑀 で縦長 一般には解なしなので、最小二乗解を求める ሚ 𝐝 = argmin 𝐝 𝐒⊤𝐀𝐝 − 𝐒⊤𝐱 2 サンプリングレートに対して、復元される信号の部分空間の次元が十 分に低ければ復元可能 （𝐾 < 𝑀）
57. グラフ信号サンプリングの問題 グラフ信号サンプリングの問題 • 生成行列 𝐀 とサンプリング演算子 𝐒 の選択・最適化 • 擬似逆行列 𝐇 = 𝐒⊤𝐀 † の計算の効率的な実装 以降で、前提知識とそれに対応するモデル式の例を見ていく 57
58. 帯域制限モデル グラフ周波数の数を ℬ = 𝐾 までに制限したモデル 𝐀 = 𝐔𝒱ℬ = 𝐮1 ⋯ 𝐮𝐾 と取る 𝐱BL = ෍ 𝑖=1 𝐾 𝑑𝑖 𝐮𝑖 = 𝐔𝒱ℬ 𝐝 𝜔 ≔ 𝜆𝐾 : カットオフ周波数 Paley-Wiener 空間 𝑃𝑊 𝜔 𝒢 …帯域制限されたグラフ信号の部分空間 58
59. グラフ周波数領域部分空間モデル 帯域制限モデルの一般化 𝐀 = ⋯ σ 𝑗=1 𝑁 ො 𝑎𝑖 𝜆𝑗 𝐮𝑗 ⋯ と取る 𝐱 = ෍ 𝑖=1 𝐾 𝑑𝑖 ෍ 𝑗=1 𝑁 ො 𝑎𝑖 𝜆𝑖 𝐮𝑗 = 𝐀𝐝 ො 𝑎𝑖 𝜆 はスペクトルの形を表現する係数 ො 𝑎𝑖 𝜆𝑗 = δ𝑗=𝑖 𝟙 𝜆𝑗<𝜔 𝜆𝑗 とすると、帯域制限モデルと同値に 59
60. 周期的グラフ周波数部分空間モデル スペクトルの周期性を仮定したモデル 𝐀 = 𝐔ො 𝑎 𝚲 𝐃samp ⊤ と取る 𝐱PGS = 𝐔ො 𝑎 𝚲 𝐃samp ⊤ 𝐝 𝐃samp ⊤ : グラフ周波数領域でのアップサンプリング （𝐃samp = 𝐈𝑀 𝐈𝑀 ⋯ : スペクトル折り畳み行列） 60
61. 頂点領域部分空間モデル 区分的に不変なグラフ信号モデル 𝐀 = 𝟏𝒯 1 ⋯ 𝟏𝒯 𝐾 と取る 𝐱PC = ෍ 𝑖=1 𝐾 𝑑𝑖 𝟏𝒯 𝑖 = 𝟏𝒯 1 ⋯ 𝟏𝒯 𝐾 𝐝 分割 𝒯 𝑖 𝑖=1 𝐾 … 含まれる頂点はクラスタ内で接続されている 𝟏𝒯 𝑖 𝑛 = 𝟙𝑣𝑛∈𝒯 𝑖 𝑛 同様に、区分的に滑らかなグラフ信号モデルも定義できる 61
62. ෤ 𝐱 = 𝐖𝐇𝐜 以外の復元手法 グラフ信号がある部分空間にあるという前提がなく、滑らかだという 情報しかないときの復元 ෤ 𝐱 = argmin 𝐱∣𝐒⊤𝐱=𝐜 𝐕𝐱 𝑝 𝐕: 信号の滑らかさを測る行列 制約つき最小二乗問題は多目的最小二乗問題と捉えられる ෤ 𝐱 = argmin 𝐱 𝐒⊤𝐱 − 𝐜 2 2 + 𝛾 𝐕𝐱 𝑝 𝛾 > 0 : 正則化パラメータ 62
63. まとめ 63 グラフ信号がある部分空間 𝒜 にある（𝐱 = 𝐀𝐝）という前提での サンプリングと復元は以下のように表せる サンプリング 𝐜 ≔ 𝐒⊤𝐱 復元 ෤ 𝐱 ≔ 𝐀 𝐒⊤𝐀 †𝐒⊤𝐱 様々なグラフ信号の特徴に対応するモデルを確認した 生成行列 𝐀 による信号 𝐱 の表現
64. グラフ信号のサンプリング 64
65. 頂点領域サンプリング 頂点領域のサンプリング サンプルとして、予め決まった集合 𝒯 ∈ 𝒱 𝒱 = 𝑀 を選ぶ 𝐜 = 𝐈𝒯𝒱 𝐆𝐱 𝐆 ∈ ℝ𝑁×𝑁: 線形グラフフィルタ（しばしば 𝐆 = 𝐈） 𝐈𝒯𝒱 : 単位行列の小行列 … 𝒯 に含まれる頂点を選ぶ写像 サンプリング演算子 𝐒⊤ = 𝐈𝒯𝒱 𝐆 65
66. グラフ周波数領域サンプリング グラフ周波数領域のサンプリング 周波数を 𝑁 個から 𝑀 個に絞る（𝑀: サンプリングレート） 𝐜 = 𝐃samp ො 𝑔 𝚲 ො 𝐱 ො 𝑔 𝚲 : グラフ周波数領域のフィルタ 𝐃samp = 𝐈𝑀 𝐈𝑀 ⋯ : スペクトル折り畳み行列 サンプリング演算子 𝐒⊤ = 𝐃samp ො 𝑔 𝚲 𝐔⊤ 66 ො 𝑔 ො 𝑥 1 ො 𝑥 1 ⋮ ො 𝑔 ො 𝑥 𝑁 ො 𝑥 𝑁 1 0 1 0 ⋱ ⋯ ⋱ 0 1 0 1 𝑐 1 ⋮ 𝑐 𝑀 𝑀 𝑁 𝑁 = 𝑀 × 𝑁/𝑀 𝑐 𝑖 = ෍ 𝑗≡𝑖 mod 𝑀 ො 𝑔 ො 𝑥 𝑗 ො 𝑥 𝑗
67. 2領域のサンプリングの関係 グラフ周波数領域におけるサンプリングは、一般には 𝐜 = 𝐈𝒯𝒱 𝐆𝐱 の形 には表せない → 頂点領域とグラフ周波数領域でのサンプリングが関連づかない グラフ周波数領域サンプリングでは、全頂点の信号が必要 67 Image Source: "Sampling Signals on Graphs: From Theory to Applications"
68. 頂点領域サンプリングの補正 通常の信号の時間領域サンプリングの復元 サンプリング後に低域通過フィルタを掛けてエイリアシングを防ぐ 補正変換 グラフ信号の頂点領域サンプリングの復元 補正行列 𝐇 = 𝐒⊤𝐀 † = 𝐈𝒯𝒱 𝐆𝐀 † は、対角なグラフ周波数領域のフィルタ ො 𝑔 𝚲 として表せない 68
69. まとめ 69 グラフ信号のサンプリングは以下の式で表せる ▶ 頂点領域 𝐜 = 𝐈𝒯𝒱 𝐆𝐱 ▶ グラフ周波数領域 𝐜 = 𝐃samp ො 𝑔 𝚲 ො 𝐱 2領域のサンプル間を互いに関連付けることはできていない
70. サンプリング集合の選択 70
71. サンプリング集合の選択における問題 サンプリング集合の選択における問題 • カットオフ周波数がわからない • ノイズに対してロバストか？ • 計算量の問題 グラフラプラシアンの固有値分解は 𝑂 𝑁3 サンプリング集合を選ぶアルゴリズムを考える • 決定的アルゴリズム … 目的のコスト関数を最適化するように選択 • 確率的アルゴリズム … 確率分布に従ってランダムに選択 71
72. 帯域制限モデルのサンプル選択 帯域制限モデルで、信号を直接サンプリングする（ 𝐆 = 𝐈 ） 独立同分布のノイズの乗ったサンプル 𝐲 = 𝐜 + 𝐧 の復元 ෤ 𝐱 = 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐲 = 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐜 + 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐧 復元誤差 𝐞 ≔ ෤ 𝐱 − 𝐱 = 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐧 多くの決定的アルゴリズムは、誤差共分散行列 𝐄 を最適化の対象に 𝐄 ≔ 𝔼 𝐞𝐞⊤ = 𝐔𝒱ℬ 𝐔𝒯ℬ ⊤ 𝐔𝒯ℬ −1 𝐔𝒱ℬ ⊤ 72
73. [補足] 誤差共分散行列の導出 ノイズ 𝐧 が 𝛍 = 𝔼 𝐧 = 𝟎, 𝚺 = 𝔼 𝐧𝐧⊤ = 𝐈 の分布に従うとする 𝐄 = 𝔼 𝐞 − 𝔼 𝐞 𝐞 − 𝔼 𝐞 ⊤ = 𝔼 𝐞 − 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝔼 𝐧 𝐞 − 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝔼 𝐧 ⊤ = 𝔼 𝐞𝐞⊤ = 𝔼 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐧 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐧 ⊤ = 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝔼 𝐧𝐧⊤ 𝐔 𝒯ℬ † ⊤ 𝐔𝒱ℬ ⊤ = 𝐔𝒱ℬ 𝐔 𝒯ℬ † 𝐔𝒯ℬ ⊤ † 𝐔𝒱ℬ ⊤ = 𝐔𝒱ℬ 𝐔𝒯ℬ ⊤ 𝐔𝒯ℬ −1 𝐔𝒱ℬ ⊤ 73
74. 最適基準 実験計画法の最適計画における基準を用いた最適化手法 応答以外のパラメータを変えて分散を小さくする方法を考えたい A最適基準 逆行列の部分のトレースを小さくする minimize 𝒯∣ 𝒯 =𝑀 Tr 𝐔𝒯ℬ ⊤ 𝐔𝒯ℬ −1 E最適基準 𝐔𝒱ℬ ⊤ 𝐔𝒱ℬ の最小固有値 𝜆min を最大化 ⇨ 最悪なケースでの誤差を最小化 maximize 𝒯∣ 𝒯 =𝑀 𝜆min 𝐔𝒯ℬ ⊤ 𝐔𝒯ℬ 74
75. 誤差共分散行列利用の問題点 誤差共分散行列を利用したサンプル選択は、 𝑀 × 𝑀 行列の特異値 分解が必要 高い計算量を要する 特異値分解を回避した貪欲な手法も提案されている • グラフ周波数プロキシを用いた手法 [A. Anis, 2016] • A最適基準をローパスグラフフィルタの関数として表し、ブロック行列の逆 行列を用いる手法 [F. Wang, 2019] • グラフ局在化演算子による手法 [A. Sakiyama, 2019] 75
76. 滑らかな信号のサンプル選択 滑らかな信号の復元において、 𝐕 = 𝐋1/2 と取る （グラフラプラシアン正則化 graph Laplacian regularization） 𝐱∗ = argmin 𝐱 𝐒⊤𝐱 − 𝐲 2 2 + 𝛾𝐱⊤𝐋𝐱 = 𝐒𝐒⊤ + 𝛾𝐋 −1𝐒𝐲 二乗誤差（の上界）のE最適基準を考え、最適な 𝐒⊤ を求める maximize 𝐒 𝜆min 𝐒𝐒⊤ + 𝛾𝐋 これは、 Gershgorin の定理により、固有値分解なしで解ける 76 c.f.) Yuanchao Bai, Fen Wang, Gene Cheung, Yuji Nakatsukasa, Wen Gao: "Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment", IEEE Trans. Signal Process., vol. 68, pp. 2419-2434 (2020)
77. [補足] 正則化つき復元の閉じた形の解 加重和目的関数の最小問題 → スタックして1つにまとめる 𝐱∗ = argmin 𝐱 𝐒⊤𝐱 − 𝐲 2 2 + 𝛾𝐱⊤𝐋𝐱 = argmin 𝐱 𝐒⊤ 𝜆𝐋1/2 𝐱 − 𝐲 𝟎 2 2 ෩ 𝐀 = 𝐒⊤ 𝜆𝐋 1 2 , ሚ 𝐛 = 𝐲 𝟎 とおくと、 ෩ 𝐀⊤ ෩ 𝐀 = 𝐒 𝜆𝐋1/2 𝐒⊤ 𝜆𝐋1/2 = 𝐒𝐒⊤ + 𝜆𝐋 ෩ 𝐀⊤𝐛 = 𝐒 𝜆𝐋1/2 𝐲 𝟎 = 𝐒𝐲 ∴ 𝐱∗ = ෩ 𝐀†ሚ 𝐛 = ෩ 𝐀⊤ ෩ 𝐀 −1 ෩ 𝐀⊤ሚ 𝐛 = 𝐒𝐒⊤ + 𝜆𝐋 −1𝐒𝐲 77 𝐋 が半正定値行列であることを利用して 𝐱⊤𝐋𝐱 = 𝐱⊤𝐋1/2𝐋1/2𝐱 = 𝐋1/2𝐱 ⊤ 𝐋1/2𝐱 = 𝐋1/2𝐱 2 2
78. [補足] Gershgorinの定理 Gershgorin の定理 Gershgorin circle theorem 𝐀 ∈ ℝ𝑛×𝑛 の任意の固有値は、少なくとも1つのGershgorin 円盤 𝐷 𝑎𝑖𝑖 , 𝑅𝑖 の上に載っている 𝐷 𝑎𝑖𝑖 , 𝑅𝑖 : 𝑎𝑖𝑖 を中心とする半径 𝑅𝑖 = σ𝑗≠𝑖 𝑎𝑖𝑗 の閉円盤 → 非対角成分のノルムが十分小さければ、固有値は対角成分からあまり遠く ならない 78
79. グラフ局在化演算子 グラフ局在化演算子 graph localization operator グラフ周波数領域フィルタ ො 𝑔 𝜆 の頂点領域表現 𝛹𝑔,𝑖 𝑛 ≔ 𝑁 ෍ 𝑘=1 𝑁 ො 𝑔 𝜆𝑘 𝑢𝑘 𝑖 𝑢𝑘 𝑛 𝛹𝑔,𝑖 = 𝐔 ො 𝑔 𝚲 𝐔⊤𝛅𝑖 頂点領域・スペクトル領域どちらの手法も統一的に記述できる 79 c.f.) A. Sakiyama, Y. Tanaka, T. Tanaka, and A. Ortega: "Eigendecomposition-free sampling set selection for graph signals", IEEE Trans. Signal Process., vol. 67, no. 10, pp. 2679-2692 (2019)
80. 確率的アルゴリズム 確率的なサンプリング集合選択アルゴリズムは以下の2種類 • グラフと独立した手法 グラフの構造を考慮に入れずランダムに選択 ◦ 計算コストが小さい △ 決定的アルゴリズムよりも必要な頂点が増える • グラフに依存した手法 グラフ構造の情報によって、頂点の重要度が変化する 例: 大きい辺の重みで多くの頂点に接続 80
81. グラフに依存した確率的選択 帯域制限グラフ信号のグラフコヒーレンスに基づく選択法 𝐩 ∈ ℝ𝑁 : 頂点 𝑖 を選ぶ確率分布 σ𝑖 𝑝 𝑖 = 1 𝑝 𝑖 ≔ 𝐔𝒱ℬ ⊤ 𝛅𝑖 2 2 𝐾 = 𝜓𝑔,𝑖 2 2 𝐾 ො 𝑔 𝜆 : 帯域制限フィルタ 固有値分解を避けるためにフィルタを多項式近似 𝛅𝑖 の代わりにランダムな信号をフィルタリングしてさらに計算量削減 81
82. まとめ 82 サンプリング集合の選択アルゴリズムは2種類に大別される 決定的アルゴリズム 目的のコスト関数の最適化問題を解くことによりサンプルを決定 確率的アルゴリズム ある確率分布に従ってサンプリングする頂点を無作為に選択 固定の確率分布 or グラフ構造の情報から生成した確率分布を利用
83. グラフ信号サンプリングの応用 83
84. 応用領域 グラフ信号サンプリングは幅広く応用できる • 無線通信 • データマイニング • 3Dイメージング ⋮ ここからはいくつかの応用例を見ていく 84
85. センサ配置 センサ配置問題 観測誤差が小さくなるように限られた数のセンサをどう配置するか 場の信号を、計測行列と低次元ベクトルで表現 𝐟 = 𝚽𝛂 これまでは 𝚽 をガウス過程回帰（劣モジュラ最適化）により生成 誤差の共分散行列を小さくするように 𝚽 = 𝐔𝑀 = 𝐋 の 𝑀 個目までの固有ベクトルを含む行列 とする → 帯域制限されたグラフ信号サンプリング問題と解釈できる 従来手法と比べ速度・復元性能ともにアップ 85
86. 行列補間のためのサンプリング 行列補間 部分的に観測した、サイズの大きな信号 𝐗 ∈ ℝ𝑁𝑟×𝑁𝑐 の欠損値を埋める 解を絞るためには 𝐗 に低ランク性などの前提が必要 低ランク ＝ 行 / 列に沿って要素が類似している → 行方向と列方向のグラフを考え、滑らかなグラフ信号の復元問題に minimize 𝐱 1 2 𝐀Ω ∘ 𝐗 − 𝐘 𝐹 2 + 𝛼 2 Tr 𝐗⊤𝐋𝑟 𝐗 + 𝛽 2 Tr 𝐗𝐋𝑐 𝐗⊤ 𝐀Ω : サンプリング行列 𝐀Ω 𝑖𝑗 = 𝟙 𝑖,𝑗 ∈Ω 𝑖, 𝑗 86
87. ポイントクラウドのサブサンプリング ポイントクラウド 3Dイメージングのための信号表現（座標などのサンプル） 数百万点にも及び、計算負荷が高い → サブサンプリングの必要性 グラフサンプリングを応用することで、幾何学的特徴をしっかり保持 することができる 点の𝑘-近傍のグラフ上で滑らかであることを期待 → 滑らかなグラフ信号の復元問題と同様 87
88. 参考文献 [1] • Yuichi Tanaka, Yonina C. Eldar, Antonio Ortega, and Gene Cheung: "Sampling Signals on Graphs: From Theory to Applications", IEEE Signal Process. Mag., vol.37, issue.6, pp.14-30 (2020) • David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst: "The Emerging Field of Signal Processing on Graphs: Extending High- Dimensional Data Analysis to Networks and Other Irregular Domains", IEEE Signal Process. Mag., vol.30, no.3, pp.83-98 (2013) • 田中雄一: "グラフ信号処理のすゝめ", 電気情報通信学会 基礎・境界ソサイエティ Fundamentals Review, vol.8, no.1, pp.15-29 (2014) • Yuanchao Bai, Fen Wang, Gene Cheung, Yuji Nakatsukasa, Wen Gao: "Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment", IEEE Trans. Signal Process., vol.68, pp.2419- 2434 (2020) 88
89. 参考文献 [2] 89 • Yonina C. Eldar: "Sampling Theory: Beyond Bandlimited Systems", Cambridge University Press (2015) • 山田功: "工学のための関数解析", 工学のための数学, 数理工学社 (2009) • 高崎金久: "線形代数とネットワーク", 日本評論社 (2017) • 鏡慎吾: "やる夫で学ぶディジタル信号処理", http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/main.html (2011) • Wikipedia: "ゲルシュゴリンの定理", https://ja.wikipedia.org/wiki/ゲルシュゴリンの定理 (閲覧: 2021/08/15)