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

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

1Bolthausenの方法[3-3, 5-1]
GAMPの状態発展方程式[3-3, 3-4]の厳密な証明を与える。
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.
2

誤差の発展方程式�0 = 𝟎𝟎と�𝒛𝒛−1 = 𝟎𝟎として、
𝒙𝒙𝜉𝜉in,𝑡𝑡−1𝒛𝒛𝑡𝑡 = 𝑨𝑨�𝒙𝒙𝑡𝑡 +𝒛𝒛� 𝑡𝑡−1 ,𝒛𝒛� 𝑡𝑡 = 𝜂𝜂out,𝑡𝑡 𝒛𝒛𝑡𝑡 , 𝒚𝒚 ,𝛿𝛿𝜉𝜉out,𝑡𝑡−1
1
�𝑡𝑡 −�𝑡𝑡+1 = 𝜂𝜂in,𝑡𝑡 𝒙𝒙𝑡𝑡
𝑨𝑨T 𝒛𝒛� 𝑡𝑡 ,𝒙𝒙𝑡𝑡 = 𝒙𝒙𝒙𝒙
𝜉𝜉out,𝑡𝑡

GAMP[3-4]

̅−1 𝒙𝒙、𝒉𝒉𝑡𝑡 = 𝒙𝒙𝑡𝑡 − 𝜁𝜁𝑡𝑡̅ 𝜉𝜉out,𝑡𝑡
̅−1 𝒙𝒙を定義する。
�𝑡𝑡 − 𝜁𝜁𝑡𝑡̅ 𝜉𝜉out,𝑡𝑡
誤差 𝒒𝒒𝑡𝑡 = 𝒙𝒙−1
̅−1 𝒛𝒛とし、 𝒛𝒛 = 𝑨𝑨𝑨𝑨を使って𝒎𝒎𝑡𝑡 = 𝜉𝜉out,𝑡𝑡
𝒛𝒛� 𝑡𝑡 、𝒃𝒃𝑡𝑡 = 𝒛𝒛𝑡𝑡 − 𝜁𝜁𝑡𝑡̅ 𝜉𝜉out,𝑡𝑡̅𝜁𝜁𝑡𝑡̅
𝜁𝜁𝑡𝑡+1
𝒒𝒒𝑡𝑡+1 = 𝜂𝜂in,𝑡𝑡
𝒙𝒙 + 𝒉𝒉𝑡𝑡 −𝒙𝒙, 𝒉𝒉𝑡𝑡 = 𝒒𝒒𝑡𝑡 − 𝑨𝑨T 𝒎𝒎𝑡𝑡 ,̅̅𝜉𝜉out,𝑡𝑡𝜉𝜉out,𝑡𝑡+11𝜁𝜁𝑡𝑡̅𝜉𝜉in,𝑡𝑡−1
𝒎𝒎𝑡𝑡 =
𝜂𝜂out,𝑡𝑡𝒛𝒛 + 𝒃𝒃𝑡𝑡 , 𝒚𝒚 , 𝒃𝒃𝑡𝑡 = 𝑨𝑨𝒒𝒒𝑡𝑡 +𝒎𝒎𝑡𝑡−1̅𝜉𝜉out,𝑡𝑡𝜉𝜉out,𝑡𝑡𝛿𝛿
̅−1 𝒙𝒙、𝒎𝒎−1 = 𝟎𝟎
ただし、𝒒𝒒0 = −𝜁𝜁0̅ 𝜉𝜉out,03

誤差の発展方程式
𝑩𝑩𝑡𝑡 = 𝒃𝒃0 , … , 𝒃𝒃𝑡𝑡−1 ,𝑯𝑯𝒕𝒕 = 𝒉𝒉0 , … , 𝒉𝒉𝑡𝑡−1 ,𝑴𝑴𝑡𝑡 = 𝒎𝒎0 , … , 𝒎𝒎𝑡𝑡−1 ,𝑸𝑸𝑡𝑡 = 𝒒𝒒0 , … , 𝒒𝒒𝑡𝑡−1 ,1𝚲𝚲𝑡𝑡 = diag 𝜉𝜉in,0 , … , 𝜉𝜉in,𝑡𝑡−1 ,𝛿𝛿

𝟎𝟎, 𝑴𝑴0 𝚲𝚲0 = 𝟎𝟎,

上記の定義を使うと、𝑩𝑩𝑡𝑡 = 𝑨𝑨𝑸𝑸𝑡𝑡 + (𝟎𝟎, 𝑴𝑴𝑡𝑡−1 𝚲𝚲𝑡𝑡−1 ),𝑯𝑯𝑡𝑡 = 𝑸𝑸𝑡𝑡 − 𝑨𝑨T 𝑴𝑴𝑡𝑡 ,𝒎𝒎𝑡𝑡 = 𝜂𝜂out,𝑡𝑡

𝒒𝒒𝑡𝑡+1 = 𝜂𝜂in,𝑡𝑡

𝜁𝜁𝑡𝑡̅

̅
𝜉𝜉out,𝑡𝑡𝜁𝜁𝑡𝑡̅̅𝜉𝜉out,𝑡𝑡

𝒛𝒛 + 𝒃𝒃𝑡𝑡 , 𝒚𝒚 ,𝒙𝒙 + 𝒉𝒉𝑡𝑡̅𝜁𝜁𝑡𝑡+1−𝒙𝒙,̅𝜉𝜉𝑡𝑡+14特異値分解と射影行列
フルランク縦長行列𝑴𝑴の特異値分解
𝑴𝑴 = 𝚽𝚽𝑴𝑴

一般化逆行列† =𝑴𝑴𝚺𝚺𝑴𝑴T,
𝚿𝚿𝑴𝑴𝑶𝑶∥⊥𝚽𝚽𝑴𝑴 = 𝚽𝚽𝑴𝑴, 𝚽𝚽𝑴𝑴.

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

𝑴𝑴が張る空間への射影∥∥∥ T†
𝑷𝑷𝑴𝑴 = 𝑴𝑴𝑴𝑴 = 𝚽𝚽𝑴𝑴 𝚽𝚽𝑴𝑴 .

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

5

補題５.１[3-3]𝑨𝑨 を 𝒩𝒩(0,1/𝑀𝑀) に従う独立な要素を持つ行列とする。

𝑿𝑿 ∈ ℝ𝑀𝑀×𝑡𝑡

𝑁𝑁×𝑡𝑡 ′

𝑁𝑁×𝑡𝑡

𝑀𝑀×𝑡𝑡 ′、𝒀𝒀 ∈ ℝ、𝑼𝑼 ∈ ℝ 、𝑽𝑽 ∈ ℝ
を縦長行列とし、以下の制約を満たすものとする。
𝑿𝑿 = 𝑨𝑨𝑨𝑨,𝒀𝒀 = 𝑨𝑨T 𝑽𝑽.

𝑼𝑼と𝑽𝑽がフルランクならば、𝑿𝑿、𝑼𝑼、𝒀𝒀、𝑽𝑽が与えられたときに、𝑨𝑨は以下の分布に従う。
T T ⊥⊥�⊥ T†𝑽𝑽 𝒀𝒀 𝑷𝑷𝑼𝑼 + 𝚽𝚽𝑽𝑽 𝑨𝑨 𝚽𝚽𝑼𝑼
T T⊥⊥�⊥ T††∼ 𝑷𝑷𝑽𝑽 𝑿𝑿𝑼𝑼 + 𝑽𝑽 𝒀𝒀 + 𝚽𝚽𝑽𝑽 𝑨𝑨 𝚽𝚽𝑼𝑼 .

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

6

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

𝑽𝑽 = 𝚽𝚽𝑽𝑽𝚺𝚺𝑽𝑽𝚿𝚿𝑽𝑽T .
𝑶𝑶

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

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

� 11𝑨𝑨= 𝚽𝚽𝑽𝑽T 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼−1 ,� 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.
7補題５.１の証明
� なので、𝑨𝑨� の未知の要素𝑨𝑨
� 22 は𝑼𝑼と𝑽𝑽が与えられたときに𝑨𝑨 ∼ 𝑨𝑨
𝒩𝒩(0,1/𝑀𝑀)に従う独立な要素を持つ。
� 𝚽𝚽𝑼𝑼T = 𝚽𝚽𝑽𝑽 𝚽𝚽𝑽𝑽T 𝑿𝑿𝚿𝚿𝑼𝑼 𝚺𝚺𝑼𝑼−1
𝑨𝑨 = 𝚽𝚽𝑽𝑽 𝑨𝑨= 𝚽𝚽𝑽𝑽

前者の表現を使って、

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

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

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

∎8

Steinの補題
𝑍𝑍 ∼ 𝒩𝒩(0, 𝜎𝜎 2 )とすると、証明

𝔼𝔼 𝑍𝑍𝑍𝑍 𝑍𝑍= 𝜎𝜎 2 𝔼𝔼 𝑓𝑓 ′ 𝑍𝑍 .

𝑝𝑝 𝑧𝑧 =𝔼𝔼 𝑍𝑍𝑍𝑍 𝑍𝑍

12𝜋𝜋𝜎𝜎 2𝑧𝑧 2−𝑒𝑒 2𝜎𝜎2 ,= �𝑧𝑧𝑧𝑧 𝑧𝑧 𝑝𝑝 𝑧𝑧 𝑑𝑑𝑑𝑑 = −𝜎𝜎 2 �𝑓𝑓 𝑧𝑧 𝑝𝑝′ 𝑧𝑧 𝑑𝑑𝑑𝑑
= 𝜎𝜎 2 �𝑓𝑓 ′ 𝑧𝑧 𝑝𝑝 𝑧𝑧 𝑑𝑑𝑑𝑑 = 𝜎𝜎 2 𝔼𝔼 𝑓𝑓 ′ 𝑍𝑍 .

∎9Steinの補題の一般化(𝑍𝑍1 , 𝑍𝑍2 , 𝑍𝑍3 ) ∼ 𝒩𝒩(𝟎𝟎, 𝚺𝚺)とすると、
𝜕𝜕𝜕𝜕𝜕𝜕𝜕𝜕
𝑍𝑍2 , 𝑍𝑍3 + 𝔼𝔼[𝑍𝑍1 𝑍𝑍3 ]𝔼𝔼
𝑍𝑍2 , 𝑍𝑍3 .
𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3 = 𝔼𝔼 𝑍𝑍1 𝑍𝑍2 𝔼𝔼
𝜕𝜕𝑍𝑍2
𝜕𝜕𝑍𝑍3証明 固有分解𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽T に対して、以下の変数変換を考える。
𝑍𝑍�1𝜆𝜆1 0 0
𝑍𝑍1𝑉𝑉11 𝑉𝑉12 𝑉𝑉13𝑍𝑍�2 = 𝑽𝑽T 𝑍𝑍2 , 𝑽𝑽 = 𝑉𝑉21 𝑉𝑉22 𝑉𝑉23 , 𝚲𝚲 = 0 𝜆𝜆2 0 .
𝑍𝑍3𝑉𝑉31 𝑉𝑉32 𝑉𝑉33
0 0 𝜆𝜆3𝑍𝑍�3𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3= 𝔼𝔼 𝑉𝑉11 𝑍𝑍�1 + 𝑉𝑉12 𝑍𝑍�2 + 𝑉𝑉13 𝑍𝑍�3 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3= 𝑉𝑉11 𝔼𝔼 𝔼𝔼𝑍𝑍�1 𝑍𝑍�1 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3+𝑉𝑉13 𝔼𝔼 𝔼𝔼𝑍𝑍�3 𝑍𝑍�3 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3+ 𝑉𝑉12 𝔼𝔼 𝔼𝔼𝑍𝑍�2 𝑍𝑍�2 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3.

最後の等号は、{𝑍𝑍�1 , 𝑍𝑍�2 , 𝑍𝑍�3 }は独立なためである。

10

Steinの補題の証明
𝑍𝑍2 = 𝑉𝑉21 𝑍𝑍�1 + 𝑉𝑉22 𝑍𝑍�2 + 𝑉𝑉23 𝑍𝑍�3 , 𝑍𝑍3 = 𝑉𝑉31 𝑍𝑍�1 + 𝑉𝑉32 𝑍𝑍�2 + 𝑉𝑉33 𝑍𝑍�3𝔼𝔼 𝑍𝑍�𝑖𝑖2 = 𝜆𝜆𝑖𝑖 に注意し、内側の期待値に一変数のSteinの補題を使う。
𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3𝜕𝜕𝜕𝜕𝜕𝜕𝜕𝜕= 𝜆𝜆1 𝑉𝑉11 𝑉𝑉21 𝔼𝔼+ 𝑉𝑉31 𝔼𝔼
𝜕𝜕𝑍𝑍2𝜕𝜕𝑍𝑍3𝜕𝜕𝜕𝜕𝜕𝜕𝜕𝜕+𝜆𝜆2 𝑉𝑉12 𝑉𝑉22 𝔼𝔼+ 𝑉𝑉32 𝔼𝔼
𝜕𝜕𝑍𝑍2𝜕𝜕𝑍𝑍3𝜕𝜕𝜕𝜕𝜕𝜕𝜕𝜕+𝜆𝜆3 𝑉𝑉13 𝑉𝑉23 𝔼𝔼+ 𝑉𝑉33 𝔼𝔼
𝜕𝜕𝑍𝑍2
𝜕𝜕𝑍𝑍3共分散行列𝚺𝚺 = 𝑽𝑽𝚲𝚲𝑽𝑽T の非対角成分を計算すると、𝔼𝔼 𝑍𝑍1 𝑍𝑍𝑗𝑗 = 𝚺𝚺 1𝑗𝑗 = 𝜆𝜆1 𝑉𝑉11 𝑉𝑉𝑗𝑗1 + 𝜆𝜆2 𝑉𝑉12 𝑉𝑉𝑗𝑗2 + 𝜆𝜆3 𝑉𝑉13 𝑉𝑉𝑗𝑗𝑗 .

よって、

𝔼𝔼 𝑍𝑍1 𝑓𝑓 𝑍𝑍2 , 𝑍𝑍3𝜕𝜕𝜕𝜕
𝜕𝜕𝜕𝜕= 𝔼𝔼 𝑍𝑍1 𝑍𝑍2 𝔼𝔼+ 𝔼𝔼[𝑍𝑍1 𝑍𝑍3 ]𝔼𝔼
𝜕𝜕𝑍𝑍2
𝜕𝜕𝑍𝑍3∎

11