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

状態発展法：厳密なアプローチ１
広島市立大学
令和４年９月２６日～９月２８日
豊橋技術科学大学
電気・電子情報工学系
准教授 竹内啓悟

1

状態発展方程式
以下の状態発展方程式[3-4]の厳密な証明を与える。

𝑣𝑣 𝑡𝑡 = 𝜎𝜎 2 +1
Ψ𝑡𝑡 𝑣𝑣 𝑡𝑡−1 ,𝛿𝛿Ψ𝑡𝑡+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

誤差の発展方程式
𝑩𝑩𝑡𝑡 = 𝒃𝒃0 , … , 𝒃𝒃𝑡𝑡−1 ,𝑯𝑯𝒕𝒕 = 𝒉𝒉0 , … , 𝒉𝒉𝑡𝑡−1 ,𝚲𝚲𝑡𝑡 = diag 𝜆𝜆0 , … , 𝜆𝜆𝑡𝑡−1 ,𝑴𝑴𝑡𝑡 = 𝒎𝒎0 , … , 𝒎𝒎𝑡𝑡−1 ,𝑸𝑸𝑡𝑡 = 𝒒𝒒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 fromunitarily invariant measurements," IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 368-386, Jan. 2020.
8補題５.１の証明
� なので、𝑨𝑨� の未知の要素𝑨𝑨
� 22 は𝑼𝑼と𝑽𝑽が与えられたときに𝑨𝑨 ∼ 𝑨𝑨
𝒩𝒩(0,1/𝑀𝑀)に従う独立な要素を持つ。
−1� 𝚽𝚽𝑼𝑼T = 𝚽𝚽𝑽𝑽 𝚽𝚽𝑽𝑽T 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼𝑨𝑨 = 𝚽𝚽𝑽𝑽 𝑨𝑨= 𝚽𝚽𝑽𝑽

前者の表現を使って、

𝚺𝚺𝑽𝑽−1 𝚿𝚿𝑽𝑽T 𝒀𝒀T 𝚽𝚽𝑼𝑼⊥𝚽𝚽𝑼𝑼T
� 22𝑨𝑨𝚺𝚺𝑽𝑽−1 𝚿𝚿𝑽𝑽T 𝒀𝒀T 𝚽𝚽𝑼𝑼

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

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

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

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

∎9

Steinの補題(𝑍𝑍1 , 𝑍𝑍2 ) ∼ 𝒩𝒩(𝟎𝟎, 𝚺𝚺)とすると、𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2= 𝔼𝔼[𝑍𝑍1 𝑍𝑍2 ]𝔼𝔼 𝑓𝑓 ′ 𝑍𝑍2 .

証明 固有分解𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽T に対して、以下の変数変換を考える。
𝑍𝑍�1𝑍𝑍1T= 𝑽𝑽,�𝑍𝑍
𝑍𝑍22𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2𝑉𝑉11𝑽𝑽 =𝑉𝑉21𝑉𝑉12,𝑉𝑉22𝜆𝜆1Λ=0= 𝔼𝔼 𝑉𝑉11 𝑍𝑍�1 + 𝑉𝑉12 𝑍𝑍�2 𝑓𝑓 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�2= 𝑉𝑉11 𝔼𝔼𝑍𝑍�2 𝔼𝔼𝑍𝑍�1 𝑍𝑍�1 𝑓𝑓 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�2+𝑉𝑉12 𝔼𝔼𝑍𝑍�1 𝔼𝔼𝑍𝑍�2 𝑍𝑍�2 𝑓𝑓 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�20.
𝜆𝜆2.

最後の等号は、𝑍𝑍�1 と𝑍𝑍�2 は互いに独立なためである。

10Steinの補題の証明
𝔼𝔼 𝑍𝑍�12 = 𝜆𝜆1 と𝔼𝔼 𝑍𝑍�22 = 𝜆𝜆2 に注意して、内側の期待値の評価に一変数のSteinの補題を使う。（第３回講義資料を参照）
𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2= 𝜆𝜆1 𝑉𝑉11 𝑉𝑉21 𝔼𝔼 𝑓𝑓 ′ 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�2+𝜆𝜆2 𝑉𝑉12 𝑉𝑉22 𝔼𝔼 𝑓𝑓 ′ 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�2= 𝜆𝜆1 𝑉𝑉11 𝑉𝑉21 + 𝜆𝜆2 𝑉𝑉12 𝑉𝑉22 𝔼𝔼 𝑓𝑓 ′ 𝑍𝑍2 .

共分散行列𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽T の非対角成分を計算すると、
𝚺𝚺 12 = 𝜆𝜆1 𝑉𝑉11 𝑉𝑉21 + 𝜆𝜆2 𝑉𝑉12 𝑉𝑉22 .

したがって、Steinの補題を得る。
𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2= 𝔼𝔼[𝑍𝑍1 𝑍𝑍2 ]𝔼𝔼 𝑓𝑓 ′ 𝑍𝑍2 .

∎11