メッセージ伝播法の入門から最先端まで
第１回講義資料

導入
九州大学
令和元年１０月９日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1

本講義の概要目標• 近似的メッセージ伝播法(AMP)の導出方法を理解する。

• AMPに現れるオンサーガー補正項の役割を理解する。
• AMPが適用可能な問題のクラスを理解する。

アプローチ
数学的に厳密な議論を通じて、上記の理解を得る。
AMPとランダム行列理論との間の深遠な関係
必要な能力
線形代数、微分積分学、確率論、複素関数論、(離散)力学系理論（Z変換）等に関する十分な知識と並外れた忍耐力
2

本講義が目指しているもの
通常の集中講義
関連する話題を浅く広く紹介して、なるべく多数の受講者の興味を引く講義をする。
面白かったという印象は残るが、実際の研究には何の役にも立たない。

本講義
新規の参入障壁は高い（勉強の忍耐力が続かない）が、役に立つ最先端の研究を講義する。
本講義をマスターすれば、トップジャーナルに楽々通るような論文が書ける。
3

数理モデル
線形観測モデル𝒚 = 𝑨𝒙 + 𝒘,𝒘 ∼ 𝒩(𝟎, 𝜎 2 𝑰𝑁 )𝒚 = 𝑦1 , … , 𝑦𝑀 T ∈ ℝ𝑀 ：𝑀次元観測ベクトル𝒙 = 𝑥1 , … , 𝑥𝑁 T ∈ ℝ𝑁 ：𝑁次元信号ベクトル𝒘 = 𝑤1 , … , 𝑤𝑀 T ∈ ℝ𝑀 ：𝑀次元ノイズベクトル
𝑨 = [𝐴𝑚𝑛 ] ∈ ℝ𝑀×𝑁 ：𝑀行𝑁列の観測行列
目標

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

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

本講義では、この条件の必要性を論じる。
電力の規格化
112𝔼 𝑨𝒙= 𝔼 Tr 𝑨𝑨T
𝑁
𝑁= 1.
5

Multiple-input multiple-output (MIMO)
𝑥1 = ±1ユーザ11𝑥2 = ±1

ユーザ2・・・

𝑀

𝑨
基地局・・・𝑥𝑁 = ±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 analogcompression,” 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 Gaussian
matrices 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