メッセージ伝播法入門
第３回講義資料

一般化近似的メッセージ伝播法
広島市立大学
令和５年９月２５日～９月２６日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1ベイズ最適AMP
更新式′ �𝑡𝑡−1 + 𝑨𝑨T 𝒛𝒛𝑡𝑡−1 ; 𝑣𝑣 𝑡𝑡−1
𝜂𝜂𝒙𝒙𝑡𝑡𝑡𝑡𝒛𝒛 = 𝒚𝒚 − 𝑨𝑨�
𝒙𝒙 +𝛿𝛿
1
𝑡𝑡 = 𝜎𝜎 2 + MMSE 𝑣𝑣 𝑡𝑡−1 ,𝑣𝑣
𝛿𝛿

�𝑡𝑡+1 = 𝜂𝜂 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 ; 𝑣𝑣 𝑡𝑡 .
𝒙𝒙

AWGN観測モデル 𝑥𝑥̅𝑛𝑛 = 𝑥𝑥𝑛𝑛 + 𝑣𝑣 1/2 𝜔𝜔𝑛𝑛 ,事後平均

𝜂𝜂 𝑥𝑥̅𝑛𝑛 ; 𝑣𝑣 = 𝔼𝔼 𝑥𝑥𝑛𝑛 𝑥𝑥̅𝑛𝑛 , 𝑣𝑣 .

𝒛𝒛𝑡𝑡−1 ,𝜔𝜔𝑛𝑛 ∼ 𝒩𝒩 0, 1 .

最小平均二乗誤差（MMSE） MMSE 𝑣𝑣 = 𝔼𝔼 𝑥𝑥𝑛𝑛 − 𝜂𝜂 𝑥𝑥̅𝑛𝑛 ; 𝑣𝑣
信号の事前分布が既知である必要がある。

2.
2

AMP[3-1]
更新式′𝑡𝑡−1 + 𝑨𝑨T 𝒛𝒛𝑡𝑡−1�𝜂𝜂
𝒙𝒙
𝑡𝑡−1𝒙𝒙𝑡𝑡 +𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨�𝛿𝛿

初期値

�𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 .
𝒙𝒙
𝒙𝒙0 = 𝟎𝟎,𝒛𝒛𝑡𝑡−1 ,𝒛𝒛−1 = 𝟎𝟎.

Denoiserを関数列{𝜂𝜂𝑡𝑡 }に一般化[3-1] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressedsensing,” Proc. Nat. Acad. Sci., vol. 106, no. 45, pp. 18914–18919, Nov. 2009.
3オンサーガ（Onsager）項
オンサーガ項大システム極限において、誤差の漸近ガウス性を成立させるための補正項

𝜉𝜉𝑡𝑡−1 𝑡𝑡−1
𝑡𝑡𝑡𝑡𝒛𝒛 = 𝒚𝒚 − 𝑨𝑨�
𝒙𝒙 +𝒛𝒛 ,𝛿𝛿′�𝑡𝑡−1 + 𝑨𝑨T 𝒛𝒛𝑡𝑡−1
𝜉𝜉𝑡𝑡−1 = 𝜂𝜂𝑡𝑡−1𝒙𝒙

L. Onsager (1903—1976)
オンサーガ相反関係（不可逆過程の熱力学の基礎）を発見した貢献により、1968年にノーベル化学賞を受賞
名前の由来
項の名前は、液体論に関わるオンサーガの1936年の論文で提案された方法論に由来する。
物理学者は、彼の方法論に従って導出される反跳場（reaction field)をオンサーガ反跳場と呼ぶ。
4

オンサーガのキャビティ（Cavity）アプローチキャビティ場（Cavity field）
𝑛𝑛番目の信号を取り除いた𝑀𝑀 × (𝑁𝑁 − 1)キャビティ観測システムにおいて、干渉除去後に残っている干渉雑音AWGNとみなせることを仮定する。

反跳場（Reaction field）
キャビティ観測システムに𝑛𝑛番目の信号を追加したときに、追加した信号がキャビティ場に与える無視できない影響
𝑨𝑨T 𝛿𝛿 −1 𝜉𝜉𝑡𝑡−1 𝒛𝒛𝑡𝑡−1𝑛𝑛 のことだと思えばよい。

�𝑡𝑡 + 𝑨𝑨T 𝒚𝒚 − 𝑨𝑨�
𝒙𝒙𝑡𝑡 𝑛𝑛 − 𝑥𝑥𝑛𝑛 に反跳場による影響の補正を真の残留干渉 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 𝑛𝑛 − 𝑥𝑥𝑛𝑛 は、𝑥𝑥𝑛𝑛 と独立なキャビティ場とみなせるはず。
加えた 𝒙𝒙5

Denoiserの例
Soft thresholding (ST)𝜂𝜂𝑡𝑡 𝑥𝑥 = 𝜂𝜂ST 𝑥𝑥; 𝜃𝜃𝑡𝑡

for 𝑥𝑥 > 𝜃𝜃𝑡𝑡
for 𝑥𝑥 ≤ 𝜃𝜃𝑡𝑡
for 𝑥𝑥 < −𝜃𝜃𝑡𝑡 .

𝑥𝑥 − 𝜃𝜃𝑡𝑡
0=�
𝑥𝑥 + 𝜃𝜃𝑡𝑡

ミニマックス最適性[3-2]任意の𝑝𝑝, 𝑞𝑞 > 0に対して、𝑟𝑟ST 𝑎𝑎 = infsupsup𝜃𝜃𝑡𝑡

𝑟𝑟ST (𝑎𝑎)lim= 1.
𝑎𝑎↓0 𝑟𝑟opt (𝑎𝑎)𝜃𝜃 𝑝𝑝 𝑥𝑥 : 𝔼𝔼 𝑥𝑥 𝑝𝑝 1/𝑝𝑝 ≤𝑎𝑎𝑛𝑛𝑛𝑛𝑟𝑟opt 𝑎𝑎 = inf−𝜃𝜃𝑡𝑡𝜂𝜂 𝑝𝑝 𝑥𝑥 : 𝔼𝔼 𝑥𝑥 𝑝𝑝 1/𝑝𝑝 ≤𝑎𝑎𝑛𝑛𝑛𝑛

𝔼𝔼 𝑥𝑥𝑛𝑛 − 𝜂𝜂ST 𝑥𝑥𝑛𝑛 + 𝑣𝑣𝜔𝜔𝑛𝑛 ; 𝜃𝜃𝔼𝔼 𝑥𝑥𝑛𝑛 − 𝜂𝜂 𝑥𝑥𝑛𝑛 + 𝑣𝑣𝜔𝜔𝑛𝑛[3-2] D. L. Donoho and I. M. Johnstone, “Minimax risk over 𝑙𝑙𝑝𝑝 -balls for 𝑙𝑙𝑞𝑞 -error,”
Probab. Theory Relat. Fields, vol. 99, no. 2, pp. 277-303, Jun. 1994.

𝑞𝑞.

𝑞𝑞,

6

ミニマックス最適性の意義
モーメント制約
𝑝𝑝 𝑥𝑥𝑛𝑛 = 1 − 𝜌𝜌 𝛿𝛿 𝑥𝑥𝑛𝑛 + 𝜌𝜌𝜌𝜌 𝑥𝑥𝑛𝑛 ,∫ 𝑥𝑥 𝑝𝑝 𝜋𝜋 𝑥𝑥 𝑑𝑑𝑑𝑑 = 𝑀𝑀𝑝𝑝,𝜌𝜌 < ∞.

𝜌𝜌 < 𝑎𝑎𝑝𝑝 /𝑀𝑀𝑝𝑝,𝜌𝜌 を満たす分布は、モーメント制約を満たす。

𝑀𝑀𝑝𝑝,𝜌𝜌 が𝜌𝜌に依存しない信号分布では、信号密度𝜌𝜌が0に収束する。

ミニマックス最適性• モーメント制約を満たす分布の中で最悪な信号分布を想定• パラメータ𝜃𝜃を最適値に設定• ST関数は𝐿𝐿𝑞𝑞 誤差を最小化

最適解の唯一性は主張していない。
7状態発展法[3-3]状態発展方程式𝑣𝑣̅ 𝑡𝑡 = 𝜎𝜎 2 +1
Ψ 𝑣𝑣̅ 𝑡𝑡−1 , 𝜆𝜆 ,𝛿𝛿𝑣𝑣̅ 0 = 1.

Ψ 𝑣𝑣, 𝜆𝜆 = 𝔼𝔼 𝑥𝑥1 − 𝜂𝜂ST 𝑥𝑥1 + 𝑣𝑣𝜔𝜔1 ; 𝜆𝜆 𝑣𝑣
閾値を𝜃𝜃𝑡𝑡 = 𝜆𝜆 𝑣𝑣̅ 𝑡𝑡 とおいた。

2 .

誤差の漸近評価1
�𝑡𝑡 2 = Ψ 𝑣𝑣̅ 𝑡𝑡−1 , 𝜆𝜆 .
𝔼𝔼 𝒙𝒙 − 𝒙𝒙lim
𝑀𝑀=𝛿𝛿𝛿𝛿→∞ 𝑁𝑁

状態発展法の解説は、第４～６回講義資料を参照[3-3] M. Bayati and A. Montanari, “The dynamics of message passing on dense graphs, with applications
to compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 764–785, Feb. 2011.
8数値的評価信号密度𝜌𝜌のBG事前分布、𝜎𝜎 2 = 0、𝛿𝛿 = 0.65、最適な𝜆𝜆9一般化線形観測モデル
観測モデル
𝒚𝒚 = 𝑓𝑓 𝒛𝒛, 𝒘𝒘 ,𝒛𝒛 = 𝑨𝑨𝑨𝑨,

例１：AWGN観測

𝒘𝒘 ∼ 𝒩𝒩 𝟎𝟎, 𝜎𝜎 2 𝑰𝑰𝑀𝑀

𝑓𝑓 𝑧𝑧, 𝑤𝑤 = 𝑧𝑧 + 𝑤𝑤

例２：非理想的増幅器

𝜃𝜃𝑓𝑓 𝑧𝑧, 𝑤𝑤 = �𝑧𝑧 + 𝑤𝑤−𝜃𝜃

例３：量子化for 𝑧𝑧 + 𝑤𝑤 > 𝜃𝜃for 𝑧𝑧 + 𝑤𝑤 ≤ 𝜃𝜃for 𝑧𝑧 + 𝑤𝑤 < −𝜃𝜃

1 for 𝑧𝑧 + 𝑤𝑤 ≥ 0𝑓𝑓 𝑧𝑧, 𝑤𝑤 = �−1 for 𝑧𝑧 + 𝑤𝑤 < 010一般化AMP（GAMP）[3-4]更新式𝜉𝜉in,𝑡𝑡−1
𝒙𝒙𝑡𝑡 +𝒛𝒛𝑡𝑡 = 𝑨𝑨�𝒛𝒛� 𝑡𝑡−1𝛿𝛿𝜉𝜉out,𝑡𝑡−1𝒛𝒛� 𝑡𝑡 = 𝜂𝜂out,𝑡𝑡 𝒛𝒛𝑡𝑡 , 𝒚𝒚 ,𝜕𝜕𝜉𝜉out,𝑡𝑡 =𝜂𝜂out,𝑡𝑡 𝒛𝒛𝑡𝑡 , 𝒚𝒚𝜕𝜕𝑧𝑧𝑡𝑡�𝑡𝑡+1 = 𝜂𝜂in,𝑡𝑡 𝒙𝒙𝑡𝑡 ,𝒙𝒙′𝜉𝜉in,𝑡𝑡 = 𝜂𝜂in,𝑡𝑡𝒙𝒙𝑡𝑡

�𝑡𝑡 −𝒙𝒙𝑡𝑡 = 𝒙𝒙
初期値

�0 = 𝟎𝟎,𝒙𝒙

1

𝜉𝜉out,𝑡𝑡𝑨𝑨T 𝒛𝒛� 𝑡𝑡 ,𝒛𝒛� −1 = 𝟎𝟎

[3-4] S. Rangan, “Generalized approximate message passing for estimation with random linear mixing,”
in Proc. 2011 IEEE Int. Symp. Inf. Theory, Saint Petersburg, Russia, Aug. 2011, pp. 2168–2172.
11

状態発展法[3-4]̅及び𝜁𝜁𝑡𝑡̅ 、𝜎𝜎𝑡𝑡2 を用いて状態発展法で定まるパラメータ𝜉𝜉out,𝑡𝑡
𝜂𝜂in,𝑡𝑡 用の𝜁𝜁𝑡𝑡̅𝑋𝑋𝑡𝑡 =𝑋𝑋 + 𝐻𝐻𝑡𝑡 ,𝐻𝐻𝑡𝑡 ∼ 𝒩𝒩 0, 𝜎𝜎𝑡𝑡2
̅𝜉𝜉out,𝑡𝑡
AWGN観測モデル
𝑋𝑋𝑡𝑡 を観測したときに、未知の信号𝑋𝑋 ∼ 𝑥𝑥1 を推定せよ。

𝜂𝜂out,𝑡𝑡 用の

AWGN観測モデル

𝑍𝑍, 𝑍𝑍𝑡𝑡 ∼ 𝒩𝒩

𝑌𝑌 = 𝑓𝑓 𝑍𝑍, 𝑊𝑊 ,𝑍𝑍0 = 0,𝑊𝑊 ∼ 𝒩𝒩(0, 𝜎𝜎 2 )𝜁𝜁𝑡𝑡̅
𝑍𝑍𝑡𝑡 =𝑍𝑍 + 𝐵𝐵𝑡𝑡̅𝜉𝜉out,𝑡𝑡2]
𝔼𝔼[𝑋𝑋10,0 𝛿𝛿 𝔼𝔼 𝑋𝑋𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1

𝔼𝔼 𝑋𝑋𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−12
𝔼𝔼 𝜂𝜂in,𝑡𝑡−1𝑋𝑋𝑡𝑡−1

𝑍𝑍𝑡𝑡 と𝑌𝑌を観測したときに、信号𝑍𝑍を推定せよ。

12状態発展法[3-4]状態発展方程式̅𝜉𝜉out,𝑡𝑡= 𝔼𝔼

前述の確率変数𝑍𝑍𝑡𝑡 、𝑍𝑍、𝑊𝑊を用いて、

𝜕𝜕𝜂𝜂out,𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑓𝑓 𝑍𝑍, 𝑊𝑊𝜕𝜕𝑍𝑍𝑡𝑡𝜕𝜕̅𝜂𝜂out,𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑓𝑓 𝑍𝑍, 𝑊𝑊𝜁𝜁𝑡𝑡 = −𝔼𝔼𝜕𝜕𝜕𝜕,2𝔼𝔼𝜂𝜂𝑍𝑍𝑡𝑡 , 𝑓𝑓(𝑍𝑍, 𝑊𝑊)out,𝑡𝑡2, 𝜎𝜎𝑡𝑡 =̅2𝜉𝜉out,𝑡𝑡

これらを用いて前述の確率変数𝑋𝑋𝑡𝑡 を定め、𝑍𝑍𝑡𝑡+1 を更新する。

誤差の漸近評価122
�𝑡𝑡𝔼𝔼 𝒙𝒙 − 𝒙𝒙lim= 𝔼𝔼 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 − 𝑋𝑋 .
𝑀𝑀=𝛿𝛿𝛿𝛿→∞ 𝑁𝑁
状態発展法の解説は、第４～６回講義資料を参照

13

ベイズ最適なDenoiser𝜂𝜂in,𝑡𝑡 の場合

𝜂𝜂in,𝑡𝑡 𝑋𝑋𝑡𝑡 = 𝔼𝔼 𝑋𝑋 𝑋𝑋𝑡𝑡

AMPの場合と同様に定めればよい。
𝜂𝜂out,𝑡𝑡 の場合

AWGN観測𝑋𝑋𝑡𝑡 の信号対雑音比(SNR)を最大化せよ。
snr𝑡𝑡 =

𝜁𝜁𝑡𝑡̅̅𝜉𝜉out,𝑡𝑡2

1
𝜁𝜁𝑡𝑡2̅
2 =2𝜎𝜎𝑡𝑡
𝔼𝔼 𝜂𝜂out,𝑡𝑡
𝑍𝑍𝑡𝑡 , 𝑓𝑓(𝑍𝑍, 𝑊𝑊)14

補題３.１[3-5]𝑊𝑊 ∼ 𝒩𝒩(0, 𝜎𝜎 2 )𝜁𝜁𝑡𝑡̅
𝑍𝑍𝑡𝑡 =𝑍𝑍 + 𝐵𝐵𝑡𝑡̅𝜉𝜉out,𝑡𝑡

AWGN観測モデル 𝑌𝑌 = 𝑓𝑓 𝑍𝑍, 𝑊𝑊 ,𝑍𝑍0 = 0,𝑍𝑍𝑡𝑡 と𝑌𝑌を観測したときの𝑍𝑍の事後平均推定量𝑍𝑍̂𝑡𝑡 を以下で定義する。

𝑍𝑍̂𝑡𝑡 𝑧𝑧𝑡𝑡 , 𝑦𝑦 =∫ 𝑧𝑧𝑝𝑝𝑌𝑌|𝑍𝑍∫ 𝑝𝑝𝑌𝑌|𝑍𝑍𝑧𝑧−𝑧𝑧𝑡𝑡 2−𝑦𝑦 𝑧𝑧 𝑒𝑒 2𝑣𝑣𝑡𝑡 𝑑𝑑𝑑𝑑𝑧𝑧−𝑧𝑧𝑡𝑡 2−𝑦𝑦 𝑧𝑧 𝑒𝑒 2𝑣𝑣𝑡𝑡 𝑑𝑑𝑑𝑑

, 𝑣𝑣𝑡𝑡 =𝔼𝔼 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 − 𝑋𝑋𝛿𝛿2

ただし、𝑝𝑝𝑌𝑌|𝑍𝑍 は𝑍𝑍が与えられたときの𝑌𝑌の確率密度関数を表す。

任意定数𝐶𝐶 ∈ ℝに対して、以下の𝜂𝜂out,𝑡𝑡 はsnr𝑡𝑡 を最大化する。
𝑍𝑍𝑡𝑡 − 𝑍𝑍̂𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑌𝑌𝜂𝜂out,𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑌𝑌 = 𝐶𝐶𝑣𝑣𝑡𝑡[3-5] K. Takeuchi, "Decentralized generalized approximate message-passing for tree-structurednetworks," submitted to 2024 IEEE Int. Conf. Acoust. Speech Signal Process., Seoul, Korea, Apr. 2024.
15

𝑍𝑍の条件付き分布

事後平均推定量の性質𝔼𝔼 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 − 𝑋𝑋
1𝔼𝔼 𝑍𝑍𝑍𝑍𝑡𝑡 = 𝔼𝔼 𝑋𝑋𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1𝛿𝛿

12= 𝔼𝔼 𝜂𝜂in,𝑡𝑡−1𝑋𝑋𝑡𝑡−1𝛿𝛿

𝑍𝑍𝑡𝑡 が与えられたときの𝑍𝑍は次のように表現できる。
証明

𝑍𝑍 ∼ 𝑍𝑍𝑡𝑡 + 𝑁𝑁𝑡𝑡 ,= 0から、= 𝔼𝔼 𝑍𝑍𝑡𝑡2

𝑁𝑁𝑡𝑡 ∼ 𝒩𝒩(0, 𝑣𝑣𝑡𝑡 )以下の𝑍𝑍と𝑍𝑍𝑡𝑡 に関する共分散を確かめよ。

𝔼𝔼 𝑍𝑍𝑍𝑍𝑡𝑡 = 𝔼𝔼 (𝑍𝑍𝑡𝑡 + 𝑁𝑁𝑡𝑡 )𝑍𝑍𝑡𝑡 = 𝔼𝔼 𝑍𝑍𝑡𝑡2
12222
𝔼𝔼 𝑍𝑍 = 𝔼𝔼 𝑍𝑍𝑡𝑡 + 𝔼𝔼 𝑁𝑁𝑡𝑡 = 𝔼𝔼 𝜂𝜂in,𝑡𝑡−1𝑋𝑋𝑡𝑡−1 + 𝑣𝑣𝑡𝑡𝛿𝛿
112= 𝔼𝔼 𝑋𝑋 + 2𝔼𝔼 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 𝜂𝜂in,𝑡𝑡−1 𝑋𝑋𝑡𝑡−1 − 𝑋𝑋 = 𝔼𝔼 𝑋𝑋 2𝛿𝛿𝛿𝛿
∎

16

線形観測の場合
𝑓𝑓 𝑧𝑧, 𝑤𝑤 = 𝑧𝑧 + 𝑤𝑤の場合にベイズ最適な𝜂𝜂out,𝑡𝑡 を導出する。
𝑌𝑌 = 𝑍𝑍 + 𝑊𝑊および𝑍𝑍 ∼ 𝒩𝒩(𝑍𝑍𝑡𝑡 , 𝑣𝑣𝑡𝑡 )から𝑣𝑣𝑡𝑡
̂𝑍𝑍𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑌𝑌 = 𝑍𝑍𝑡𝑡 +(𝑌𝑌 − 𝑍𝑍𝑡𝑡 )確かめよ。
2
𝑣𝑣𝑡𝑡 + 𝜎𝜎𝐶𝐶
それゆえ 𝜂𝜂out,𝑡𝑡 𝑍𝑍𝑡𝑡 , 𝑌𝑌 =(𝑍𝑍𝑡𝑡 − 𝑌𝑌)
𝐶𝐶は任意
2𝑣𝑣𝑡𝑡 + 𝜎𝜎𝜕𝜕𝜂𝜂out,𝑡𝑡 𝒛𝒛𝑡𝑡 , 𝒚𝒚𝜉𝜉out,𝑡𝑡 =𝜕𝜕𝑧𝑧𝑡𝑡𝐶𝐶=,2𝑣𝑣𝑡𝑡 + 𝜎𝜎𝜁𝜁𝑡𝑡̅ =𝐶𝐶𝑣𝑣𝑡𝑡 + 𝜎𝜎 2̅ベイズ最適なGAMPでは、一般に𝜉𝜉out,𝑡𝑡= 𝜁𝜁𝑡𝑡̅ [3-4]が言える。
𝒛𝒛� 𝑡𝑡𝜂𝜂out,𝑡𝑡 𝒛𝒛𝑡𝑡 , 𝒚𝒚𝜉𝜉in,𝑡𝑡−1 𝒛𝒛� 𝑡𝑡−1== 𝒛𝒛𝑡𝑡 − 𝒚𝒚 = 𝑨𝑨�𝒙𝒙𝑡𝑡 − 𝒚𝒚 +𝜉𝜉out,𝑡𝑡𝜉𝜉out,𝑡𝑡𝛿𝛿 𝜉𝜉out,𝑡𝑡−1
線形観測に対するGAMPはAMPに帰着する。

17