固定の加速係数を用いるFISTAのパラメータ設定に関する検討

1/17 固定の加速係数を用いる FISTAのパラメータ設定に関する 検討 亀田快宙1，早川諒1，林和則2，飯國洋二1 大阪大学大学院 基礎工学研究科1 京都大学国際高等教育院附属データ科学イノベーション教育研究センター2 2022/5/18 SCI2022

目次 1. 研究背景・目的 2. 先行研究 3. 検討手法 4. シミュレーション結果（特性評価） 5. 結論 2/17

研究背景｜圧縮センシング[1] 3/17 少ない観測データ 𝒚 = 𝑨𝒙∗ + 𝒆 ∈ ℂ𝑀 から スパースな（零成分が多い）信号 𝒙∗ ∈ ℂ𝑁 を復元（𝒆 ∈ ℂ𝑀 ：雑音 ） 観測ベクトル 推定したいスパースな ベクトル 𝐾≤𝑀<𝑁 [1] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289 –1306, Apr. 2006. 観測雑音 個

研究背景｜ FISTA [2] 圧縮センシングの最適化問題 観測との誤差 4/17 スパース性 minimize 𝑁 𝒙∈ℂ 高速反復縮小閾値アルゴリズム (FISTA：Fast Iterative Shrinkage Thresholding Algorithm) 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 推定値 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1 ] + 𝑗𝑆γλ Im[𝒖𝑡+1 ] ソフト閾値関数：𝛼 > 0，𝑣 ∈ ℝ 𝑎𝑡+1 = 𝑠𝑡−1 𝑠𝑡+1 𝑣− 𝛼 (𝑣 ≥ 𝛼) (−𝛼 < 𝑣 < 𝛼) 𝑆𝛼 (𝑣) = ൞ 0 𝑣+ 𝛼 (𝑣 ≤ −𝛼) 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑎𝑡+1 𝒙𝑡+1 − 𝒙𝑡 [2] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 188–202, 2009.

研究背景｜ FISTA [2] 圧縮センシングの最適化問題 観測との誤差 5/17 スパース性 minimize 𝑁 𝒙∈ℂ 高速反復縮小閾値アルゴリズム (FISTA：Fast Iterative Shrinkage Thresholding Algorithm) 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 推定値 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1 ] + 𝑗𝑆γλ Im[𝒖𝑡+1 ] 𝑎𝑡+1 = 𝑠𝑡−1 𝑠𝑡+1 加速係数𝑎𝑡+1は 更新に変数での除算を含む 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑎𝑡+1 𝒙𝑡+1 − 𝒙𝑡 [2] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 188–202, 2009.

研究背景・目的｜光演算回路[3] 6/17 光演算回路・・・電子ではなく光を利用する演算回路 ベクトル-行列積などの演算が低遅延・省電力で行える 行えない演算がある 例）変数による除算 FISTAは加速係数 𝑎𝑡+1= 𝑠𝑡 −1 の更新に 𝑠𝑡+1 変数による除算を含む計算がある 先行研究 圧縮センシングの低遅延化・省電力化のために 光演算回路での実装を想定したFISTA（CMC-FISTA）の 検討と特性評価 [3] K. Nozaki, S. Matsuo, T. Fujii, K. Takeda, A. Shinya, E. Kuramochi, and M. Notomi, “Femto-farad optoelectronic integration demonstrating energy-saving signal conversion and nonlinear functions,” Nature Photonics, vol. 13, pp. 454–459, 2019.

先行研究｜CMC-FISTA [4] 7/17 加速係数 𝑎𝑡+1 を定数 𝑐 に置き換えたFISTA (CMC-FISTA：Constant Momentum Coefficient FISTA）を 光演算回路に適したアルゴリズムとして提案 FISTA CMC-FISTA 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1] + 𝑗𝑆γλ Im[𝒖𝑡+1] 𝑎𝑡+1 = 𝑠𝑡 −1 加速係数 0 ≤ 𝑎𝑡+1 ≤ 1 固定の加速係数 0≤𝑐 ≤1 𝑠𝑡+1 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑎𝑡+1 𝒙𝑡+1 − 𝒙𝑡 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 [4] 亀田快宙，早川諒，林和則，飯國洋二，「固定のMomentum係数を用いるFISTAの特性評価」，電子情報通信学会総合大会，A-8-12，2022年3月

先行研究｜CMC-FISTA [4] 8/17 加速係数 𝑎𝑡+1 を定数 𝑐 に置き換えたFISTA (CMC-FISTA：Constant Momentum Coefficient FISTA）を 光演算回路に適したアルゴリズムとして提案 FISTA CMC-FISTA 固定の加速係数 𝑐 の値を適切に定めれば 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 CMC-FISTAはFISTAと同程度の特性を達成する 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1] + 𝑗𝑆γλ Im[𝒖𝑡+1] 𝑎𝑡+1 = 𝑠𝑡 −1 加速係数 0 ≤ 𝑎𝑡+1 ≤ 1 固定の加速係数 0≤𝑐 ≤1 𝑠𝑡+1 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑎𝑡+1 𝒙𝑡+1 − 𝒙𝑡 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 [4] 亀田快宙，早川諒，林和則，飯國洋二，「固定のMomentum係数を用いるFISTAの特性評価」，電子情報通信学会総合大会，A-8-12，2022年3月

検討①｜ソフト閾値関数の変更 9/17 ① ソフト閾値関数の変更（複素スパースベクトルに適切なソフト閾値関数を採用） ➢ 実部と虚部を同時に考慮することができ、信号 𝒙∗ が複素スパースな場合 推定の精度を上げることが出来る 従来手法 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1] + 𝑗𝑆γλ Im[𝒖𝑡+1] 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 ソフト閾値関数：𝛼 > 0，𝑣 ∈ ℝ 𝑣− 𝛼 (𝑣 ≥ 𝛼) (−𝛼 < 𝑣 < 𝛼) 𝑆𝛼 (𝑣) = ൞ 0 𝑣+ 𝛼 (𝑣 ≤ −𝛼) 提案手法 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑇γλ 𝒖𝑡+1 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 ソフト閾値関数：𝛼 > 0，𝑣 ∈ ℂ 𝑣 𝑣 −𝛼 𝑣 ≥𝛼 𝑣 𝑇𝛼 (𝑣) = ቐ 0 𝑣 <𝛼 シミュレーションの流れ 1. 収束時の平均二乗誤差が最小となる λ の値 2. 収束までの繰り返し回数が最小となる 𝑐 の値 →従来手法と検討手法で𝛌、 𝒄 の値にどのような違いが生じるか調べた

検討① 収束時の平均二乗誤差が最小となる λ の値の分布 𝑁 = 500，信号対雑音比 25 dB 𝑨 ：部分離散フーリエ変換行列 提案手法 圧縮率(M/N) 圧縮率(M/N) 従来手法 信号密度(K/N) 信号密度(K/N) ➢ 圧縮率が0.5以上になるとλはほぼ同じ値となる ➢ 提案手法のλ の値は、従来法のλ の値とほぼ同じ値である 10/17

検討① 11/17 収束時の平均二乗誤差が最小となる λ の値の分布 圧縮センシングの最適化問題 𝑁 = 500，信号対雑音比 25 dB 観測との誤差 𝑨 ：部分離散フーリエ変換行列 minimize 𝑁 𝒙∈ℂ 従来手法 スパース性 提案手法 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 圧縮率(M/N) 圧縮率(M/N) 従来手法 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑆γλ Re[𝒖𝑡+1] + 𝑗𝑆γλ Im[𝒖𝑡+1] ソフト閾値関数：𝑣 ∈ ℝ 信号密度(K/N) 𝑆𝛾𝜆 (𝑣) 信号密度(K/N) −𝛾𝜆 ➢ 圧縮率が0.5以上になるとλはほぼ同じ値となる 𝛾𝜆 ➢ 提案手法のλ の値は、従来法のλ の値とほぼ同じ値である

検討① 収束時の平均二乗誤差が最小となる λ の値の分布 𝑁 = 500，信号対雑音比 25 dB 𝑨 ：部分離散フーリエ変換行列 提案手法 圧縮率(M/N) 圧縮率(M/N) 従来手法 信号密度(K/N) 信号密度(K/N) ➢ 圧縮率が0.5以上になるとλはほぼ同じ値となる ➢ 提案手法のλ の値は、従来法のλ の値とほぼ同じ値である 12/17

検討① 収束までの繰り返し回数が最小となる 𝑐 の値の分布 𝑁 = 500，信号対雑音比 25 dB 𝑨 ：部分離散フーリエ変換行列 従来手法 13/17 提案手法 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑇γλ 𝒖𝑡+1 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 提案手法 ➢ 従来・提案手法両方において、信号密度が小さく，また 圧縮率の値が大きくなるにつれ適切な 𝑐 の値は小さくなる ➢ 提案手法での適切な 𝑐 の値は従来手法と同程度の値となる

検討②｜観測行列𝑨 ② 観測行列𝑨 ：部分フーリエ変換行列→i.i.d.ガウス行列 ◼ 部分離散フーリエ変換 光演算回路で実現しやすい ◼ i.i.d.ガウス行列 圧縮センシング行列でよく検討されるランダム行列 𝐾≤𝑀<𝑁 シミュレーションの流れ 1. 収束時の平均二乗誤差が最小となる λ の値 2. 収束までの繰り返し回数が最小となる 𝑐 の値 →部分フーリエ変換行列とi.i.d.ガウス行列で𝝀、 𝒄 の値に どのような違いが生じるか調べた 14/17

検討② 収束時の平均二乗誤差が最小となる λ の値の分布 𝑁 = 500，信号対雑音比 25 dB 𝑨 ：i.i.d.ガウス行列 圧縮率(M/N) 圧縮率(M/N) 𝑨 ：部分離散フーリエ変換行列 信号密度(K/N) 信号密度(K/N) ➢ 圧縮率が0.5以上になるとλはほぼ同じ値となる ➢ 観測行列𝑨を部分離散フーリエ変換行列からi.i.d.ガウス行列に 変更しても、λ の値はほぼ同じ値となる 15/17

検討② 収束までの繰り返し回数が最小となる 𝑐 の値の分布 16/17 提案手法 𝒖𝑡+1 = 𝒛𝑡 − γ𝑨H 𝑨𝒛𝑡 − 𝒚 𝒙𝑡+1 = 𝑇γλ 𝒖𝑡+1 𝑁 = 500，信号対雑音比 25 dB 𝒛𝑡+1 = 𝒙𝑡+1 + 𝑐 𝒙𝑡+1 − 𝒙𝑡 𝑨 ：i.i.d.ガウス行列 信号対雑音比 25 dB 圧縮率(M/N) 𝑨 ：部分離散フーリエ変換行列 信号密度(K/N) ➢ i.i.dガウス行列を用いた場合、部分離散フーリエ変換行列を用いた時場合と 比べ 𝑐 の値は全体的に大きな値となる ➢ 観測行列𝑨がi.i.d.ガウス行列の場合，信号密度や圧縮率の値によって適切な 𝑐 の値はあまり変化しない

まとめ 17/17 • 光演算回路での実装に適した圧縮センシングアルゴリズム であるCMC-FISTAの性能を調べた。 適切な 𝜆 の値 適切な 𝑐 の値 検討① ソフト閾値関数を変更 従来手法とほぼ同じ値 従来手法とほぼ同じ値 検討② 観測行列𝑨を i.i.d.ガウス行列に変更 部分離散フーリエ変換 行列を用いた場合と ほぼ同じ値 部分離散フーリエ変換 行列を用いた場合と 異なる値 ➢ 観測行列 𝑨は適切な 𝑐 の値に影響を与えることが分かった。

検討① ソフト閾値関数変更による収束時の平均二乗誤差の変化 𝑁 = 500，信号密度(𝐾/𝑁) = 0.05，圧縮率(𝑀/𝑁) = 0.4，𝜆 = 0.02 提案手法 平均二乗誤差 平均二乗誤差 従来手法 繰返し回数 (𝑡) 繰返し回数 (𝑡) 18/17

パラメータ 𝛾 の決め方 19/17 λmax 𝑨H 𝑨 ：行列𝑨H 𝑨の固有値の絶対値の最大値

シミュレーション設定 シミュレーション設定 𝒙∗ ∈ ℂ𝑁 𝒚 ∈ ℂ𝑀 𝒆 ∈ ℂ𝑀 𝑨 ∈ ℂ𝑀×𝑁 20/15 原信号 ：𝒙 ∗ の非零成分~𝑁(0, 1) ：𝐾は𝒙∗ の非零成分の個数（𝐾 ≤ 𝑀 < 𝑁） 観測雑音 ：𝒆~𝑁(0, 𝜎𝑒 ) 観測行列 ：𝑨は部分離散フーリエ変換行列 もしくは、i.i.d.ガウス行列 設定値 ：𝑁 = 500 初期値 ：𝒙0 = 𝟎，𝒛0 = 𝟎 収束の定義： 1 𝑁 𝒙𝒕−𝒊 − 𝒙𝒕−𝟏−𝒊 2 2 < 10−16 ，𝑖 = 0, 1, 2, 3

加速係数 𝑎𝑡+1 の推移 21/17 ，