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

メッセージ伝播法の発展的内容
広島市立大学
令和４年９月２６日～９月２８日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1

AMPの利点と欠点
AMPの利点• 計算量は、干渉除去に整合フィルタを使うため、最小限である。
反復当たりの計算量：𝒪𝒪(𝑀𝑀𝑀𝑀)• 観測行列の成分が独立で𝒩𝒩(0,1/𝑀𝑀)に従う場合、状態発展方程式の不動点が唯一ならば、AMPは大システム極限でベイズ最適な性能を達成する。[3-4, 1-7, 1-8]
AMPの欠点
悪条件[7-1]や非ゼロ平均[7-2]など、観測行列が非i.i.d.行列の場合、AMPは収束しない。
[7-1] S. Rangan, P. Schniter, A. Fletcher, and S. Sarkar, “On the convergence of approximate message
passing with arbitrary matrices,” IEEE Trans. Inf. Theory, vol. 65, no. 9, pp. 5339–5351, Sep. 2019.
[7-2] F. Caltagirone, L. Zdeborová, and F. Krzakala, “On convergence of approximate message passing,”
in Proc. 2014 IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jul. 2014, pp. 1812–1816.
2

Orthogonal/Vector AMP[7-3, 7-4]
モジュールAオンサーガ補正
𝒙𝒙A,𝑡𝑡 − 𝜉𝜉A,𝑡𝑡 𝒙𝒙B→A,𝑡𝑡𝒙𝒙A,𝑡𝑡 = 𝒙𝒙B→A,𝑡𝑡 + 𝑾𝑾T𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡 , 𝒙𝒙,A→B,𝑡𝑡 =1 − 𝜉𝜉A,𝑡𝑡1𝜉𝜉A,𝑡𝑡 = Tr 𝑰𝑰 − 𝑾𝑾T𝑡𝑡 𝑨𝑨𝜉𝜉A,𝑡𝑡 𝑣𝑣B→A,𝑡𝑡𝑁𝑁𝑣𝑣A→B,𝑡𝑡 =1 − 𝜉𝜉A,𝑡𝑡
線形フィルタDenoiser

モジュールB

𝒙𝒙B,𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 (𝒙𝒙A→B,𝑡𝑡 ),𝜉𝜉B,𝑡𝑡 = ⟨𝜂𝜂𝜂𝑡𝑡 (𝒙𝒙A→B,𝑡𝑡 )⟩オンサーガ補正
𝒙𝒙B,𝑡𝑡+1 − 𝜉𝜉B,𝑡𝑡 𝒙𝒙A→B,𝑡𝑡
𝒙𝒙B→A,𝑡𝑡+1 =,1 − 𝜉𝜉B,𝑡𝑡
𝜉𝜉B,𝑡𝑡 𝑣𝑣A→B,𝑡𝑡𝑣𝑣B→A,𝑡𝑡+1 =1 − 𝜉𝜉B,𝑡𝑡[7-3] J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020–2033, Jan. 2017.
[7-4] S. Rangan, P. Schniter, and A. K. Fletcher, “Vector approximate message passing,”
IEEE Trans. Inf. Theory, vol. 65, no. 10, pp. 6664–6684, Oct. 2019.

3

OAMP/VAMP
ベイズ最適なOAMP/VAMP
以下の線形MMSEフィルタとベイズ最適なdenoiserを使用
2T −1

𝑾𝑾𝑡𝑡 = 𝑣𝑣B→A,𝑡𝑡 𝜎𝜎 𝑰𝑰 + 𝑣𝑣B→A,𝑡𝑡 𝑨𝑨𝑨𝑨

関連アルゴリズム𝑨𝑨• ベイズ最適なOAMP/VAMPは、期待値伝播法[7-5]の大システム近似[7-6, 7-7]と等価である。
• OAMP/VAMPの特別な場合は、[7-8]で最初に提案された。
[7-5] T. P. Minka, “Expectation propagation for approximate Bayesian inference,” in Proc. 17th Conf. Uncertainty
Artif. Intell., Seattle, WA, USA, Aug. 2001, pp. 362–369.
[7-6] J. Céspedes, P. M. Olmos, M. Sánchez-Fernández, and F. Perez-Cruz, “Expectation propagation detection
for high-order high-dimensional MIMO systems,” IEEE Trans. Commun., vol. 62, no. 8, pp.2840–2849, Aug. 2014.
[7-7] K. Takeuchi, “Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariantmeasurements,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 368–386, Jan. 2020.
[7-8] M. Opper and O. Winther, “Expectation consistent approximate inference,” J. Mach. Learn. Res.,
vol. 6, pp. 2177–2204, Dec. 2005.
4

行列の直交不変性
𝑿𝑿を任意のランダム行列とする。

左直交不変性𝚽𝚽𝑿𝑿が定義可能で、 𝑿𝑿と独立なすべての直交行列𝚽𝚽に対して、以下の条件が成立するとき、𝑿𝑿は左直交不変であると言う。

右直交不変性𝑿𝑿 ∼ 𝚽𝚽𝑿𝑿. （両辺の分布が同一）𝑿𝑿𝚿𝚿が定義可能で、 𝑿𝑿と独立なすべての直交行列𝚿𝚿に対して、以下の条件が成立するとき、𝑿𝑿は右直交不変であると言う。
𝑿𝑿 ∼ 𝑿𝑿𝚿𝚿.

5

状態発展法による解析
状態発展方程式[7-4, 7-7]
モジュールA1̅Tr 𝑰𝑰 − 𝑾𝑾T𝑡𝑡 𝑨𝑨 ,𝜉𝜉A,𝑡𝑡 = lim
𝑀𝑀=𝛿𝛿𝛿𝛿→∞ 𝑁𝑁モジュールB̅ = 𝔼𝔼 𝜂𝜂′𝑡𝑡 𝑥𝑥1 + 𝜔𝜔1 ,𝜉𝜉B,𝑡𝑡𝜔𝜔1 ∼ 𝒩𝒩 0, 𝑣𝑣̅A→B,𝑡𝑡 .

右直交不変な観測行列の場合

̅ 𝑣𝑣̅B→A,𝑡𝑡
𝜉𝜉A,𝑡𝑡𝑣𝑣̅A→B,𝑡𝑡 =̅
1 − 𝜉𝜉A,𝑡𝑡

̅ 𝑣𝑣̅A→B,𝑡𝑡
𝜉𝜉B,𝑡𝑡𝑣𝑣̅B→A,𝑡𝑡+1 =̅
1 − 𝜉𝜉B,𝑡𝑡

大システム極限で、12𝒙𝒙 − 𝒙𝒙B,𝑡𝑡+1 → 𝔼𝔼 𝑥𝑥1 − 𝜂𝜂𝑡𝑡 (𝑥𝑥1 + 𝜔𝜔1 ) 2 almost surely.
𝑁𝑁6

OAMP/VAMPの利点と欠点
OAMP/VAMPの利点• 観測行列が右直交不変の場合、状態発展方程式の不動点が唯一ならば、OAMP/VAMPは大システ
ム極限でベイズ最適な性能を達成する。[7-4, 7-7, 7-9, 7-10, 7-11]
OAMP/VAMPの欠点• 線形MMSEフィルタの実装に、𝑨𝑨の特異値分解が必要である。
特異値分解の計算量：𝒪𝒪(𝑀𝑀2 𝑁𝑁 + 𝑀𝑀𝑁𝑁 2 + 𝑁𝑁 3 )• 信号事前分布としてガウス分布を仮定できない。
[7-9] K. Takeda, S. Uda, and Y. Kabashima, “Analysis of CDMA systems that are characterizedby eigenvalue spectrum,” Europhys. Lett., vol. 76, no. 6, pp. 1193–1199, 2006.
[7-10] A. M. Tulino, G. Caire, S. Verdú, and S. Shamai (Shitz), “Support recovery with sparsely sampled
free random matrices,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4243–4271, Jul. 2013.
[7-11] J. Barbier, N. Macris, A. Maillard, and F. Krzakala, “The mutual information in random linear estimation
beyond i.i.d. matrices,” in Proc. 2018 IEEE Int. Symp. Inf. Theory, Vail, CO, USA, Jun. 2018, pp. 1390–1394.
7

長期記憶メッセージ伝播法
一般形 𝒙𝒙A,𝑡𝑡 = 𝜙𝜙𝑡𝑡 𝒙𝒙B,0 , … , 𝒙𝒙B,𝑡𝑡 ,𝒙𝒙B,𝑡𝑡+1 = 𝜓𝜓𝑡𝑡 (𝒙𝒙A,0 , … , 𝒙𝒙A,𝑡𝑡 )メッセージを更新する際、過去のメッセージすべてを使う。

𝜙𝜙𝑡𝑡 や𝜓𝜓𝑡𝑡 の設計目標

最小限の計算量で、ベイズ最適な性能を達成する。

設計手順
1. 関数𝜙𝜙𝑡𝑡 や𝜓𝜓𝑡𝑡 の適切なモデルを考える。

2. 状態発展法の一般論[7-12]を利用して、誤差が漸近的にガウス分布するように、モデルパラメータの一部を設計する。
3. 状態発展法により、残りのパラメータを最適化する。

[7-12] K. Takeuchi, “Bayes-optimal convolutional AMP,” IEEE Trans. Inf. Theory, vol. 67, no. 7,pp. 4405–4428, Jul. 2021.
8

Convolutional AMP
Convolutional AMP (CAMP) [7-12, 7-13]
𝒙𝒙𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 ,𝑡𝑡−1𝑡𝑡−1𝜏𝜏=0𝑡𝑡 ′ =𝜏𝜏𝜉𝜉𝑡𝑡 = 𝜂𝜂𝑡𝑡′ 𝒙𝒙𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡

𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨𝒙𝒙𝑡𝑡 + � � 𝜉𝜉𝑡𝑡 ′𝜃𝜃𝑡𝑡−𝜏𝜏 𝑨𝑨𝑨𝑨T − 𝑔𝑔𝑡𝑡−𝜏𝜏 𝑰𝑰𝑀𝑀 𝒛𝒛𝜏𝜏 ,AMPのオンサーガ補正を過去の全メッセージの畳み込みに拡張
CAMPの利点
CAMPの計算量は、最小限である。
注意
𝑨𝑨の成分が独立で𝒩𝒩(0,1/𝑀𝑀)に従うとき、CAMPはAMPと等価[7-13] K. Takeuchi, “Convolutional approximate message-passing,” IEEE Signal Process. Lett.,
vol. 27, pp. 416–420, 2020.

9数値実験（文献[7-12]のFig. 4）

𝑀𝑀 = 210 、𝑁𝑁 = 211 、信号密度𝜌𝜌 = 0.1のBG事前分布、1/𝜎𝜎 2 = 30 dB

10

Memory AMP [7-14]
モジュールA𝑡𝑡

1𝒙𝒙A→B,𝑡𝑡 =𝑨𝑨T 𝒛𝒛𝑡𝑡 − � 𝜉𝜉A,𝑡𝑡,𝜏𝜏 𝒙𝒙B→A,𝜏𝜏 ,𝜖𝜖𝑡𝑡
𝜏𝜏=0𝒛𝒛𝑡𝑡 = 𝑎𝑎𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡 + 𝑏𝑏𝑡𝑡 𝜆𝜆̅ − 𝑨𝑨𝑨𝑨T 𝒛𝒛𝑡𝑡−1 ,モジュールB
𝒙𝒙B,𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙A→B,𝑡𝑡 ,𝜉𝜉B,𝑡𝑡 = 𝜂𝜂 ′ 𝑡𝑡 𝒙𝒙A→B,𝑡𝑡

𝜆𝜆max 𝑨𝑨𝑨𝑨T + 𝜆𝜆min 𝑨𝑨𝑨𝑨T𝜆𝜆̅ =2𝑡𝑡𝒙𝒙B,𝜏𝜏+1 − 𝜉𝜉B,𝜏𝜏 𝒙𝒙A→B,𝜏𝜏
𝒙𝒙B→A,𝑡𝑡+1 = � 𝜃𝜃𝑡𝑡,𝜏𝜏
1 − 𝜉𝜉B,𝜏𝜏,𝜏𝜏=0Memory AMPの計算量は、最小限である。

[7-14] L. Liu, S. Huang and B. M. Kurkoski, "Memory AMP," IEEE Trans. Inf. Theory, 2022,
DOI: 10.1109/TIT.2022.3186166.
11

Memory AMPの特徴
モジュールA

以下の恒等式を使って、 LMMSEフィルタを近似∞

𝑰𝑰 − 𝑮𝑮𝑡𝑡 −1 = � 𝑮𝑮𝜏𝜏𝑡𝑡 ,𝜏𝜏=0𝑮𝑮𝑡𝑡 = 𝑰𝑰 − 𝑏𝑏𝑡𝑡

𝜎𝜎 2𝑣𝑣B→A,𝑡𝑡

𝑰𝑰 + 𝑨𝑨𝑨𝑨T .

{𝜉𝜉A,𝑡𝑡,𝜏𝜏 }は誤差の漸近ガウス性が成立するように設計

モジュールB

長期記憶ダンピング[7-15]により、収束を保証[7-14]

Memory AMPの利点• 観測行列が右直交不変の場合、状態発展方程式の不動点が唯一ならば、memory AMPは大システム極限でベイズ最適な性能を達成する。[7-14][7-15] K. Takeuchi, "On the convergence of orthogonal/vector AMP: Long-memory message-passing
strategy," IEEE Trans. Inf. Theory, 2022, DOI: 10.1109/TIT.2022.3194855.
12WS-CG-VAMP
Warm-Starting Conjugate Gradient VAMP (WS-CG-VAMP) [7-16]
𝑡𝑡
モジュールA
1𝑥𝑥A→B,𝑡𝑡 =𝑨𝑨T 𝒛𝒛𝑖𝑖𝑡𝑡 − � 𝜉𝜉A,𝑡𝑡,𝜏𝜏 𝒙𝒙B→A,𝜏𝜏 ,𝜖𝜖𝑡𝑡
𝜏𝜏=0𝒛𝒛𝑖𝑖𝑡𝑡 は、線形方程式に対する解𝒛𝒛𝑡𝑡 を𝑖𝑖回のCG反復[7-17]で近似した解(𝜎𝜎 2 /𝑣𝑣B→A,𝑡𝑡 )𝑰𝑰 + 𝑨𝑨𝑨𝑨T 𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡

モジュールB𝒙𝒙B,𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 (𝒙𝒙A→B,𝑡𝑡 ),𝜉𝜉B,𝑡𝑡 = ⟨𝜂𝜂𝜂𝑡𝑡 (𝒙𝒙A→B,𝑡𝑡 )⟩𝒙𝒙B,𝑡𝑡+1 − 𝜉𝜉B,𝑡𝑡 𝒙𝒙A→B,𝑡𝑡𝒙𝒙B→A,𝑡𝑡+1 =,1 − 𝜉𝜉B,𝑡𝑡𝜉𝜉B,𝑡𝑡 𝑣𝑣A→B,𝑡𝑡𝑣𝑣B→A,𝑡𝑡+1 =1 − 𝜉𝜉B,𝑡𝑡[7-16] N. Skuratovs and M. E. Davies, “Compressed sensing with upscaled vector approximate
message passing,” IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4818–4836, Jul. 2022.

[7-17] K. Takeuchi and C.-K. Wen, “Rigorous dynamics of expectation-propagation signal detection
via the conjugate gradient method,” in Proc. 18th IEEE Int. Workshop Sig. Process. Advances Wirel.
Commun., Sapporo, Japan, Jul. 2017, pp. 88–92.

13

WS-CG-VAMPの特徴
WS-CG-VAMPの利点• WS-CG-VAMPの計算量は、最小限である。
• 観測行列が右直交不変の場合、状態発展方程式の不動点が唯一ならば、WS-CG-VAMPは大システム極限でベイズ最適な性能を達成する。[7-16]
Memory AMPとWS-CG-VAMPの比較
Memory AMPは、 CG反復1回のWS-CG-VAMPと同等性能
未解決課題• Memory AMPとWS-CG-VAMP（ 𝑖𝑖 > 1 ）の公平な比較• システムが大きすぎる（𝑁𝑁 = 214 [7-14]、𝑁𝑁 = 220 [7-16]）

14

Rotationally Invariant AMP
Rotationally Invariant AMP (RI-AMP) [7-18]
モジュールA

𝒙𝒙A,𝑡𝑡 = 𝜙𝜙𝑡𝑡 𝒙𝒙B→A,1 , … , 𝒙𝒙B→A,𝑡𝑡 , 𝒚𝒚 ,𝑡𝑡

モジュールB

𝒙𝒙A→B,𝑡𝑡 = 𝑨𝑨T 𝒙𝒙A,𝑡𝑡 − � 𝜃𝜃A,𝑡𝑡,𝜏𝜏 𝒙𝒙B,𝜏𝜏𝜏𝜏=1𝒙𝒙B,𝑡𝑡+1 = 𝜓𝜓𝑡𝑡 𝒙𝒙A→B,0 , … , 𝒙𝒙A→B,𝑡𝑡 ,𝑡𝑡𝒙𝒙B→A,𝑡𝑡+1 = 𝑨𝑨𝒙𝒙B,𝑡𝑡+1 − � 𝜃𝜃B,𝑡𝑡,𝜏𝜏 𝒙𝒙A,𝜏𝜏
𝜏𝜏=0RI-AMPの計算量は、最小限である。

[7-18] Z. Fan, “Approximate message passing algorithms for rotationally invariant matrices,”Ann. Statist., vol. 50, no. 1, pp. 197–224, Feb. 2022.
15

RI-AMPの特徴
利点• 状態発展法[7-18]により、誤差の漸近ガウス性が成立する
ように、{𝜃𝜃A,𝑡𝑡,𝜏𝜏 , 𝜃𝜃B,𝑡𝑡,𝜏𝜏 }を設計できる。

• 状態発展法[7-18]は、Dynamical Functional Theory [7-19]を応用・厳密化した結果である。
未解決問題• 状態発展法を用いてベイズ最適な𝜙𝜙𝑡𝑡 や𝜓𝜓𝑡𝑡 を定義できるが、最適化問題が複雑すぎて、解が解けない。
[7-19] M. Opper, B. Çakmak, and O. Winther, “A theory of solving TAP equations for Ising models withgeneral invariant random matrices,” J. Phys. A: Math. Theor., vol. 49, no. 11, p. 114002, Feb. 2016.
16

まとめ
アルゴリズム

計算量

信号事前分布 観測行列

収束性

ベイズ最適

AMP [3-1]

最小限

任意

i.i.d.ガウス

証明済

証明済

OAMP/VAMP[7-3, 7-4]

高

非ガウス

右直交不変

証明済
[7-15]

証明済

CAMP [7-12]

最小限

任意

右直交不変

低条件数のみ証明済（収束すれば）

Memory AMP[7-14]

最小限

非ガウス

右直交不変

証明済

証明済

WS-CG-VAMP[7-16]

最小限

非ガウス

右直交不変

証明済

証明済

RI-AMP [7-18]

最小限

任意

右直交不変？

？

赤字は欠点/未解決問題を表す。
現状で、赤字の項目がないアルゴリズムは存在しない。
17