ADMMに基づく圧縮センシングの漸近特性予測

20 2 3/ 09/08 第2 2回 情 報 科 学 技 術 フ ォ ー ラム （FI T2023 ） @大阪公立大学 ト ップ コン フ ァ レンスセ ッ シ ョ ン A DM Mに基づく圧 縮センシングの 漸 近 特 性 予測 大 阪大学 大 学 院基 礎工 学 研 究 科 助教 早川 諒 （ ha yak aw a . r yo .e s @o s aka- u . ac .j p ） 発表 論 文 ： R. H a y aka wa , “As y m p t o t i c p e rfo rm ance p re dict io n fo r ADM M -b a se d c o mp res s e d s e nsi ng,” I EEE Tran sactio n s on S i g nal Pro c e ss i n g, v ol . 70, p p. 5 1 9 4 -5 2 0 7 , 2 0 2 2 .

1/12 本 発 表の概 要 凸最 適化のためのADM M（Alternat ing Direction Method of Multipliers） という 反 復アルゴリズムによってスパース信号を復元するときの， 推 定値の誤差のふるまいを解析する試み ADMMによる復元 更新 未知の スパース信号 観測 観測値 復元 初期値 更新 暫定解 … 本 研 究の解 析対象（ 全体） 従 来の解 析 対 象（結 果のみ） 最適解 （復元結果）

目次 ✦ 研究背景 ✦ 研 究目的・提案アプローチ ✦ 課題 ✦ まとめ

研究背景 2/12 信号復元 ✓ ノイズや変換で劣化した観測値から， 未知の信号（音，画像，電波，脳波，…）を復元 → データから価値のある情報を抽出するための基盤となる数理的技術 未知信 号 観測 ス パース 画像 動画 復元 観測値

研究背景 圧 縮センシング（スパース信号の復元）[1] 3/12 ✓ 圧縮センシング・スパースモデリング： データや信号に内在するスパース性を活用した情報処理の枠組み ほとんどの値が0であるという性 質 応用例：✦ MRI画像再 構成 [ 2 ] （ M a gn et ic Re so na nc e I m a gi n g ） ✦ 無線通 信路 推定 [ 3 ] [1] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006. [2] M. Lustig, D. L. Donoho, J. M. Santos, and J. M. Pauly, “Compressed sensing MRI,” IEEE Signal Process. Mag., vol. 25, no. 2, pp. 72–82, Mar. 2008. [3] K. Hayashi, M. Nagahara, and T. Tanaka, “A user’s guide to compressed sensing for communications systems,” IEICE Trans. Commun., vol. E96-B, no. 3, pp. 685–712, Mar. 2013.

研究背景 4/12 圧 縮センシングの観 測モデル ✓ スパースな（ 零 成 分が多い）未知ベクトル x ∈ ℝN を その線 形 観 測 y = Ax + v ∈ ℝM から推定 (M < N) N M y = A 非零 成分 x + v 雑音 推 定 値 x̂

研究背景 最 適 化に基づくスパース信 号復元 5/12 N ✓ ℓ1 正 則 化 ∥s∥1 = ∑ |sn| （ sn： s の第 n 成分）を用いた n=1 最適 化 問題を解くと，スパースな（零 成分が多い）推定値を得られる N M y = A x + v 雑音 非 零 成分 パラメータ 1 推 定値 x̂ = arg min ∥y − As∥22 + λ ∥s∥1 {2 } s∈ℝN データ忠 実性：観 測 y = Ax + v を活用 正則 化： x に関する事前情報を活用

研究背景 6/12 推 定 値の誤 差の解 析 ✓ 1 推 定値 x̂ = arg min ∥y − As∥22 + λ ∥s∥1 の誤差を知りたい {2 } s∈ℝN 解 析のアプローチ ✦ メッセージ伝 播 法に基づく解 析 [ 4 , 5 ] ❖ ✦ 1 例：MS E（M e an Squa re d Error） ∥x̂ − x∥22 N メッセージ伝 播アルゴリズムの特 性解 析 → 最適化問題との関係を議論 CGM T（Con vex ❖ Gaussian Min-max Theorem）に基づく解 析 [6, 7] 最適 化問 題を少し変 形したものを解析 → 漸近的な誤差を導出 [4] D. L. Donoho, A. Maleki, and A. Montanari, “The noise-sensitivity phase transition in compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 6920–6941, Oct. 2011. [5] M. Bayati and A. Montanari, “The LASSO risk for Gaussian matrices,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 1997–2017, Apr. 2012. [6] C. Thrampoulidis, S. Oymak, and B. Hassibi, “Regularized linear regression: A precise analysis of the estimation error,” in Proc. COLT, Jun. 2015, pp. 1683–1709. [7] C. Thrampoulidis, E. Abbasi, and B. Hassibi, “Precise error analysis of regularized M-estimators in high dimensions,” IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5592–5628, Aug. 2018.

研究目的・提案アプローチ 研 究目的 ｜ 最 適化アルゴリズムの解析 ✓ 7/12 これまでのC GM Tを用いた解析では，最適解が主な対象 → 最 適 化アルゴリズム中の暫 定的な解の特 性は？ 最適 化アルゴリズムのふるまい 最 適解 （これまでの解析の対 象） 目的関 数の等 高線 暫 定解 暫 定 解を解 析することで， 最 適 化アルゴリズムの ふるまいを調べたい アルゴリズムの理解 ✦ パラメータ調整 などへの応用を期 待 ✦ 初期値

研究目的・提案アプローチ 提 案アプローチ ｜ 部分問題の解析 ✓ 8/12 A DM Mによる暫定 解が別の部 分問 題の解であることを利用して， 暫 定解のM S E（ M e an S qu are d Err or ）を解析 先 行 研究 最適解 最 適 解の MS E C G MT 本研究 暫定解 初期 値 A DM Mの動き 部 分問題 による 特徴づけ C G MT 暫 定 解の M SE

研究目的・提案アプローチ 9/12 シミュレーション結果 ✓ N（ 未知ベクトルの次元 ）が十 分大きい場合， 各 反復で実際のM SEと漸 近的 MSEの予測値が近い 100 empirical (N = 50) empirical (N = 100) M SE MSE 10°1 10°2 empirical (N = 500) empirical (N = 1000) prediction asymptotic MSE of optimizer 実 際のMS E 漸 近 的 MSEの 予測値 10°3 最 適 解の漸近 的 M SEに収 束 10°4 5 10 15 20 25 30 最 適 解の0 number of iterations 漸 近的 MSE 復元アルゴリズム（ ADM M）の反 復回数

研究目的・提案アプローチ 9/12 シミュレーション結果 ✓ N（ 未知ベクトルの次元 ）が十 分大きい場合， 各 反復で実際のM SEと漸 近的 MSEの予測値が近い 100 empirical (N = 50) empirical (N = 100) empirical (N = 500) M SE MSE 10°1 empirical (N = 1000) prediction asymptotic MSE of optimizer 10°2 実 際のMS E 漸 近 的 MSEの 予測値 10°3 10°4 最 適 解の漸近 的 M SEに収 束 最 適化アルゴリズムの復元 誤差を予測 可能 5 10 15 20 25 30 → パラメータ設計・ アルゴリズム開 発などへの応用が期待（？） number of iterations 最 適 解の0 漸 近的 MSE 復元アルゴリズム（ ADM M）の反 復回数

10/12 【 余 談 】 C G MTのイメージ ✓ 主 問題（ P ri m ar y O p t im iza ti on, PO）と 補 助問 題（ A u xil i a r y O p t im iza ti on, AO）を関連付ける定理 （PO） （A O） min max { u 𝖳Ge + ξ(e, u)} min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} e∈𝒮e u∈𝒮u e∈𝒮e u∈𝒮u 𝒮 𝒮 ϕ̄𝒮c ̂ eΦ e ̂ ∈ 𝒮) = 1 lim Pr (eΦ M, N→∞ ϕ̄ eϕ̂ e 条件： M, N → ∞ で ϕ̄ < ϕ̄𝒮c （最 適解が集合 𝒮 に属する）

10/12 【 余 談 】 C G MTのイメージ ξ : ℝN × ℝM → ℝ： e に関しては凸関数 ， ✓ 主 問題 （ P riMm ar y O p t im iza ti on, PO）と u に関しては凹関 数 N 𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ： コンパクト集合 補 助問 題（ A u xil i a r y O p t im iza ti on, AO）を関連付ける定理 G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝN： 各成分が独立に標準ガウス分布 （PO） （A O） min max { u 𝖳Ge + ξ(e, u)} e∈𝒮e u∈𝒮u min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} e∈𝒮e u∈𝒮u 𝒮 𝒮 ϕ̄𝒮c ̂ eΦ e ̂ ∈ 𝒮) = 1 lim Pr (eΦ M, N→∞ ϕ̄ eϕ̂ e 条件： M, N → ∞ で ϕ̄ < ϕ̄𝒮c （最 適解が集合 𝒮 に属する）

10/12 【 余 談 】 C G MTのイメージ ξ : ℝN × ℝM → ℝ： e に関しては凸関数 ， ✓ 主 問題 （ P riMm ar y O p t im iza ti on, PO）と u に関しては凹関 数 N 𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ： コンパクト集合 補 助問 題（ A u xil i a r y O p t im iza ti on, AO）を関連付ける定理 G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝN： 各成分が独立に標準ガウス分布 （PO） （A O） min max { u 𝖳Ge + ξ(e, u)} e∈𝒮e u∈𝒮u min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} e∈𝒮e u∈𝒮u 𝒮 直 感的には… 𝒮 補 助 問題（A O ）の解が高 確 率で集合 𝒮 に属する → 主問 題（ PO ）の解も高 確 率で集合 𝒮 に属する ϕ̄𝒮c ϕ̄ 主 問題（ PO ）の代わりに補 助問 題（ AO ）を解析してもよい e ̂ ̂ eΦ e ̂ ∈ 𝒮) = 1 lim Pr (eΦ M, N→∞ eϕ 条件： M, N → ∞ で ϕ̄ < ϕ̄𝒮c （最 適解が集合 𝒮 に属する）

11/12 課題 ✓ 暫 定解の特 性 予 測の際はCG M Tを繰り返し適用 → 厳 密な証 明にはCG M Tの拡 張が必 要 （ 実験 的にはよく予測できている） ✓ CGM Tによる解析自体にいくつか仮定が必要 観測 率 Δ = M/N が一定で M, N → ∞ となる極 限を考える N M y = A x + v 各成 分は独 立に平均 0・分散 1/N のガウス分布に従う

12/12 まとめ 凸最 適化のためのADM M（Alternat ing Direction Method of Multipliers）という 反 復アルゴリズムによってスパース信号を復元するときの， 推 定値の誤差のふるまいを予測する手法を提 案 ADMMによる復元 更新 未知の スパース信号 観測 観測値 復元 初期値 更新 暫定解 … 本 研 究の解 析対象（ 全体） 従 来の解 析 対 象（結 果のみ） 最適解 （復元結果）