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

状態発展法：厳密なアプローチ１
九州大学
平成３０年１０月１０日～１０月１２日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1状態発展方程式
以下の状態発展方程式[3-4]の厳密な証明を与える。
1𝑣𝑣 = 𝜎𝜎 + Ψ𝑡𝑡 𝑣𝑣 𝑡𝑡−1 ,𝛿𝛿𝑡𝑡

2

Ψ𝑡𝑡+1 𝑣𝑣 = 𝔼𝔼 𝑥𝑥1 − 𝜂𝜂𝑡𝑡 𝑥𝑥1 + 𝑣𝑣𝜔𝜔12𝑣𝑣 0 = 1,,𝜔𝜔1 ∼ 𝒩𝒩 0,1 .

2Bolthausenの方法[3-4, 5-1]
1. 𝑨𝑨を𝒩𝒩(0,1/𝑀𝑀)に従う独立な要素を持つ行列とする。
2. 反復𝑡𝑡時点までのすべての推定値の履歴を条件として与えたときに、観測行列𝑨𝑨の条件付き分布を評価する。

3. 上記の条件付き分布を使って、反復𝑡𝑡 + 1での推定値の分布を厳密に計算する。
[5-1] E. Bolthausen, “An iterative construction of solutions of the TAP equations for the SherringtonKirkpatrick model,” Commun. Math. Phys., vol. 325, no. 1, pp. 333–366, Jan. 2014.
3誤差の発展方程式
AMP[3-1]′𝑡𝑡−1 + 𝑨𝑨T 𝒛𝒛𝑡𝑡−1
�𝜂𝜂𝒙𝒙
𝑡𝑡−1𝒛𝒛𝑡𝑡 = 𝒚𝒚 − 𝑨𝑨�
𝒙𝒙𝑡𝑡 +𝛿𝛿�𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 .
𝒙𝒙𝒛𝒛𝑡𝑡−1 ,𝒛𝒛−1 = 𝟎𝟎,

誤差の発展方程式

�𝑡𝑡 − 𝒙𝒙 、 𝒉𝒉𝑡𝑡 = 𝒙𝒙
�𝑡𝑡 + 𝑨𝑨T 𝒛𝒛𝑡𝑡 − 𝒙𝒙 と誤差を定義する。
𝒒𝒒𝑡𝑡 = 𝒙𝒙
𝒎𝒎𝑡𝑡 = 𝒛𝒛𝑡𝑡 、𝒃𝒃𝑡𝑡 = 𝒘𝒘 − 𝒛𝒛𝑡𝑡 とすると、
𝒒𝒒𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙 + 𝒉𝒉𝑡𝑡 − 𝒙𝒙,

𝒎𝒎𝑡𝑡 = 𝒘𝒘 − 𝒃𝒃𝑡𝑡 ,𝒉𝒉𝑡𝑡 = 𝑨𝑨T 𝒎𝒎𝑡𝑡 + 𝒒𝒒𝑡𝑡 ,𝒃𝒃𝑡𝑡 = 𝑨𝑨𝒒𝒒𝑡𝑡 − 𝜆𝜆𝑡𝑡−1 𝒎𝒎𝑡𝑡−1 ,𝜂𝜂𝑡𝑡′ 𝒙𝒙 + 𝒉𝒉𝑡𝑡
𝜆𝜆𝑡𝑡 =
𝛿𝛿.

4

誤差の発展方程式
𝑩𝑩𝒕𝒕 = 𝒃𝒃𝟎𝟎 , … , 𝒃𝒃𝒕𝒕−𝟏𝟏 ,𝑯𝑯𝒕𝒕 = 𝒉𝒉𝟎𝟎 , … , 𝒉𝒉𝒕𝒕−𝟏𝟏 ,𝚲𝚲𝑡𝑡 = diag 𝜆𝜆0 , … , 𝜆𝜆𝑡𝑡−1 ,𝑴𝑴𝒕𝒕 = 𝒎𝒎𝟎𝟎 , … , 𝒎𝒎𝒕𝒕−𝟏𝟏 ,𝑸𝑸𝒕𝒕 = 𝒒𝒒𝟎𝟎 , … , 𝒒𝒒𝒕𝒕−𝟏𝟏 ,上記の定義を使うと、

𝟎𝟎, 𝑴𝑴0 𝚲𝚲0 = 𝟎𝟎,𝑾𝑾𝑡𝑡 = 𝒘𝒘, … , 𝒘𝒘 ∈ ℝ𝑀𝑀×𝑡𝑡 .

𝑩𝑩𝑡𝑡 = 𝑨𝑨𝑸𝑸𝑡𝑡 − (𝟎𝟎, 𝑴𝑴𝑡𝑡−1 𝚲𝚲𝑡𝑡−1 ), 𝑴𝑴𝑡𝑡 = 𝑾𝑾𝑡𝑡 − 𝑩𝑩𝑡𝑡 ,𝑯𝑯𝑡𝑡 = 𝑨𝑨T 𝑴𝑴𝑡𝑡 + 𝑸𝑸𝑡𝑡 ,𝒒𝒒𝑡𝑡+1 = 𝜂𝜂𝑡𝑡 𝒙𝒙 + 𝒉𝒉𝑡𝑡 − 𝒙𝒙.

5特異値分解と射影行列
フルランク縦長行列𝑴𝑴の特異値分解
𝑴𝑴 = 𝚽𝚽𝑴𝑴

一般化逆行列

𝑴𝑴† =

𝚺𝚺𝑴𝑴T
𝚿𝚿𝑴𝑴
,𝑶𝑶

∥⊥
𝚽𝚽𝑴𝑴 = 𝚽𝚽𝑴𝑴, 𝚽𝚽𝑴𝑴.

−1 T∥ T−1T
𝑴𝑴 𝑴𝑴 𝑴𝑴 = 𝚿𝚿𝑴𝑴 𝚺𝚺𝑴𝑴 𝚽𝚽𝑴𝑴 .

𝑴𝑴が張る空間への射影

∥∥
∥ T
†
𝑷𝑷𝑴𝑴 = 𝑴𝑴𝑴𝑴 = 𝚽𝚽𝑴𝑴 𝚽𝚽𝑴𝑴 .

直交補空間への射影∥⊥⊥⊥ T
𝑷𝑷𝑴𝑴 = 𝑰𝑰 − 𝑷𝑷𝑴𝑴 = 𝚽𝚽𝑴𝑴 𝚽𝚽𝑴𝑴 .

6

補題５.１[3-4]𝑨𝑨 を 𝒩𝒩(0,1/𝑀𝑀) に従う独立な要素を持つ行列とする。
𝑀𝑀×𝑡𝑡 、𝒀𝒀 ∈ ℝ𝑁𝑁×𝑡𝑡 ′ 、𝑼𝑼 ∈ ℝ𝑁𝑁×𝑡𝑡 、𝑽𝑽 ∈ ℝ𝑀𝑀×𝑡𝑡 ′ を𝑿𝑿 ∈ ℝ
縦長行列とし、以下の制約を満たすものとする。
𝑿𝑿 = 𝑨𝑨𝑨𝑨,𝒀𝒀 = 𝑨𝑨T 𝑽𝑽.

𝑼𝑼と𝑽𝑽がフルランクならば、上記の制約を満たすという条件の下で、𝑨𝑨は以下と統計的に等価である。
T T ⊥⊥�⊥ T†
𝑽𝑽 𝒀𝒀 𝑷𝑷𝑼𝑼 + 𝚽𝚽𝑽𝑽 𝑨𝑨 𝚽𝚽𝑼𝑼
T T⊥
⊥�⊥ T††∼ 𝑷𝑷𝑽𝑽 𝑿𝑿𝑼𝑼 + 𝑽𝑽 𝒀𝒀 + 𝚽𝚽𝑽𝑽 𝑨𝑨 𝚽𝚽𝑼𝑼 .

𝑨𝑨 ∼ 𝑿𝑿𝑼𝑼† +� は𝑨𝑨と独立で、𝒩𝒩(0,1/𝑀𝑀)に従う独立な要素を持
ただし、𝑨𝑨つ行列である。
7

補題５.１の証明[5-2]𝚺𝚺𝑼𝑼
𝑼𝑼 = 𝚽𝚽𝑼𝑼𝚿𝚿𝑼𝑼T ,𝑶𝑶𝚺𝚺𝑽𝑽
𝑽𝑽 = 𝚽𝚽𝑽𝑽
𝚿𝚿𝑽𝑽T .
𝑶𝑶𝚺𝚺𝑼𝑼,𝑶𝑶

𝚺𝚺𝑽𝑽,𝑶𝑶

上記の特異値分解を二つの制約式に代入すると、
�𝚽𝚽𝑽𝑽T 𝑿𝑿𝚿𝚿𝑼𝑼 = 𝑨𝑨
�11𝑨𝑨
�=𝑨𝑨� 21𝑨𝑨�T𝚽𝚽𝑼𝑼T 𝒀𝒀𝚿𝚿𝑽𝑽 = 𝑨𝑨

�12𝑨𝑨と分解すると、
�𝑨𝑨22

�11𝑨𝑨
−1= 𝚽𝚽𝑽𝑽T 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼,�𝑨𝑨21

� = 𝚽𝚽𝑽𝑽T 𝑨𝑨𝚽𝚽𝑼𝑼 .
𝑨𝑨

�11 , 𝑨𝑨
�12 = 𝚺𝚺𝑽𝑽−1 𝚿𝚿𝑽𝑽T 𝒀𝒀T 𝚽𝚽𝑼𝑼 .
𝑨𝑨[5-2] K. Takeuchi, “Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariantmeasurements,” in Proc. 2017 IEEE Int. Symp. Inf. Theory, Aachen, Germany, Jun. 2017, pp. 501–505.
8補題５.１の証明
� なので、𝑨𝑨� の未知の要素𝑨𝑨
� 22 は𝒩𝒩(0,1/𝑀𝑀)に従う𝑨𝑨 ∼ 𝑨𝑨
独立な要素を持つ。
−1 T T ⊥𝚺𝚺𝑽𝑽 𝚿𝚿𝑽𝑽 𝒀𝒀 𝚽𝚽𝑼𝑼TT−1�𝑨𝑨 = 𝚽𝚽𝑽𝑽 𝑨𝑨𝚽𝚽𝑼𝑼 = 𝚽𝚽𝑽𝑽 𝚽𝚽𝑽𝑽 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼𝚽𝚽𝑼𝑼T
� 22𝑨𝑨= 𝚽𝚽𝑽𝑽

前者の表現を使って、

𝚺𝚺𝑽𝑽−1 𝚿𝚿𝑽𝑽T 𝒀𝒀T 𝚽𝚽𝑼𝑼

⊥ T−1𝚽𝚽𝑽𝑽 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼

� 22𝑨𝑨𝚽𝚽𝑼𝑼T∥ T∥ −1 T T ⊥−1⊥�⊥ T
𝑨𝑨 = 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼 𝚽𝚽𝑼𝑼 + 𝚽𝚽𝑽𝑽 𝚺𝚺𝑽𝑽 𝚿𝚿𝑽𝑽 𝒀𝒀 𝑷𝑷𝑼𝑼 + 𝚽𝚽𝑽𝑽 𝑨𝑨22 𝚽𝚽𝑼𝑼†

= 𝑿𝑿𝑼𝑼 +⊥�
⊥ T† T T ⊥𝑽𝑽 𝒀𝒀 𝑷𝑷𝑼𝑼 + 𝚽𝚽𝑽𝑽 𝑨𝑨22 𝚽𝚽𝑼𝑼 .

もう一つの表現は後者から得られる。

∎9

補題５.１の注意
� 𝒗𝒗が次ページの主定理の証明で必要な性質は、ベクトル𝑨𝑨
平均𝟎𝟎の𝐾𝐾体独立なガウス分布に従うという性質である。

例えば、𝑨𝑨をハール直交行列[5-3]に取ると、この性質を満たす。
• AMPはハール直交する観測行列を使用すると、収束性が保証されて、i.i.d.ガウス観測行列と同じ性能を達成する？
• ベイズ最適な性能[5-4]は𝑨𝑨の経験特異値分布に依存するため、この場合のAMPは常に最適でない。
[5-3] S. Chatterjee and E. Meckes, “Multivariate normal approximation using exchangeable pairs,”
ALEA Latin. Amer. J. Prob. Math. Stat., vol. 4, pp. 257–283, 2008.
[5-4] K. Takeda, S. Uda, and Y. Kabashima, “Analysis of CDMA systems that are characterized byeigenvalue spectrum,” Europhys. Lett., vol. 76, no. 6, pp. 1193–1199, 2006.
10

主定理[3-4]大システム極限で、以下が成り立つ。
(a)(b)(c)(d)(e)

𝒃𝒃𝑡𝑡 ∼ 𝑩𝑩𝑡𝑡 𝜷𝜷𝑡𝑡 + 𝝃𝝃𝑡𝑡 ,2 𝑰𝑰𝝃𝝃𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒒𝒒⊥
𝑀𝑀 .
𝑡𝑡

𝒉𝒉𝑡𝑡 ∼ 𝑯𝑯𝑡𝑡 𝜶𝜶𝑡𝑡 + 𝜻𝜻𝑡𝑡 ,𝜻𝜻𝑡𝑡 ∼ 𝒩𝒩 𝟎𝟎, 𝑀𝑀−1 𝒎𝒎𝑡𝑡⊥ 2 𝑰𝑰𝑁𝑁 .
1 T
1 T
1 T
1 T𝒉𝒉𝑡𝑡 𝒉𝒉𝑡𝑡 ′ − 𝒎𝒎𝑡𝑡 𝒎𝒎𝑡𝑡 ′ → 0,𝒃𝒃𝑡𝑡 𝒃𝒃𝑡𝑡 ′ −𝒒𝒒𝑡𝑡 𝒒𝒒𝑡𝑡 ′ → 0.
𝑁𝑁𝑀𝑀𝑀𝑀𝛿𝛿𝛿𝛿
1 T𝛿𝛿𝜆𝜆𝑡𝑡 ′−1 T𝒉𝒉𝑡𝑡 𝒒𝒒𝑡𝑡 ′ −𝒉𝒉𝑡𝑡 𝒉𝒉𝑡𝑡 ′−1 → 0.
𝑁𝑁
𝑁𝑁
1 T
1 T𝒉𝒉𝑡𝑡 𝒙𝒙 → 0.
𝒃𝒃𝑡𝑡 𝒘𝒘 → 0,𝑁𝑁𝑁𝑁𝜶𝜶𝑡𝑡 = 𝑴𝑴†𝑡𝑡 𝒎𝒎𝑡𝑡 ,𝒎𝒎𝑡𝑡⊥ = 𝑷𝑷⊥
𝑴𝑴𝑡𝑡 𝒎𝒎𝑡𝑡 ,𝜷𝜷𝑡𝑡 = 𝑸𝑸𝑡𝑡† 𝒒𝒒𝑡𝑡 = 𝛽𝛽0 , … , 𝛽𝛽𝑡𝑡−1 T ,
⊥𝒒𝒒⊥
=𝑷𝑷𝑡𝑡
𝑸𝑸𝑡𝑡 𝒒𝒒𝑡𝑡 .

11

状態発展方程式の導出
性質(b)から、誤差𝒉𝒉𝑡𝑡 はガウス分布に従うi.i.d.成分からなることが言える。
以下を仮定して、N−1 𝒒𝒒T𝑡𝑡+1 𝒒𝒒𝑡𝑡+1 を評価する。
1 T
1 T
𝑡𝑡−1𝑡𝑡𝒒𝒒𝑡𝑡 𝒒𝒒𝑡𝑡 → Ψ𝑡𝑡 𝑣𝑣,
𝑣𝑣 = 𝒉𝒉𝑡𝑡 𝒉𝒉𝑡𝑡 .
𝑁𝑁
𝑁𝑁

性質(c)(e)、定義𝒎𝒎𝑡𝑡 = 𝒘𝒘 − 𝒃𝒃𝑡𝑡 、大数の強法則を使って、
𝑣𝑣 𝑡𝑡 →

1 T
1 T
122𝒎𝒎𝑡𝑡 𝒎𝒎𝑡𝑡 → 𝜎𝜎 + 𝒃𝒃𝑡𝑡 𝒃𝒃𝑡𝑡 → 𝜎𝜎 + Ψ𝑡𝑡 (𝑣𝑣 𝑡𝑡−1 ).
𝑀𝑀𝑀𝑀
𝛿𝛿
𝑁𝑁

1 T
1𝒒𝒒𝑡𝑡+1 𝒒𝒒𝑡𝑡+1 = � 𝜂𝜂𝑡𝑡 𝑥𝑥𝑛𝑛 + 𝒉𝒉𝑡𝑡 𝑛𝑛 − 𝑥𝑥𝑛𝑛 2 → Ψ𝑡𝑡+1 𝑣𝑣 𝑡𝑡 .
𝑁𝑁𝑁𝑁
𝑛𝑛=112