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

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

1

本講義の目標
1. 初日（第１回から第３回）
D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing
algorithms for compressed sensing,” Proc. Nat. Acad. Sci., vol.
106, no. 45, pp. 18914–18919, Nov. 2009.

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.

3. 三日目（第７回と第８回）
D. L. Donoho, A. Javanmard, and A. Montanari, “Information
theoretically optimal compressed sensing via spatial coupling andapproximate message passing,” IEEE Trans. Inf. Theory, vol. 59,
no. 11, pp. 7434–7464, Nov. 2013.
2

本講義の心得
数学的議論は最高難度
世界トップの研究者が見ている世界は理解しがたい？
本講義資料を下に「試験」を実施したら、学生全員不合格？
木ではなく、森を見よ
数学的議論の詳細ではなく、議論のアイデアを把握せよ。
途中でついてこれなくなっても諦めるな
各回の講義は基本的に独立である。
一回分の講義を理解したら、それで論文１本書ける？
3

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

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

目標

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

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

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

観測行列

𝑨𝑨は平均0分散𝑀𝑀−1 のガウス分布に従う独立な成分からなる。
電力の規格化1
12
𝔼𝔼 𝑨𝑨𝑨𝑨= 𝔼𝔼 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のBG事前分布、SNR：1/𝜎𝜎 2 = 60 dB.

13

厳密性に関するコメント
文献[1-7, 1-8, 1-9]の結果を組み合わせると、前ページの結果は正しいと結論づけられる。
相互情報量𝐼𝐼(𝑥𝑥; 𝑦𝑦|𝐴𝐴)に関する厳密解[1-7] G. Reeves and H. D. Pfister, “The replica-symmetric prediction for compressed sensing with Gaussianmatrices is exact,” in Proc. 2016 IEEE Int. Symp. Inf. Theory, Barcelona, Spain, Jul. 2016, pp. 665–669.

[1-8] J. Barbier, M. Dia, N. Macris, and F. Krzakala, “The mutual information in random linear estimation,”in Proc. 54th Annual Allerton Conf. Commun. Control & Computing, Urbana-Champaign, IL, USA, Sep.
2016, pp. 625–632.

相互情報量とMMSEの厳密な関係式[1-9] D. Guo, S. Shamai (Shitz), and S. Verdú, “Mutual information and minimum mean-squareerror in Gaussian channels,” IEEE Trans. Inf. Theory, vol. 51, no. 4, pp. 1261–1282, Apr. 2005.

14

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

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

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

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

証明

� 2 = 𝔼𝔼𝒚𝒚 𝔼𝔼𝒙𝒙 𝒙𝒙 − 𝒙𝒙
�PME + 𝒙𝒙
�PME − 𝒙𝒙� 2 |𝒚𝒚
𝔼𝔼 𝒙𝒙 − 𝒙𝒙

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

∎15

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

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

事後平均推定量

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

16

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

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

最小計算量の定義

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

17

数値的比較

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

18