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

1.7K Views

September 09, 23

スライド概要

第22回情報科学技術フォーラム(FIT2023)トップコンファレンスセッション(2023/09/08)
https://onsite.gakkai-web.net/fit2023/abstract/data/html/event/event_TCS7-1.html

論文:https://ieeexplore.ieee.org/document/9932009
arXiv:https://arxiv.org/abs/2009.08545
GitHub:https://github.com/rhayakawa/predict-admm-cs

profile-image

東京農工大学大学院工学研究院 准教授

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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 .

2.

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

3.

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

4.

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

5.

研究背景 圧 縮センシング(スパース信号の復元)[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.

6.

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

7.

研究背景 最 適 化に基づくスパース信 号復元 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 に関する事前情報を活用

8.

研究背景 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.

9.

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

10.

研究目的・提案アプローチ 提 案アプローチ | 部分問題の解析 ✓ 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

11.

研究目的・提案アプローチ 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)の反 復回数

12.

研究目的・提案アプローチ 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)の反 復回数

13.

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 (最 適解が集合 𝒮 に属する)

14.

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 (最 適解が集合 𝒮 に属する)

15.

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 (最 適解が集合 𝒮 に属する)

16.

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

17.

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