メッセージ伝播復調法の課題と展望
CS研究会 特別招待講演
2024年3月14日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1大規模MIMOアップリンク
𝑁𝑁人のユーザから単一基地局への無線伝送モデル
𝒚𝒚 = 𝑨𝑨𝑨𝑨 + 𝒘𝒘,𝒘𝒘 ∼ 𝒩𝒩(𝟎𝟎, 𝜎𝜎 2 𝑰𝑰𝑀𝑀 )𝒚𝒚 = 𝑦𝑦1 , … , 𝑦𝑦𝑀𝑀 T ∈ ℝ𝑀𝑀 ：𝑀𝑀次元受信ベクトル

𝒙𝒙 = 𝑥𝑥1 , … , 𝑥𝑥𝑁𝑁 T ∈ ℝ𝑁𝑁 ：𝑁𝑁次元送信ベクトル

𝒘𝒘 = 𝑤𝑤1 , … , 𝑤𝑤𝑀𝑀 T ∈ ℝ𝑀𝑀 ：𝑀𝑀次元ノイズベクトル

𝑨𝑨 = [𝐴𝐴𝑚𝑚𝑚𝑚 ] ∈ ℝ𝑀𝑀×𝑁𝑁 ：𝑀𝑀行𝑁𝑁列の通信路行列

復調問題の目的

受信ベクトル𝒚𝒚と通信路行列𝑨𝑨に関する情報を使って、最小限の計算量かつベイズ最適な性能で送信ベクトル𝒙𝒙を推定せよ。
2

メッセージ伝播法のまとめ
アルゴリズム
近似的メッセージ伝播法(AMP) [1]直交/ベクトルAMP(OAMP [2]/VAMP [3])畳み込みAMP (CAMP) [4]メモリAMP (MAMP) [5]計算量
𝒪𝒪(𝑡𝑡𝑡𝑡𝑡𝑡)
𝑡𝑡：反復回数

𝒪𝒪(𝑡𝑡𝑡𝑡𝑡𝑡 + 𝑀𝑀3+ 𝑀𝑀2 𝑁𝑁)
𝒪𝒪(𝑡𝑡𝑡𝑡𝑡𝑡)

𝒪𝒪(𝑡𝑡𝑡𝑡𝑡𝑡)

通信路行列 性能
i.i.d.ガウス 最適
右直交不変 最適
右直交不変 最適?
右直交不変 最適?

[1] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,”
Proc. Nat. Acad. Sci., vol. 106, no. 45, pp. 18 914–18 919, Nov. 2009.
[2] J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020–2033, Jan. 2017.
[3] 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.
[4] K. Takeuchi, “Bayes-optimal convolutional AMP,” IEEE Trans. Inf. Theory, vol. 67, no. 7,pp. 4405–4428, Jul. 2021.
[5] L. Liu, S. Huang, and B. M. Kurkoski, “Memory AMP,” IEEE Trans. Inf. Theory, vol. 68, no. 12,pp. 8015–8039, Dec. 2022.
3

従来型メッセージ伝播法の概要
モジュールA (線形干渉除去)
𝒚𝒚, 𝑨𝑨

信号推定
𝒙𝒙A,𝑡𝑡 ∈ ℝ𝑁𝑁
𝑣𝑣A,𝑡𝑡 > 0

オンサーガ補正
𝒙𝒙A→B,𝑡𝑡 ∈ ℝ𝑁𝑁
𝑣𝑣A→B,𝑡𝑡 > 0

モジュールB (要素ごとの軟判定)
オンサーガ補正𝒙𝒙B→A,𝑡𝑡+1 ∈ ℝ𝑁𝑁
𝑣𝑣B→A,𝑡𝑡+1 > 0

信号推定
𝒙𝒙B,𝑡𝑡+1 ∈ ℝ𝑁𝑁𝑣𝑣B,𝑡𝑡+1 > 0推定結果

4

近似的メッセージ伝播法[1]モジュールA（整合フィルタ推定）
𝒙𝒙A→B,𝑡𝑡 = 𝒙𝒙B,𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 ,𝑁𝑁
2𝑣𝑣A→B,𝑡𝑡 = 𝜎𝜎 + 𝑣𝑣B,𝑡𝑡 ,𝑀𝑀

𝑁𝑁𝑣𝑣B,𝑡𝑡𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨𝒙𝒙B,𝑡𝑡 +𝒛𝒛𝑡𝑡−1 .
𝑀𝑀𝑣𝑣A→B,𝑡𝑡−1オンサーガ補正モジュールB（要素ごとの軟判定）

𝒙𝒙B,𝑡𝑡+1 = 𝔼𝔼[𝒙𝒙|𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡 ],12𝑣𝑣B,𝑡𝑡+1 = 𝔼𝔼 𝒙𝒙 − 𝒙𝒙B,𝑡𝑡+1 |𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡
𝑁𝑁

仮想的なガウス通信路

𝒙𝒙A→B,𝑡𝑡 = 𝒙𝒙 + 𝒉𝒉𝑡𝑡 ,𝒉𝒉𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑣𝑣A→B,𝑡𝑡 𝑰𝑰𝑁𝑁 .

推定誤差𝒙𝒙A→B,𝑡𝑡 − 𝒙𝒙がガウス分布することを想定

5

オンサーガ補正の効果

補正なし
圧縮比

補正あり
𝑀𝑀/𝑁𝑁 = 0.5

送信信号

信号密度0.1のベルヌーイ・ガウス信号

通信路行列

i.i.d.ガウス行列

信号対雑音比(SNR)

30 dB

反復回数

2回

6

直交/ベクトルAMP [2, 3]
モジュールA（LMMSE推定）
𝒙𝒙A,𝑡𝑡 = 𝒙𝒙B→A,𝑡𝑡 + 𝑨𝑨T 𝜩𝜩𝑡𝑡−1 (𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡 ),𝜎𝜎 2𝜩𝜩𝑡𝑡 =
𝑰𝑰𝑀𝑀 + 𝑨𝑨𝑨𝑨T ,𝑣𝑣B→A,𝑡𝑡𝑣𝑣B→A,𝑡𝑡
Tr 𝑰𝑰𝑁𝑁 − 𝑨𝑨T 𝜩𝜩𝑡𝑡−1 𝑨𝑨 ,𝑣𝑣A,𝑡𝑡 =𝑁𝑁𝒙𝒙A,𝑡𝑡 − 𝜉𝜉A,𝑡𝑡 𝒙𝒙B→A,𝑡𝑡𝑣𝑣A,𝑡𝑡
𝜉𝜉A,𝑡𝑡 𝑣𝑣B→A,𝑡𝑡, 𝑣𝑣A→B,𝑡𝑡 =𝒙𝒙A→B,𝑡𝑡 =.
, 𝜉𝜉A,𝑡𝑡 =1 − 𝜉𝜉A,𝑡𝑡𝑣𝑣B→A,𝑡𝑡
1 − 𝜉𝜉A,𝑡𝑡

モジュールB（要素ごとの軟判定）

オンサーガ補正

𝒙𝒙B,𝑡𝑡+1 = 𝔼𝔼[𝒙𝒙|𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡 ],AMPと同定義
12𝑣𝑣B,𝑡𝑡+1 = 𝔼𝔼 𝒙𝒙 − 𝒙𝒙B,𝑡𝑡+1 |𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡
𝑁𝑁
𝒙𝒙B,𝑡𝑡+1 − 𝜉𝜉B,𝑡𝑡 𝒙𝒙A→B,𝑡𝑡
𝜉𝜉B,𝑡𝑡 𝑣𝑣A→B,𝑡𝑡𝑣𝑣B,𝑡𝑡+1𝒙𝒙B→A,𝑡𝑡 =, 𝑣𝑣B→A,𝑡𝑡 =, 𝜉𝜉B,𝑡𝑡 =.
1 − 𝜉𝜉B,𝑡𝑡
1 − 𝜉𝜉B,𝑡𝑡𝑣𝑣A→B,𝑡𝑡7

長期記憶型メッセージ伝播法の概要
モジュールA (線形干渉除去)
メモリ

信号推定𝒙𝒙B→A,𝜏𝜏 𝜏𝜏=0
𝑽𝑽B→A,𝑡𝑡

𝒙𝒙A,𝑡𝑡 ∈ ℝ𝑁𝑁
𝑽𝑽A,𝑡𝑡𝑡𝑡𝒚𝒚, 𝑨𝑨

オンサーガ補正
𝒙𝒙A→B,𝑡𝑡 ∈ ℝ𝑁𝑁
𝑽𝑽A→B,𝑡𝑡

モジュールB (要素ごとの軟判定)
オンサーガ補正
𝒙𝒙B→A,𝑡𝑡+1 ∈ ℝ𝑁𝑁
𝑽𝑽B→A,𝑡𝑡+1

信号推定
𝒙𝒙B,𝑡𝑡+1
𝑽𝑽B,𝑡𝑡+1

∈ ℝ𝑁𝑁

推定結果

メモリ

𝑡𝑡𝒙𝒙A→B,𝜏𝜏 𝜏𝜏=0
𝑽𝑽A→B,𝑡𝑡8

畳み込みAMP (CAMP) [4]モジュールA（整合フィルタ推定）
𝑡𝑡−1𝜌𝜌𝑨𝑨T 𝑨𝑨 ：𝑨𝑨T 𝑨𝑨の漸近固有値分布
𝑡𝑡−1

𝑣𝑣B,𝑡𝑡 ′+1,𝑡𝑡 ′+1(𝑡𝑡−1)
𝑔𝑔𝑡𝑡−𝜏𝜏 𝒛𝒛𝜏𝜏 , 𝜉𝜉𝜏𝜏𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨𝒙𝒙B,𝑡𝑡 + � 𝜉𝜉𝜏𝜏=�,𝑣𝑣A→B,𝑡𝑡 ′,𝑡𝑡 ′′𝜏𝜏=0
𝑡𝑡 =𝜏𝜏
𝒙𝒙A→B,𝑡𝑡 = 𝒙𝒙B,𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 , 𝑽𝑽A→B,𝑡𝑡 = 𝚽𝚽𝑡𝑡CAMP (𝑽𝑽A→B,𝑡𝑡−1 , 𝑽𝑽B,𝑡𝑡 ; 𝜌𝜌𝑨𝑨T𝑨𝑨 ).
𝑡𝑡−1タップ係数𝑔𝑔𝜏𝜏 ∈ ℝと共分散行列𝑽𝑽A→B,𝑡𝑡 は状態発展法で設計する。

モジュールB（要素ごとの軟判定）
𝒙𝒙B,𝑡𝑡+1 = 𝔼𝔼[𝒙𝒙|𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡 ],1T′𝑣𝑣B,𝑡𝑡+1,𝑡𝑡 +1 = 𝔼𝔼 𝒙𝒙 − 𝒙𝒙B,𝑡𝑡+1 (𝒙𝒙 − 𝒙𝒙B,𝑡𝑡 ′+1 )|𝒙𝒙A→B,𝑡𝑡 , 𝒙𝒙A→B,𝑡𝑡 ′𝑁𝑁𝒙𝒙A→B,𝑡𝑡 = 𝒙𝒙 + 𝒉𝒉𝑡𝑡 ,𝒉𝒉𝑡𝑡 , 𝒉𝒉𝑡𝑡 ′𝑣𝑣A→B,𝑡𝑡,𝑡𝑡 𝑰𝑰 𝑣𝑣A→B,𝑡𝑡,𝑡𝑡 ′ 𝑰𝑰
∼ 𝒩𝒩 𝟎𝟎,𝑣𝑣A→B,𝑡𝑡 ′,𝑡𝑡 𝑰𝑰 𝑣𝑣A→B,𝑡𝑡 ′,𝑡𝑡 ′ 𝑰𝑰9

誤差の同時確率密度関数の等高線

システムサイズ𝑀𝑀 = 8192、𝑁𝑁 = 16384

送信信号

信号密度0.1のベルヌーイ・ガウス信号

通信路行列

条件数5の右直交不変行列

信号対雑音比(SNR)

30 dB

10

勾配降下法による逆行列演算の近似
OAMP/VAMPにおける逆行列演算
𝒛𝒛𝑡𝑡 = 𝑐𝑐𝑡𝑡 𝜩𝜩𝑡𝑡−1 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡𝑐𝑐𝑡𝑡 ∈ ℝは任意定数２次最適化問題としての定式化

1 TT𝑓𝑓𝑡𝑡 𝒛𝒛 = 𝒛𝒛 𝜩𝜩𝑡𝑡 𝒛𝒛 − 𝑐𝑐𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡 𝒛𝒛.
2𝒛𝒛𝑡𝑡 = argmin 𝑓𝑓𝑡𝑡 𝒛𝒛 ,𝒛𝒛∈ℝ𝑀𝑀

勾配降下法による近似(𝑖𝑖+1)𝒛𝒛𝑡𝑡(𝑖𝑖)

𝑖𝑖= 𝒛𝒛𝑡𝑡 − 𝜖𝜖𝑡𝑡 ∇𝑓𝑓𝑡𝑡 𝒛𝒛𝑡𝑡

𝜖𝜖𝑡𝑡 > 0の最適化(𝑖𝑖+1)𝒛𝒛𝑡𝑡𝜩𝜩𝑡𝑡 𝒛𝒛𝑡𝑡 = 𝑐𝑐𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡𝑖𝑖= 𝑰𝑰 − 𝜖𝜖𝑡𝑡 𝜩𝜩𝑡𝑡 𝒛𝒛𝑡𝑡 + 𝜖𝜖𝑡𝑡 𝑐𝑐𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡(𝑖𝑖)= 𝜖𝜖𝑡𝑡 𝜆𝜆𝑰𝑰̅ − 𝑨𝑨𝑨𝑨T 𝒛𝒛𝑡𝑡 + 𝜖𝜖𝑡𝑡 𝑐𝑐𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡= 𝜁𝜁𝑡𝑡 とおく

11

メモリAMP (MAMP) [5]
設計指針
MAMPの反復ごとに勾配降下法の更新を１回だけ行う。
モジュールA（線形推定）
𝒛𝒛𝑡𝑡 = 𝜖𝜖𝑡𝑡 𝜆𝜆𝑰𝑰̅ − 𝑨𝑨𝑨𝑨T 𝒛𝒛𝑡𝑡−1 + 𝜁𝜁𝑡𝑡 𝒚𝒚 − 𝑨𝑨𝒙𝒙B→A,𝑡𝑡 ,𝒙𝒙A→B,𝑡𝑡 =T𝑨𝑨(𝑡𝑡)𝑡𝑡𝒛𝒛𝑡𝑡 + Σ𝜏𝜏=0𝜁𝜁𝜏𝜏 𝜖𝜖𝜏𝜏+1 𝜉𝜉A,𝑡𝑡−𝜏𝜏 𝒙𝒙B→A,𝜏𝜏
,(𝑡𝑡)
𝑡𝑡∑𝜏𝜏=0𝜁𝜁𝜏𝜏 𝜖𝜖𝜏𝜏+1 𝜉𝜉A,𝑡𝑡−𝜏𝜏𝑽𝑽A→B,𝑡𝑡 = 𝚽𝚽𝑡𝑡MAMP (𝑽𝑽B,𝑡𝑡 ; 𝜌𝜌𝑨𝑨T 𝑨𝑨 ).

(𝑡𝑡)

𝑡𝑡−1𝜖𝜖𝜏𝜏+1 = � 𝜖𝜖𝑡𝑡′ ,𝑡𝑡 ′ =𝜏𝜏

パラメータ𝜉𝜉A,𝜏𝜏 , 𝜁𝜁𝑡𝑡 ∈ ℝと共分散行列𝑽𝑽A→B,𝑡𝑡 は状態発展法で設計

12

メモリAMP (MAMP) [5]モジュールB（要素ごとの軟判定）
𝒙𝒙B,𝑡𝑡+1 , = 𝔼𝔼[𝒙𝒙|𝒙𝒙A→B,𝑡𝑡 , 𝑣𝑣A→B,𝑡𝑡 ],CAMPと同じ

1T𝑣𝑣B,𝑡𝑡+1,𝑡𝑡 ′+1 = 𝔼𝔼 𝒙𝒙 − 𝒙𝒙B,𝑡𝑡+1 (𝒙𝒙 − 𝒙𝒙B,𝑡𝑡 ′+1 )|𝒙𝒙A→B,𝑡𝑡 , 𝒙𝒙A→B,𝑡𝑡 ′𝑁𝑁𝒙𝒙B,𝑡𝑡+1 − 𝜉𝜉B,𝑡𝑡 𝒙𝒙A→B,𝑡𝑡𝑣𝑣B,𝑡𝑡+1,𝑡𝑡+1 OAMP/VAMP
𝒙𝒙B→A,𝑡𝑡 =, 𝜉𝜉B,𝑡𝑡 =,1 − 𝜉𝜉B,𝑡𝑡𝑣𝑣A→B,𝑡𝑡,𝑡𝑡 と同じ
𝑣𝑣B,𝑡𝑡+1,𝑡𝑡 ′+1 − 𝜉𝜉B,𝑡𝑡 𝜉𝜉B,𝑡𝑡 ′ 𝑣𝑣A→B,𝑡𝑡,𝑡𝑡 ′𝑣𝑣B→A,𝑡𝑡+1,𝑡𝑡 ′ +1 =[6]
(1 − 𝜉𝜉B,𝑡𝑡 )(1 − 𝜉𝜉B,𝑡𝑡 ′ )原著[5]とは異なる𝑣𝑣B→A,𝑡𝑡+1,𝑡𝑡 ′+1 の更新式[6]を用いた。

[6] K. Takeuchi, “On the convergence of orthogonal/vector AMP: Long-memory message-passing strategy,”IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 8121–8138, Dec. 2022.
13収束性の保証長期記憶型(LM)ダンピング [5, 6, 7]
𝑡𝑡

𝒙𝒙A→B,𝑡𝑡 ≔ � 𝜃𝜃𝑡𝑡,𝜏𝜏 𝒙𝒙A→B,𝜏𝜏 ,𝜏𝜏=0𝑣𝑣A→B,𝑡𝑡,𝑡𝑡 ′ : =1

𝟏𝟏T 𝑽𝑽−1
A→B,𝑡𝑡 𝟏𝟏

LMダンピングの効果[6, 7]

𝜃𝜃𝑡𝑡,0𝑽𝑽−1
A→B,𝑡𝑡 𝟏𝟏⋮ = T −1,
𝟏𝟏 𝑽𝑽A→B,𝑡𝑡 𝟏𝟏𝜃𝜃𝑡𝑡,𝑡𝑡

for all 𝑡𝑡 ′ ∈ {0, … , 𝑡𝑡}.

大システム極限において、LMダンピング後の平均二乗誤差
2−1
𝑁𝑁 𝔼𝔼 𝒙𝒙 − 𝒙𝒙A→B,𝑡𝑡 は、一般に反復𝑡𝑡に関して単調減少する。
LMダンピングを用いたMAMPは収束する。

[7] L. Liu, S. Huang, and B. M. Kurkoski, “Sufficient statistic memory approximate message passing,”
in Proc. 2022 IEEE Int. Symp. Inf. Theory, Espoo, Finland, Jun.-Jul. 2022, pp.1378–1383.
14

数値実験

システムサイズ𝑀𝑀 = 8192、𝑁𝑁 = 16384

送信信号

信号密度0.1のベルヌーイ・ガウス信号

通信路行列

条件数10の右直交不変行列

信号対雑音比(SNR)

30 dB

15

数値実験

システムサイズ𝑀𝑀 = 8192、𝑁𝑁 = 16384

送信信号

信号密度0.1のベルヌーイ・ガウス信号

反復回数

MSEが最小値を取る回数

信号対雑音比(SNR)

30 dB

16

まとめ
現状認識
LMメッセージ伝播法を用いることで、AMPとOAMP/VAMPの利点(計算量、適用範囲、性能)を部分的に両立できる。
今後の課題
現状のLMメッセージ伝播法の性能（条件数<数十）は、最良なOAMP/VAMPのそれ（条件数<数千）に比べてはるかに劣る。
LMメッセージ伝播法は、システムが大きくないと、収束特性が悪い。
LMメッセージ伝播法は、非零平均の通信路行列に対処できない。
LMメッセージ伝播法は、改善の余地が大いにある。
17