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

空間結合の導入
九州大学
平成３０年１０月１０日～１０月１２日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1

ベイズ最適な性能[1-5,1-6]
MMSE 𝑠𝑠 = 𝔼𝔼

1𝑣𝑣 = 𝜎𝜎 + MMSE 1/𝑣𝑣 ,𝛿𝛿
2𝑥𝑥𝑛𝑛 − 𝔼𝔼 𝑥𝑥𝑛𝑛 𝑥𝑥𝑛𝑛 + 𝑠𝑠 −1/2 𝜔𝜔𝑛𝑛2,

𝜔𝜔𝑛𝑛 ∼ 𝒩𝒩 0, 1 .

𝑣𝑣を上記の不動点方程式の解として、ベイズ最適な推定のMSEは、大システム極限でMMSE(1/𝑣𝑣)に等しい。
ただし、複数の解が存在する場合は、自由エネルギー𝐹𝐹(1/𝑣𝑣)を最小にする解を選ぶ。

自由エネルギー𝛿𝛿 2𝐹𝐹 𝑠𝑠 = 𝐼𝐼 𝑠𝑠 + 𝜎𝜎 𝑠𝑠 − 1 − ln 𝜎𝜎 2 𝑠𝑠2

𝐼𝐼 𝑠𝑠 = 𝐼𝐼 𝑥𝑥𝑛𝑛 ; 𝑥𝑥𝑛𝑛 + 𝑠𝑠 −1/2 𝜔𝜔𝑛𝑛 ,𝑑𝑑+ ln 𝜎𝜎 2 .
2𝑑𝑑：信号𝑥𝑥𝑛𝑛 のレニー情報次元2

数値的評価信号密度𝜌𝜌 = 0.3のBG事前分布、SNR：1/𝜎𝜎 2 = 60 dB.

3

自由エネルギーの性質
𝛿𝛿 > 𝑑𝑑とする。ノイズなしの極限𝜎𝜎 2 → 0で、0に収束する不動点方程式の解𝑣𝑣opt は、𝑠𝑠opt = 1/𝑣𝑣opt として𝐹𝐹(𝑠𝑠opt )を最小にする。
意義

ベイズ最適な推定は、ノイズなしの極限で情報理論的な圧縮限界𝑑𝑑[1-2]を達成する。
証明
I-M関係式[1-9]不動点方程式′𝐹𝐹 𝑠𝑠 = 0𝑑𝑑
1
𝐼𝐼 𝑠𝑠 = MMSE 𝑠𝑠 .
𝑑𝑑𝑑𝑑
2112= 𝜎𝜎 + MMSE 𝑠𝑠 .
𝑠𝑠𝛿𝛿4

エネルギー差の評価
𝑠𝑠 = 𝑂𝑂(𝜎𝜎 −2 )を満たす解[7-1]ℎ 𝑥𝑥1< ∞なので、𝑑𝑑𝐼𝐼 𝑠𝑠 = ln 𝑠𝑠 + 𝑜𝑜(ln 𝑠𝑠) as 𝑠𝑠 → ∞.
2𝑑𝑑
𝛿𝛿 22𝐹𝐹 𝑠𝑠 = ln(𝜎𝜎 𝑠𝑠) + 𝜎𝜎 𝑠𝑠 − 1 − ln 𝜎𝜎 2 𝑠𝑠 + 𝑜𝑜(ln 𝑠𝑠) as 𝑠𝑠 → ∞.
22
上記の𝐹𝐹 ′ 𝑠𝑠 = 0の解𝜎𝜎 2 𝑠𝑠opt = 1 − 𝑑𝑑/𝛿𝛿 + 𝑜𝑜 1 を使うと、−2 .
lim
𝐹𝐹
𝑠𝑠=𝑜𝑜
ln
𝜎𝜎opt
2

𝜎𝜎 →0

𝑠𝑠 −1 = 𝛿𝛿 −1 MMSE 𝑠𝑠 かつ𝑠𝑠 < ∞の解𝛿𝛿𝛿𝛿 − 𝑑𝑑−2lim
𝐹𝐹
𝑠𝑠=
𝐼𝐼𝑠𝑠−1+ln
𝑠𝑠+limln𝜎𝜎.
22𝜎𝜎 →022 𝜎𝜎 →0𝐹𝐹 𝑠𝑠 − 𝐹𝐹 𝑠𝑠opt
𝛿𝛿 − 𝑑𝑑 > 0なので、 lim
2𝜎𝜎 →0> 0.

[7-1] Y. Wu and S. Verdú, “MMSE dimension,” IEEE Trans. Inf. Theory, vol. 57, no. 8,pp. 4857-4879, Aug. 2011.

∎5

状態発展方程式
閾値関数𝜂𝜂𝑡𝑡 を使ったAMP
𝑣𝑣 𝑡𝑡 = 𝜎𝜎 2 +1
𝔼𝔼 𝑥𝑥𝑛𝑛 − 𝜂𝜂𝑡𝑡 𝑥𝑥𝑛𝑛 + 𝑣𝑣 𝑡𝑡−1 𝜔𝜔𝑛𝑛𝛿𝛿2,

𝑣𝑣 0 = 1.

ベイズ最適AMP
𝑣𝑣 𝑡𝑡 = 𝜎𝜎 2 +1
MMSE 1/𝑣𝑣 𝑡𝑡−1 ,𝛿𝛿

𝑣𝑣 0 = 1.

ベイズ最適AMPでない限り、不動点方程式がベイズ最適な推定法のものからずれている。
6

チャート（不動点が唯一）

信号密度𝜌𝜌 = 0.3のBG事前分布、1/𝜎𝜎 2 = 60 dB、𝛿𝛿 = 0.55

7チャート（不動点が複数）

信号密度𝜌𝜌 = 0.3のBG事前分布、1/𝜎𝜎 2 = 60 dB、𝛿𝛿 = 0.42

8

AMPの最適性
AMPは、次の２条件を満たすときに、情報理論的な圧縮限界を達成する。
条件１
閾値関数𝜂𝜂𝑡𝑡 として、ベイズ最適なものが使用されている。
条件２
状態発展方程式の不動点は唯一である。

9

複数不動点への対処法1
電力配分[3-3,7-2]• 不動点方程式の解が唯一になるように、観測行列の列ベクトルのノルムにばらつきを持たせる。
• 高SNRでの性能が悪化するという欠点がある。

電力配分なし電力配分あり[7-2] G. Caire, R. R. Müller, and T. Tanaka, “Iterative multiuser joint decoding: Optimal power allocationand low-complexity implementation,” IEEE Trans. Inf. Theory, vol. 50, no. 9, pp. 1950–1973, Sep. 2004.
10

複数不動点への対処法２
空間結合[7-3,7-4,7-5]不動点方程式の解が唯一になるように、観測行列に空間結合構造を導入する。

[7-3] S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold saturation via spatial coupling:
Why convolutional LDPC ensembles perform so well over the BEC,” IEEE Trans. Inf. Theory, vol. 57,
no. 2, pp. 803–834, Feb. 2011.
[7-4] K. Takeuchi, T. Tanaka, and T. Kawabata, “Performance improvement of iterative multiuser
detection for large sparsely spread CDMA systems by spatial coupling,” IEEE Trans. Inf. Theory,
vol. 61, no. 4, pp. 1768–1794, Apr. 2015.
[7-5] D. L. Donoho, A. Javanmard, and A. Montanari, “Information theoretically optimal compressedsensing via spatial coupling and approximate message passing,” IEEE Trans. Inf. Theory, vol. 59, no. 11,
pp. 7434–7464, Nov. 2013.
11

空間結合
𝑨𝑨を 𝐿𝐿 + 𝑊𝑊 − 1 × (𝐿𝐿 + 2𝑊𝑊 − 2)ブロック帯行列に拡張

𝑨𝑨[0, −𝑊𝑊 + 1] ⋯ 𝑨𝑨[0,0]𝑨𝑨 =𝑶𝑶𝑨𝑨[𝐿𝐿 + 𝑊𝑊 − 2, 𝐿𝐿 − 1]

𝑶𝑶

𝑨𝑨[𝐿𝐿 + 𝑊𝑊 − 2, 𝐿𝐿 + 𝑊𝑊 − 2]𝑨𝑨 𝑙𝑙, 𝑙𝑙′ ∈ ℝ𝑀𝑀×𝑁𝑁 ：𝒩𝒩(0,1/𝑊𝑊𝑊𝑊)に従うi.i.d.要素を持つ。

12

境界条件
ブロック信号ベクトル𝒙𝒙 = (𝒙𝒙 −𝑊𝑊 + 1 , … 𝒙𝒙[𝐿𝐿 + 𝑊𝑊 − 2])T

境界条件

開始セクション𝑙𝑙 ∈ {−𝑊𝑊 + 1, … , −1}と終了セクション𝑙𝑙 ∈ {𝐿𝐿, … , 𝐿𝐿 + 𝑊𝑊 − 2}における信号ブロック𝒙𝒙[𝑙𝑙]は、干渉+雑音電力が𝜎𝜎 2 で推定できるような工夫を施す。

注意

境界セクションの干渉＋雑音電力をベイズ最適な推定法が達成するものより小さい値に設定する必要がある。
13

AMPの状態発展方程式[7-4,7-5]
状態発展方程式
AMPの反復𝑡𝑡セクション𝑙𝑙におけるMSEは、大システム極限でMMSE 𝑠𝑠 𝑡𝑡 [𝑙𝑙] に収束する。

𝑊𝑊−1
信号対干渉＋雑音比
11𝑡𝑡（SINR）
� 𝑡𝑡−1
𝑠𝑠 𝑙𝑙 =,𝑊𝑊𝑣𝑣 [𝑙𝑙 + 𝑤𝑤]
𝑤𝑤=0
干渉＋雑音電力
𝑊𝑊−1
1𝑡𝑡
2𝑣𝑣 𝑙𝑙 = 𝜎𝜎 +� MMSE 𝑠𝑠 𝑡𝑡 [𝑙𝑙 − 𝑤𝑤] .
𝛿𝛿𝛿𝛿

境界条件
初期条件

𝑤𝑤=0𝑣𝑣 𝑡𝑡 𝑙𝑙 = 𝜎𝜎 2 for 𝑙𝑙 ∉ 0, … , 𝐿𝐿 − 1 .
𝑣𝑣 0 𝑙𝑙 = 1 for 𝑙𝑙 ∈ 0, … , 𝐿𝐿 − 1 .

14数値的評価信号密度𝜌𝜌 = 0.3のBG事前分布、1/𝜎𝜎 2 = 60 dB、
𝐿𝐿 = 64、𝑊𝑊 = 4、 𝛿𝛿 = 0.39

15

数値的評価信号密度𝜌𝜌 = 0.3のBG事前分布、1/𝜎𝜎 2 = 60 dB、
𝐿𝐿 = 64、𝑊𝑊 = 4、 𝛿𝛿 = 0.38、𝑡𝑡 → ∞16