メッセージ伝播法入門
第１回講義資料導入
広島市立大学
令和５年９月２５日～９月２６日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1

本講義の内容
1. 第１回から第３回
D. L. Donoho, A. Maleki, and A. Montanari, “Message-passingalgorithms for compressed sensing,” Proc. Nat. Acad. Sci., vol.
106, no. 45, pp. 18914–18919, Nov. 2009.
S. Rangan, “Generalized approximate message passing forestimation with random linear mixing,” in Proc. 2011 IEEE Int. Symp.
Inf. Theory, Saint Petersburg, Russia, Aug. 2011, pp. 2168–2172.

2. 第４回から第６回
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.

2

本講義の心得
本講義の目的学部の教養科目として習った微分積分学、線形代数、確率論等の基礎数学が、最先端の研究にどう活用されているかを学ぶ。
難易度

最高難度？（基礎数学の連続に耐える体力が必要）

論文は、教養レベルの数学に精通している前提で書かれている。
• 微分積分学：積分（高校レベル）、偏微分• 線形代数：固有分解、特異値分解、ノルム• 確率論：大数の法則、中心極限定義
難しいと思ったら数学的議論の詳細ではなく、議論のアイデアを把握せよ。
各回の講義は独立なので、敗者復活できる。
3

数理モデル
線形観測モデル𝒚𝒚 = 𝑨𝑨𝑨𝑨 + 𝒘𝒘,𝒘𝒘 ∼ 𝒩𝒩(𝟎𝟎, 𝜎𝜎 2 𝑰𝑰𝑀𝑀 )𝒚𝒚 = 𝑦𝑦1 , … , 𝑦𝑦𝑀𝑀 T ∈ ℝ𝑀𝑀 ：𝑀𝑀次元観測ベクトル𝒙𝒙 = 𝑥𝑥1 , … , 𝑥𝑥𝑁𝑁 T ∈ ℝ𝑁𝑁 ：𝑁𝑁次元信号ベクトル

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

目標

𝑨𝑨 = [𝐴𝐴𝑚𝑚𝑚𝑚 ] ∈ ℝ𝑀𝑀×𝑁𝑁 ：𝑀𝑀行𝑁𝑁列の観測行列

𝒚𝒚、𝑨𝑨、未知の確率変数の統計的性質に関する情報を使って、最小限の計算量かつ最良な性能で信号ベクトル𝒙𝒙を推定せよ。
4

本講義を通じての仮定
信号ベクトル𝒙𝒙は平均0分散1の独立同一分布に従う(i.i.d.)成分からなる。

観測行列

𝑨𝑨は平均0分散𝑀𝑀−1 のガウス分布に従う独立な成分からなる。
電力の規格化
1
1
2
𝔼𝔼 𝑨𝑨𝑨𝑨= 𝔼𝔼 Tr 𝑨𝑨𝑨𝑨𝒙𝒙T 𝑨𝑨T
𝑁𝑁
𝑁𝑁

1= 𝔼𝔼 Tr 𝑨𝑨𝑨𝑨T
𝑁𝑁= 1.

5

Multiple-input multiple-output (MIMO)
𝑥𝑥1 = ±1

ユーザ1

𝑥𝑥2 = ±1

ユーザ2・・・

𝑨𝑨

1・・・

𝑀𝑀

基地局

𝑥𝑥𝑁𝑁 = ±1ユーザ𝑁𝑁

6圧縮センシング
𝐾𝐾-スパース信号

信号ベクトル𝒙𝒙の非零要素数は高々𝐾𝐾である。

𝑥𝑥𝑛𝑛0𝑛𝑛7

スパース重ね合わせ符号[1-1]セクション数𝐿𝐿ブロックサイズ𝐵𝐵の符号語
𝒙𝒙 1⋮𝒄𝒄 = 𝑨𝑨𝑨𝑨 = 𝑨𝑨 1 ⋯ 𝑨𝑨[𝐿𝐿]
𝒙𝒙 𝐿𝐿𝑥𝑥 𝑙𝑙 ∈ ℝ𝐵𝐵 :非零要素が1の𝐵𝐵次元１-スパース情報ベクトル

符号化率

𝐿𝐿
𝑅𝑅 = log 𝐵𝐵
𝑀𝑀[1-1] A. Joseph and A. R. Barron, “Least squares superposition codes of moderate dictionary size arereliable at rates up to capacity,” IEEE Trans. Inf. Theory, vol. 58,no. 5, pp. 2541-2557, May 2012.
8情報理論的スパース性[1-2]
ノイズなしの場合ノイズがない場合を考え、信号成分{𝑥𝑥𝑛𝑛 }は特異成分を持たな
い独立同一分布(i.i.d.) に従うと仮定する。
圧縮率𝛿𝛿 = 𝑀𝑀/𝑁𝑁を固定して次元𝑀𝑀と𝑁𝑁を無限大にした大システム極限において、任意の𝜖𝜖 ∈ (0,1)に対して信号再構成に失敗する確率が𝜖𝜖以下となるような観測行列𝑨𝑨と再構成方法が存在するための必要十分条件は、圧縮率𝛿𝛿がレニー情報次元𝑑𝑑(𝑥𝑥1 )以上であることである。

[1-2] Y. Wu and S. Verdú, “Rényi information dimension: Fundamental limits of almost lossless analog
compression,” IEEE Trans. Inf. Theory, vol. 56, no. 8, pp. 3721-3748, Aug. 2010.
9

レニー情報次元[1-3]以下、𝐻𝐻 𝑋𝑋

< ∞を満たすとする。

確率変数𝑋𝑋のレニー情報次元𝑑𝑑
𝐻𝐻 𝑛𝑛−1 𝑛𝑛𝑛𝑛

レニーエントロピー= 𝑑𝑑 log 𝑛𝑛 + ℎ + 𝑜𝑜 1 as 𝑛𝑛 → ∞.

離散確率変数𝑋𝑋の場合
𝐻𝐻 𝑛𝑛−1 𝑛𝑛𝑛𝑛 = 0 log 𝑛𝑛 + 𝐻𝐻 𝑋𝑋 + 𝑜𝑜(1).

絶対連続な確率変数𝑋𝑋の場合
𝐻𝐻 𝑛𝑛−1 𝑛𝑛𝑛𝑛 = 1 log 𝑛𝑛 + ℎ 𝑋𝑋 + 𝑜𝑜(1).
混合分布𝑃𝑃に従う確率変数𝑋𝑋の場合
𝐻𝐻 𝑛𝑛−1 𝑛𝑛𝑛𝑛

= 𝜌𝜌 log 𝑛𝑛 + 𝑂𝑂 1 .

𝑃𝑃 = 1 − 𝜌𝜌 𝑃𝑃d + 𝜌𝜌𝑃𝑃c (𝑃𝑃d ：離散分布、𝑃𝑃c ：絶対連続分布)[1-3] A. Rényi, “On the dimension and entropy of probability distributions,”
Acta Mathematica Hungarica, vol. 10, no. 1-2, Mar. 1959.

10詳細な解析[1-4]
ノイズがない場合を考え、信号成分{𝑥𝑥𝑛𝑛 }は±1を独立に等確率で取るものと仮定する。
圧縮率𝛿𝛿 = 𝑀𝑀/𝑁𝑁が以下の不等式を満たすならば、
𝑀𝑀2>𝑁𝑁 log 3 𝑁𝑁

次元𝑀𝑀と𝑁𝑁を無限大した極限において、ビット誤り確率が0に収束するような観測行列𝑨𝑨と信号再構成方法が存在する。
注意
𝑨𝑨をi.i.d.ガウス行列に取れば良い。

[1-4] M. A. Sedaghat, R. R. Müller, and F. Marvasti, “On Optimum Asymptotic Multiuser Efficiency ofRandomly Spread CDMA,” IEEE Trans. Inf. Theory, vol. 61, no. 12, pp. 6635-6642, Dec. 2015.
11

ノイズがある場合ノイズがある場合の性能限界の評価は困難である。
レプリカ法[1-5, 1-6]
• 統計力学で開発された計算手法である。
• 他の厳密な手法では評価が困難な問題を解ける。
• いくつかの未証明な仮定を使う。
仮定の一例
モーメント系列 𝔼𝔼 𝑋𝑋 𝑛𝑛
外挿できる。

∞𝛼𝛼
𝑛𝑛=1 から、期待値𝔼𝔼 𝑋𝑋 （𝛼𝛼 < 1）を[1-5] T. Tanaka, “A statistical-mechanics approach to large-system analysis of CDMA multiuserdetectors,” IEEE Trans. Inf. Theory, vol. 48, no. 11, pp. 2888–2910, Nov. 2002.
[1-6] D. Guo and S. Verdú, “Randomly spread CDMA: Asymptotics via statistical physics,”
IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1983–2010, Jun. 2005.
12ノイズがある場合[1-5, 1-6]

信号密度𝜌𝜌 = 0.3のBernoulli-Gauss(BG)分布、SNR：1/𝜎𝜎 2 = 60 dB.

13

厳密性に関するコメント
文献[1-7, 1-8]の結果から、前ページの結果は正しい。
相互情報量𝐼𝐼(𝑥𝑥; 𝑦𝑦|𝐴𝐴)に関する厳密解[1-7] G. Reeves and H. D. Pfister, "The replica-symmetric prediction for random linear estimation with
Gaussian matrices is exact," IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2252-2283, Apr. 2019.

[1-8] J. Barbier, N. Macris, M. Dia and F. Krzakala, "Mutual information and optimality of approximate
message-passing in random linear estimation," IEEE Trans. Inf. Theory, vol. 66, no. 7, pp. 4270-4303,
Jul. 2020.

一般化線形観測モデルに関する厳密解（第３回資料参照）[1-9] J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová, “Optimal errors and phasetransitions in high-dimensional generalized linear models,” Proc. Nat. Acad. Sci., vol. 116, no. 12,
pp. 5451–5460, Mar. 2019.

14

ベイズ最適な推定� ∈ ℝ𝑁𝑁 を信号ベクトル𝒙𝒙の推定量とする。
𝒙𝒙

最適性の基準・・・平均二乗誤差（MSE）

�opt = argmin 𝔼𝔼 𝒙𝒙 − 𝒙𝒙
� 2 |𝑨𝑨𝒙𝒙
�∈ℝ𝑁𝑁𝒙𝒙

事後平均推定量�
𝒙𝒙PME = 𝔼𝔼[𝒙𝒙|𝒚𝒚, 𝑨𝑨]は最適である。

証明 𝔼𝔼 𝒙𝒙 − 𝒙𝒙
� 2 = 𝔼𝔼𝒚𝒚 𝔼𝔼𝒙𝒙 𝒙𝒙 − 𝒙𝒙
�PME + 𝒙𝒙
�PME − 𝒙𝒙� 2 |𝒚𝒚
�PME 2 + 𝔼𝔼 𝒙𝒙
�PME − 𝒙𝒙� 2= 𝔼𝔼 𝒙𝒙 − 𝒙𝒙
�PME T 𝒙𝒙
�PME − 𝒙𝒙�+2𝔼𝔼𝒚𝒚 𝔼𝔼𝒙𝒙 𝒙𝒙 − 𝒙𝒙

�PME 2 + 𝔼𝔼 𝒙𝒙
�PME − 𝒙𝒙� 2 ≥ 𝔼𝔼 𝒙𝒙 − 𝒙𝒙
�PME 2= 𝔼𝔼 𝒙𝒙 − 𝒙𝒙
𝑨𝑨に関する条件付けを省略した。

∎15

事後平均推定量
事後平均推定量の定義
�PME = ∫ 𝒙𝒙𝑝𝑝 𝒙𝒙 𝒚𝒚, 𝑨𝑨 𝑑𝑑𝒙𝒙𝒙𝒙

ベイズの公式𝑝𝑝 𝒚𝒚 𝑨𝑨, 𝒙𝒙 𝑝𝑝(𝒙𝒙),𝑝𝑝 𝒙𝒙 𝒚𝒚, 𝑨𝑨 =𝑝𝑝(𝒚𝒚|𝑨𝑨)𝑝𝑝 𝒚𝒚 𝑨𝑨 = ∫ 𝑝𝑝 𝒚𝒚 𝑨𝑨, 𝒙𝒙 𝑝𝑝 𝒙𝒙 𝑑𝑑𝒙𝒙

事後平均推定量

�PME =𝒙𝒙∫ 𝒙𝒙𝑝𝑝 𝒚𝒚 𝑨𝑨, 𝒙𝒙 𝑝𝑝 𝒙𝒙 𝑑𝑑𝒙𝒙
∫ 𝑝𝑝 𝒚𝒚 𝑨𝑨, 𝒙𝒙 𝑝𝑝 𝒙𝒙 𝑑𝑑𝒙𝒙

16

事後平均推定量の性質
一般に、事後平均推定量はその誤差と無相関である。
�PME 𝒙𝒙
�PME − 𝒙𝒙 T |𝑨𝑨 = 𝑶𝑶
𝔼𝔼 𝒙𝒙

証明

�PME は𝒚𝒚と𝑨𝑨の決定論的な関数なので、𝒙𝒙�PME 𝒙𝒙T |𝑨𝑨 = 𝔼𝔼 𝒙𝒙
�PME 𝔼𝔼 𝒙𝒙T 𝒚𝒚, 𝑨𝑨 |𝑨𝑨 = 𝔼𝔼 𝒙𝒙
�PME 𝒙𝒙�TPME |𝑨𝑨𝔼𝔼 𝒙𝒙

この式から

�PME 𝒙𝒙
�PME − 𝒙𝒙 T |𝑨𝑨𝔼𝔼 𝒙𝒙

�PME 𝒙𝒙�TPME 𝑨𝑨 − 𝔼𝔼 𝒙𝒙
�PME 𝒙𝒙�TPME 𝑨𝑨 = 𝑶𝑶= 𝔼𝔼 𝒙𝒙∎
17

事後平均推定量の問題点
計算量
𝒙𝒙が連続の場合・・・𝑁𝑁重積分が必要

𝒙𝒙 ∈ ±1 𝑁𝑁 の場合・・・少なくとも2𝑁𝑁 回の足し算が必要

最小限の計算量

𝒪𝒪(𝐼𝐼𝐼𝐼𝐼𝐼)の計算量で評価できる𝒙𝒙の推定量�
𝒙𝒙は、最小限の計算量で評価可能と言う。
𝐼𝐼：𝑀𝑀や𝑁𝑁に直接依存しないパラメータ（反復回数）
本講義で扱うAMPは、最小限の計算量である。

18

数値的比較

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

19