更正

最后一个$r_i^t$的表达式写错了，改了过来。欢迎各位指出错误，可以在评论区交流。

开始

找了很久都没有找到一个比较详细的关于近似消息传递（AMP）的详尽推导，本文旨从因子图角度对其进行推导。

先验知识

在进行AMP的推导之前，我们首先需要一些先验知识：

1. 消息，因子图与和积算法（Sum Product Algorithm, SPA）:这一部分在通信中的变分推理技术--因子图和消息传递方法的第2-3章有较为详细的描述，此处只做简述。

首先，我们的问题可以转化为对某些感兴趣变量（如$\bf x$等）的估计，而这个估计一般会在又一般会在全局函数（$p(\bf x, \bf y |\bf H)$）上进行。在这上面直接计算最大后验估计（MAP）或最小均方误差估计（MMSE）是可以达到全局最优的，但是这种计算复杂度一般是不可承受的（一般而言会是NP-Hard）。

因此，我们会对全局函数进行因式分解，并且对其进行分块，再迭代计算局部最优。在因子图中，因式分解后的全局函数中包含两类节点，变量节点和因子节点。因子节点是全局函数中的部分因子，而变量节点为因子所含的变量。因子图是二部图，两类节点只能与不同类型的节点连接。在两类节点中传递的关于因子的概率密度函数（PDF），被称为消息。计算消息的方法便是消息传递算法。

在这里，我们使用SPA作为我们的消息传递算法，它包含变量节点到与其相连的因子节点和因子节点到与其相连的变量节点的消息计算方式。计算公式为： $$\mu_{i\to a}^{t+1}(x_i)\propto \prod_{b\neq a}^{M}\mu_{b\to i}^{t}(x_i) $$ $$ \mu_{a\to i}^{t}(x_{i})\propto\int f_a(\mathbf{x})\prod_{j\neq i}^{N}\mu_{j\rightarrow a}^{t}(x_{j})\mathrm{d}\mathbf{x}_{\setminus i} $$ 其中$x_i$为变量，$f_a(\mathbf{x})$为全局函数的一个因子，$\mu^{t}$代表第$t$次迭代时传递的消息，由其下标指明方向，$\mathbf{x}_{\setminus i}$代表对除了$x_i$的其余$x$。基于上述公式可以将消息在变量节点和因子节点中迭代。此方式又被称为置信传播（BP），在无环图中，BP可以很快得到最优解，但如果存在环，传递的消息便会存在偏差。 2. 高斯合并引理：令$\mathcal{N}\left(x; \mu, \sigma^2 \right)$表示均值为$\mu$，方差为$\sigma^2$的高斯PDF，则两个高斯PDF（注意是PDF不是随机变量）的乘积可以写成另外两个高斯变量的乘积。用公式表示为： $$ \mathcal{N}(x;a,A)\mathcal{N}(x;b,B)~=~\mathcal{N}(x;c,C)\mathcal{N}(0;a~-~b,A~+~B) $$ 其中$C=(A^{-1}+B^{-1})^{-1}$, $c=C\left(\frac{a}{A}+\frac{b}{B}\right)$.

3. 中心极限定理：一系列独立零均值和有限方差的随机变量求和后得到的新随机变量是高斯的。这是中心极限定理的第三类形式（Lindeberg-Feller）。令$X_i,i=1,\cdots,N$为独立随机变量序列，同时假设$E[X_{i}]=0$，并记 $$ S_n=\sum_{i=1}^nX_i $$ $$ s_i^2=\operatorname{Var}(X_i) $$ $$ \sigma_n^2=\sum_{i=1}^ns_i^2=\operatorname{Var}(S_n) $$ 假设对任意$\epsilon>0$均有 $$ \lim\limits_{n\to\infty}\frac{1}{\sigma_n^2}\sum\limits_{i=1}^nE[X_i^2;\{|X_i|>\epsilon\sigma_n\}]=0\qquad(Lindeberg) $$ 则 $$ S_n/\sigma_n\overset{d}{\rightarrow}N(0,1) $$ 注意需要$X_i$严格独立，是否同分布并不重要。

若$X_i$中仅存在有限类不同类型的分布，则其退化为独立同分布中心极限定理的求和形式，此时可以对上述部分条件进行放宽。

具体推导

对于以下系统： $$ \bf y=\bf{Hx}+\bf{n}, $$ 其中$\bf x \in \mathbb{R}^N$为被估计信号，$\bf H \in \mathbb{R}^{M\times N}$为已知矩阵，$\bf y \in \mathbb{R}^M$为已知接收信号，$\bf n \in \mathbb{R}^M$为高斯噪声矢量，其元素服从独立的$\mathcal N\left(n_i; 0,N_0\right)$.

其全局函数为 $$p\left({\bf{x}},{\bf{y}}|{\bf{H}}\right) = p({\bf{x}})p({\bf{y}}|{\bf{x}},{\bf{H}})$$ 其因子图为

 

由于$p(x_i)$和$y_i$均为已知量，因此在这张因子图中，我们需要推导两类消息，即变量节点$x_i$到因子节点$p(y_a|\bf x ,\bf H)$的消息$\mu_{i\rightarrow a}$和反向传播的消息$\mu_{a\rightarrow i}$.但我们最终需要的并不完全是消息，而是信号在以下概率密度函数下的均值与方差

$$ {p^t}({x_i}) = p(x_i)\prod\limits_{a = 1}^M {{\mu _{a \to i}^t}} ({x_i}) $$

此概率密度函数被称为近似的边缘概率,为某变量的PDF在因子图中的近似值。

反向消息

首先考虑$\mu_{a\rightarrow i}$，由SPA算法，可以得到

$$ \mu_{a\rightarrow i}^{t} = \int p_a(y_a|\mathbf{x},{\bf H})\prod_{j\neq i}^{N}\mu_{j\rightarrow a}^{t}(x_{j})\mathrm{d}\mathbf{x}_{\setminus i} $$

由于 $$\begin{aligned} p({y_a}|{\bf{x}},{\bf{H}}) &= {\mathcal N}\left( {{y_a};\sum\limits_k {{h_{ak}}{x_k}} ,{N_0}} \right)\\ &= {\mathcal N}\left( {{y_a};\sum\limits_{k \ne i} {{h_{ak}}{x_k} + {h_{ai}}{x_i}} ,{N_0}} \right)\\ &= {\mathcal N}\left( {{y_a};{h_{ai}}{x_i} + {S_{a \to i}},{N_0}} \right) \end{aligned}$$ 其中${S_{a \to i}} = \sum\limits_{k \ne i} {{h_{ak}}{x_k}}$，为一系列独立随机变量$x_k$的求和。

同时，消息变为 $$ \begin{aligned} \mu _{a \to i}^t &= \int {\mathcal N\left( {{y_a};{h_{ai}}{x_i} + {S_{a \to i}},{N_0}} \right)p\left( {{S_{a \to i}}|{{\bf{x}}_{\backslash i}}} \right)\prod\limits_{j \ne i}^N {{p_{j \to a}}} ({x_j})} {\rm{d}}{S_{a \to i}}{\rm{d}}{{\bf{x}}_{\backslash i}}\\ &= \int {\mathcal N\left( {{y_a};{h_{ai}}{x_i} + {S_{a \to i}},{N_0}} \right)} \left( {p\left( {{S_{a \to i}}|{{\bf{x}}_{\backslash i}}} \right)\prod\limits_{j \ne i}^N {{p_{j \to a}}} ({x_j}){\rm{d}}{{\bf{x}}_{\backslash i}}} \right){\rm{d}}{S_{a \to i}} \end{aligned} $$ 在此处，认为$x_k$的PDF为$p_{k\to a}(x_k)=\mu_{k\rightarrow a}^{t}(x_{k})$，其并不一定是高斯变量，但其存在均值及有限方差，分别为${{{\hat x}_{k \to a}}}=\mathbb{E}\left(x_k\right)$和${{{\hat v}_{k \to a}}}=Var(x_k)$.这两个统计量会在下一节进行推导，此处仅认为其存在。

在大系统（$M,N\to \infty, M/N=const.$）条件下，大数定律成立，${S_{a \to i}}$被近似为高斯变量。在给定的条件$x_k$下，其均值和方差分别为 $$ Z_{a \to i}^t = \sum\limits_{k \ne i}^N {{h_{ak}}{{\hat x}_{k \to a}^t}} $$ $$ V_{a \to i}^t = \sum\limits_{k \ne i}^N {|{h_{ak}}{|^2}{{\hat v}_{k \to a}^t}} $$ 实际上此变量可以视为对$y_a$在${\bf x}_{\setminus i}$下的估计。继续对消息进行变换： $$ \begin{aligned} \mu_{a\rightarrow i}^{t}& \overset{a.s.}{=}\int {\mathcal N}\left(y_{a};h_{ai}x_{i}+S_{a\rightarrow i},N_{0}\right)\mathcal{N}\left(S_{a\rightarrow i};Z_{a\rightarrow i}^{t},V_{a\rightarrow i}^{t}\right)\mathrm{d}S_{a\rightarrow i} \\ &=\int {\mathcal N}\left(S_{a\rightarrow i};y_{a}-h_{ai}x_{i},N_{0}\right)\mathcal{N}\left(S_{a\rightarrow i};Z_{a\rightarrow i}^{t},V_{a\rightarrow i}^{t}\right)\mathrm{d}S_{a\rightarrow i} \\ &\propto {\mathcal N}\left(0;y_{a}-h_{ai}x_{i}-Z_{a\rightarrow i}^{t},N_{0}+V_{a\rightarrow i}^{t}\right) \\ &\propto {\mathcal N}\Bigg(x_{i};\frac{y_{a}-Z_{a\rightarrow i}^{t}}{h_{ai}},\frac{N_{0}+V_{a\rightarrow i}^{t}}{\left|h_{ai}\right|^{2}}\Bigg) \end{aligned} $$

注意到此时消息变成了高斯的，且计算时也需要传入消息的均值与方差。高斯消息仅存在两个充分统计量，会让参数传递变得方便。在此，定义此条消息的均值和方差为

$$ {{\hat x}_{a \to i}^t} = \frac{{{y_a} - Z_{a \to i}^t}}{{{h_{ai}}}} $$ $$ {{\hat v}_{a \to i}^t} = \frac{{{N_0} + V_{a \to i}^t}}{{{{\left| {{h_{ai}}} \right|}^2}}} $$

正向消息

由SPA，我们可以得到

$$ \mu _{i \to a}^{t + 1}({x_i}) \propto p({x_i})\prod\limits_{b=1,b \ne a}^M {\mu _{b \to i}^t} ({x_i}) $$ 注意到，这条消息由于$p(x_i)$的存在，并不具备高斯特性，但其中的一部分可以进行高斯合并： $$ \begin{aligned} \prod\limits_{b=1,b \ne a}^M {\mu _{b \to i}^t} ({x_i}) &= \prod\limits_{b=1,b \ne a}^M {{\mathcal N}\left( {{x_i};{{\hat x}_{b \to i}^t},{{\hat v}_{b \to i}^t}} \right)} \\ &\propto {\mathcal N}\left( {{x_i};{{\hat r}_{i \to a}^t},{{\hat \Sigma }_{i \to a}^t}} \right) \end{aligned} $$ 其中

$$ \begin{aligned} {{\hat r}_{i \to a}^t} &\overset{def}{=} {{\hat \Sigma }_{i \to a}^t}\sum\limits_{b=1,b \ne a}^M {\frac{{{{\hat x}_{b \to i}^t}}}{{{{\hat v}_{b \to i}^t}}}} \\ &= {{\hat \Sigma }_{i \to a}^t}{\sum\limits_{b=1,b \ne a}^M {\frac{{{y_b} - Z_{b \to i}^t}}{{{h_{b \to i}}}}\left( {\frac{{{N_0} + V_{b \to i}^t}}{{{{\left| {{h_{bi}}} \right|}^2}}}} \right)} ^{ - 1}}\\ &= {{\hat \Sigma }_{i \to a}^t}\sum\limits_{b=1,b \ne a}^M {\frac{{h_{b \to i}^*\left( {{y_b} - Z_{b \to i}^t} \right)}}{{{N_0} + V_{b \to i}^t}}} \\ {{\hat \Sigma }_{i \to a}^t} &\overset{def}{=} {\left( {\sum\limits_{b=1,b \ne a}^M {\frac{1}{{{{\hat v}_{b \to i}^t}}}} } \right)^{ - 1}}\\ &= {\left( {\sum\limits_{b=1,b \ne a}^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)^{ - 1}} \end{aligned} $$

这一系列高斯消息的乘积可以视为从$\bf y_{\setminus a}$来的消息形成的对$x_i$的估计。但这个估计并不全面，因为其并未包含非高斯的先验信息$p(x_i)$的约束，而一般而言，$x_i$的先验分布可能相当复杂，可能无法通过计算得到严格的闭式PDF。

但是从反向消息的推导可知，此处并不需要$\mu _{i \to a}^{t + 1}({x_i})$确切的分布，仅仅需要其均值及方差。因此，计算以下分布： $$ \mu_{i\to a}^{t+1}(x_i)\propto p(x_i)\mathcal{N}(x_i;r_{i\to a}^{t},\Sigma_{i\to a}^{t}) $$ 的均值及方差为： $$ \begin{aligned} {{\hat x}_{i \to a}^{t+1}} &= \mathbb E\left( {{x_i}} \right)\\ &= \int {{x_i}\frac{1}{Z}p({x_i}){\mathcal N}\left( {{x_i};{{\hat r}_{i \to a}^t},{{\hat \Sigma }_{i \to a}^t}} \right)} {\rm{d}}{x_i}\\ &\overset{def}{=}F(x_i;{{\hat r}_{i \to a}},{{\hat \Sigma }_{i \to a}^t})\\ {{\hat v}_{i \to a}^{t+1}} &= Var({x_i})\\ &= \int {{{\left( {{x_i} - {{\hat x}_{i \to a}^t}} \right)}^2}\frac{1}{Z}p({x_i}){\mathcal N}\left( {{x_i};{{\hat r}_{i \to a}^t},{{\hat \Sigma }_{i \to a}^t}} \right)} {\rm{d}}{x_i}\\ &\overset{def}{=}G(x_i;{{\hat r}_{i \to a}^t},{{\hat \Sigma }_{i \to a}^t})\\ \end{aligned} $$ 其中$Z \overset{def}{=} \int {p({x_i}){\mathcal N}\left( {{x_i};{{\hat r}_{i \to a}^t},{{\hat \Sigma }_{i \to a}^t}} \right)} {\rm{d}}{x_i}$为归一化参数. 当$p(x_i)$为确定分布时，这两个积分可以直接计算或近似，其复杂度为$\mathcal O(1)$.

至此，正向消息和反向消息均推导完毕。到这里，实际上是对LBP进行了近似，减少了传递的参数量，将消息传递变成了统计量传递

进一步的简化

上述正向消息和反向消息的计算均涉及到${\mathcal O}(N)$（或${\mathcal O}(M)$,两者同等级，以下统一为${\mathcal O}(N)$）复杂度的计算过程，同时，在系统中，每次迭代存在$MN$条正向和反向消息，故实际上以上算法的复杂度约为${\mathcal O}(N^3)$.考虑到大系统下三次复杂度依然难以接受，AMP对上述两类消息进行了进一步的简化。

具体的，定义以下六个与边无关的统计量： $$ \begin{aligned} Z_a^t &= \sum\limits_{i = 1}^N {{h_{ai}}} \hat x_{i \to a}^t\\ V_a^t &= \sum\limits_{i = 1} {|{h_{ai}}{|^2}\hat v_{i \to a}^t} \\ \hat \Sigma _i^t &= {\left( {\sum\limits_{a = 1}^M {\frac{{|{h_{ai}}{|^2}}}{{N_0 + V_{a\to i}^t}}} } \right)^{ - 1}}\\ \hat r_i^t &= \Sigma _i^t\sum\limits_{a = 1}^M {\frac{{h_{ai}^*({y_a} - Z_{a\to i}^t)}}{{N_0 + V_{a \to i}^t}}} \\ {{\hat x}_i^{t+1}} &= \int {{x_i}\frac{1}{Z}p({x_i}){\mathcal{N}}\left( {{x_i};{{\hat r}_i^t},{{\hat \Sigma }_i^t}} \right)} {\rm{d}}{x_i}\\ {{\hat v}_i^{t+1}} &= \int {{{\left( {{x_i} - {{\hat x}_i}} \right)}^2}\frac{1}{Z}p({x_i}){\mathcal{N}}\left( {{x_i};{{\hat r}_i^t},{{\hat \Sigma }_i^t}} \right)} {\rm{d}}{x_i} \end{aligned} $$

而下面的操作，则是使用之前推导的正向消息与反向消息来确定以上六个变量之间的关系。换句话说，需要将之前的正向和反向消息与这六个变量之间建立联系，并试图建立此六个变量之间的迭代算法。

我们约定，$|h_{ij}|$的数量级为${\mathcal O}(\frac{1}{\sqrt{N}})$，因此$|h_{ij}|^2$的数量级为${\mathcal O}(\frac{1}{{N}})$；同时约定$x_j$的数量级为${\mathcal O}(1)$，因此其估计量--${{\hat x}_i}$和${{\hat v}_i}$数量级同样为${\mathcal O}(1)$。在以上约定下，$y_{i}$的数量级同样的，也是${\mathcal O}(1)$，$Z_a,V_a$也同样应为${\mathcal O}(1)$.因此，我们认为在在大系统极限下，单独存在的${\mathcal O}(\frac{1}{\sqrt{N}})$数量级的变量以及$N$-求和的${\mathcal O}(\frac{1}{N})$数量级的变量（求和后数量级为${\mathcal O}(\frac{1}{\sqrt{N}})$）可作为无穷小量而被忽略。

同时我们认为$\mathbb E(x)=F(x;r,\Sigma)$和$Var(x)=G(x;r,\Sigma)$ 是关于两个变量Lipschitz连续的。

观察以上变量，可以发现，其本质上存在相互依赖。具体的，变量依赖为$\Sigma_i,r_i\to \hat v_i,\hat x_i \to V_a,Z_a\to \Sigma_i,r_i\to \cdots$，其中$\to$代表后面的变量依赖于前面的变量。因此，首先对$r_i^t$和$\Sigma _i^t$进行近似： $$ \begin{aligned} \hat \Sigma _i^t - {{\hat \Sigma }_{i \to a}^t} &= {\left( {\sum\limits_b^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)^{ - 1}} - {\left( {\sum\limits_{b \ne a}^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)^{ - 1}}\\ &= - \frac{{\frac{{{{\left| {{h_{ai}}} \right|}^2}}}{{{N_0} + V_{a \to i}^t}}}}{{\left( {\sum\limits_b^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)\left( {\sum\limits_{b \ne a}^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)}}\\ &= {\mathcal O}\left( {\frac{1}{N}} \right)\\ \hat r_i^t - {{\hat r}_{i \to a}^t} &= {{\hat \Sigma }_i}\sum\limits_b^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b \to i}^t} \right)}}{{{N_0} + V_{b \to i}^t}}} - {{\hat \Sigma }_{i \to a}}\sum\limits_{b \ne a}^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b \to i}^t} \right)}}{{{N_0} + V_{b \to i}^t}}} \\ &= {{\hat \Sigma }_i}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}} + {\mathcal O}\left( {\frac{1}{N}} \right)*\sum\limits_{b\neq a}^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b \to i}^t} \right)}}{{{N_0} + V_{b \to i}^t}}} \\ &= {{\hat \Sigma }_i}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}} + {\mathcal O}\left( {\frac{1}{N}} \right) \end{aligned} $$ 即，我们得到 $$ \begin{aligned} \hat \Sigma _i^t &\approx {{\hat \Sigma }_{i \to a}}\\ \hat r_i^t &\approx {{\hat r}_{i \to a}} +{{\hat \Sigma }_i}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}} \end{aligned} $$ 接下来，我们对$\hat x_{i \to a}^{t+1}$和$\hat v_{i \to a}^{t+1}$分别在${{\hat x}_i^{t+1}}$和${{\hat v}_i^{t+1}}$处进行一阶泰勒展开。由于Lipschitz连续性，函数几乎处处存在一阶导数且导数有界。因此可以得到 $$ \begin{aligned} \hat x_{i \to a}^{t + 1} - \hat x_i^{t + 1} &= -\left( {\hat r_i^t - \hat r_{i \to a}^t} \right)\frac{{\partial F\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}} - \left( {\hat \Sigma _i^t - \hat \Sigma _{i \to a}^t} \right)\frac{{\partial F\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial \Sigma }}\\ &= -\left( {\hat r_i^t - \hat r_{i \to a}^t} \right)\frac{{\partial F\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}} + {\mathcal O}\left( {\frac{1}{N}} \right)\\ \hat v_{i \to a}^{t + 1} - \hat v_i^{t + 1} &= -\left( {\hat r_i^t - \hat r_{i \to a}^t} \right)\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}} - \left( {\hat \Sigma _i^t - \hat \Sigma _{i \to a}^t} \right)\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial \Sigma }}\\ &= -\left( {\hat r_i^t - \hat r_{i \to a}^t} \right)\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}} + {\mathcal O}\left( {\frac{1}{N}} \right) \end{aligned} $$ 并且对于$F(x;r,\Sigma)=\mathbb E(x)=\int {{x}\frac{1}{Z}p({x}){\mathcal N}\left( {{x};{{r}},{\Sigma}} \right)} {\rm{d}}{x}$而言，存在$\frac{{\partial F\left( {x;r,\Sigma } \right)}}{{\partial r}} = \frac{{G\left( {x;r,\Sigma } \right)}}{\Sigma } = \frac{{Var(x)}}{\Sigma }$，故有 $$ \begin{aligned} \hat v_{i \to a}^{t + 1} &\approx \hat v_i^{t + 1} - {{\hat \Sigma }_i}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}}\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}}\\ \hat x_{i \to a}^{t + 1} &\approx \hat x_i^{t + 1} - \frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}}\hat v_i^{t + 1} \end{aligned} $$ 接着，将上面二式代入$Z_a^t$和$V_a^t$得到 $$ \begin{aligned} V_a^t &= \sum\limits_{i = 1}^N {|{h_{ai}}{|^2}\hat v_{i \to a}^t} \\ &= \sum\limits_{i = 1}^N {\left( {|{h_{ai}}{|^2}\hat v_i^t - |{h_{ai}}{|^2}{{\hat \Sigma }_i}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}}\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}}} \right)} \\ &= \sum\limits_{i = 1}^N {\left( {|{h_{ai}}{|^2}\hat v_i^t - |{h_{ai}}{|^2}{{\left( {\sum\limits_b^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)}^{ - 1}}\frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}}\frac{{\partial G\left( {{x_i};{{\hat r}_i},{{\hat \Sigma }_i}} \right)}}{{\partial r}}} \right)} \\ &= \sum\limits_{i = 1}^N {|{h_{ai}}{|^2}\hat v_i^t} + {\mathcal O}\left( {\frac{1}{N}} \right)\\ Z_a^t &= \sum\limits_{i = 1}^N {{h_{ai}}} \hat x_{i \to a}^t\\ &= \sum\limits_{i = 1}^N {{h_{ai}}} \left( {\hat x_i^t - \frac{{h_{ai}^*\left( {{y_a} - Z_{a \to i}^{t - 1}} \right)}}{{{N_0} + V_{a \to i}^{t - 1}}}\hat v_i^t} \right)\\ &= \sum\limits_{i = 1}^N {\left( {{h_{ai}}\hat x_i^t - \frac{{|{h_{ai}}{|^2}\left( {{y_a} - Z_{a \to i}^{t - 1}} \right)}}{{{N_0} + V_{a \to i}^{t - 1}}}\hat v_i^t} \right)} \\ &= \sum\limits_{i = 1}^N {{h_{ai}}\hat x_i^t} - \sum\limits_{i = 1}^N {\frac{{|{h_{ai}}{|^2}\left( {{y_a} - Z_{a \to i}^{t - 1}} \right)}}{{{N_0} + V_{a \to i}^{t - 1}}}\hat v_i^t} \end{aligned} $$

同时，由于 $$ \begin{aligned} Z_a^t - Z_{a \to i}^t &= {h_{ai}}\hat x_{i \to a}^t \\ &= {h_{ai}}\hat x_i^t - \frac{{|{h_{ai}}{|^2}\left( {{y_a} - Z_{a \to i}^t} \right)}}{{{N_0} + V_{a \to i}^t}}\hat v_i^t \\ &= {h_{ai}}\hat x_i^t + {\mathcal O}\left( {\frac{1}{N}} \right)\\ V_a^t - V_{a \to i}^t &= |{h_{ai}}{|^2}\hat v_{i \to a}^t\\ &= {\mathcal O}\left( {\frac{1}{N}} \right) \end{aligned} $$ 得到 $$ \begin{aligned} Z_a^t &= \sum\limits_{i = 1}^N {{h_{ai}}\hat x_i^t} - \sum\limits_{i = 1}^N {\frac{{|{h_{ai}}{|^2}\left( {{y_a} - Z_{a \to i}^{t - 1}} \right)}}{{{N_0} + V_{a \to i}^{t - 1}}}\hat v_i^t} \\ &\approx \sum\limits_{i = 1}^N {{h_{ai}}\hat x_i^t} - \frac{{V_a^t\left( {{y_a} - Z_a^{t - 1}} \right)}}{{{N_0} + V_a^{t - 1}}} \end{aligned} $$

至此，我们得到了$Z_a^t$和$V_a^t$的一组与边无关的表达式，或者说我们得到了第一组仅用这六个量表达的变量，接下来需要做的，便是将这六个变量中的其余部分都转换出与边无关的表达。由于$\hat x_{i \to a}^{t+1}$和$\hat v_{i \to a}^{t+1}$本身便是由$r_i^t$和$\Sigma _i^t$表出，因此接下来只需要对$r_i^t$和$\Sigma _i^t$进行转换。 将$Z_a^t$和$V_a^t$代入$r_i^t$和$\Sigma _i^t$中得到 $$ \begin{aligned} \hat \Sigma _i^t &= {\left( {\sum\limits_b^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_{b \to i}^t}}} } \right)^{ - 1}}\\ &= {\left( {\frac{{\sum\limits_a^M {{{\left| {{h_{ai}}} \right|}^2} \prod \limits_{b \ne a}^M \left( {{N_0} + V_{b}^t + O\left( {\frac{1}{N}} \right)} \right)} }}{{ \prod \limits_{b = 1}^M \left( {{N_0} + V_{b}^t + O\left( {\frac{1}{N}} \right)} \right)}}} \right)^{ - 1}}\\ &= {\left( {\frac{{\sum\limits_a^M {{{\left| {{h_{ai}}} \right|}^2} \prod \limits_{b \ne a}^M \left( {{N_0} + V_{b}^t} \right) + O\left( {\frac{1}{N}} \right)} }}{{ \prod \limits_{b = 1}^M \left( {{N_0} + V_{b}^t} \right) + O\left( {\frac{1}{N}} \right)}}} \right)^{ - 1}}\\ &\approx {\left( {\frac{{\sum\limits_a^M {{{\left| {{h_{ai}}} \right|}^2} \prod \limits_{b \ne a}^M \left( {{N_0} + V_{b}^t} \right)} }}{{ \prod \limits_{b = 1}^M \left( {{N_0} + V_{b}^t} \right)}}} \right)^{ - 1}}\\ &= {\left( {\sum\limits_b^M {\frac{{{{\left| {{h_{bi}}} \right|}^2}}}{{{N_0} + V_b^t}}} } \right)^{ - 1}}\\ r_i^t &= \hat \Sigma _i^t\sum\limits_b^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b \to i}^t} \right)}}{{{N_0} + V_{b \to i}^t}}} \\ &= \hat \Sigma _i^t\sum\limits_b^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b }^t + {h_{bi}}\hat x_i^t}+ {\mathcal O}\left( {\frac{1}{{N }}} \right)\right)}}{{{N_0} + V_{b \to i}^t}}} \\ &= \hat \Sigma _i^t\sum\limits_b^M {\frac{{h_{bi}^*\left( {{y_b} - Z_{b }^t} \right) + |{h_{bi}}{|^2}\hat x_i^t}}{{{N_0} + V_{b \to i}^t}}}+{\mathcal O}\left( {\frac{1}{{N }}} \right) \\ &\approx \hat x_i^t + \hat \Sigma _i^t\sum\limits_b^M {\frac{{h_{bi}^*\left( {{y_b} - Z_b^t} \right)}}{{{N_0} + V_b^t}}} \end{aligned} $$

到此，AMP算法推导大致完成。此时，变量迭代均在六个边不变变量之中进行，将计算复杂度降低了一个维度。值得注意的是，这里的缩放假设只有在大系统下体现较为明显。

结语

AMP的主要思路是对边消息进行近似，再转换成点消息。近似和转换的过程中均使用了一些系统缩放的假设，因此最终产生了比较奇妙的结果。

本文于2023.10.2完成，水平一般，如有谬误，望指正。

参考文献:

https://arxiv.org/abs/2201.07487

https://arxiv.org/abs/1010.5141