1 前言

本次博文主要介绍了OAMP论文，同时加了一些粗浅的理解。一方面，前两部分涉及了一些AMP相关的知识以及我自己给出的解释，另一方面，博文所推公式可能与论文稍有偏差，笔者才疏学浅，又是第一次写博客，这两个部分都不敢保证能理解到位和描述清晰，难免解释可能会有所偏差，甚至有歪曲原文的不当之处，还希望各位读者能够包涵。下一篇博文可能会是对VAMP的解读，希望这可以在年内完成，之后博客可能会推出一些与消息传递算法较相关的论文介绍，以及自认为有价值的积累。

2 绪论

简短回顾一下Approximate Message Passing (AMP) 的问题模型

$$y\text{y}y=A\text{A}Ax\text{x}x+n\text{n}n\text{\hspace{1em}(1a)}$$ $$x_j\sim P_X(x),\forall x\text{\hspace{1em}(1b)}$$

其中$A\text{A}A\in {\mathbb{C}}^{M\times N}$是感知矩阵，$n\text{n}n\in {\mathbb{C}}^{M\times 1}$是均值为$0$，方差为${\sigma }^2$的高斯向量。AMP的一个重要性质就是其算法性能可以用state evolution来精确刻画，就是说给定真实的$x\text{x}x$，我们可以依据state evolution的结果${\tau }^t$，预测AMP在第$t$次迭代过程中估计得到的${\widehat{x\text{x}x}}^t$与真实$x\text{x}x$的均方差（MSE）$\mathbb{E}[{\Vert x\text{x}x-{\widehat{x\text{x}x}}^t\Vert }_2^2]$，表示为

$${{\tau }_t}^2\to \frac{1}{N}{\Vert x\text{x}x-{\widehat{x\text{x}x}}^t\Vert }_2^2,(N\to \infty )\text{\hspace{1em}(2)}$$

事实上，式(2)为趋近于而不是严格等于，因为$\frac{1}{N}{\Vert x\text{x}x-{\widehat{x\text{x}x}}^t\Vert }_2^2$是关于${\widehat{x\text{x}x}}^t$的二阶Lipschitz函数，满足如下收敛关系

$$\frac{1}{N}{\Vert x\text{x}x-{\widehat{x\text{x}x}}^t\Vert }_2^2\to \mathbb{E}[{\Vert x\text{x}x-{\widehat{x\text{x}x}}^t\Vert }_2^2],(N\to \infty )\text{\hspace{1em}(3)}$$

但遗憾的是，大部分情况下，只有当$A\text{A}A$为高斯矩阵或者次高斯矩阵时，state evolution才能与AMP估计的结果统一，如果感知矩阵的特征值分布与高斯矩阵的特征值分布相差较远，AMP的性能就不能保证，甚至可能会出现不收敛的情况。为了解决该问题，Junjie Ma和Li Ping提出了OAMP^[1]。

AMP还有一个重要的点是其线性迭代过程中含有"onsager"这一项，它的作用是为了消除迭代过程中感知矩阵$A\text{A}A$与估计结果${\widehat{x\text{x}x}}^t$之间的相关性。虽然OAMP把AMP中的“onsager”这一项给去掉了，但是为了补偿"onsager"原来的作用，OAMP在非线性估计中加入了divergence-free的约束（可能divergence-free这个概念有点抽象，简单理解为导数为0就行）。

备注：其实OAMP并没有严格意义的数学推导，作者先是给了两个独立性的假设（假设1和假设2），而OAMP-state evolution就是由该假设条件推出来的。让OAMP迭代开始($t=0$时刻)先保证独立性，满足两个假设条件之一，如果之后的每一次迭代假设1和假设2都能互相推出对方，那么我们可以认为每一次迭代的程始终可以保证独立条件成立，也就保证了state evolution。但略有遗憾，假设1和假设2只能“部分”地互相推出对方，可以保证不相关（由正交推出），但是不能保证独立。幸运的是，仿真结果表明，虽然迭代过程中的独立条件不能始终保持，但是state evolution还是能够和OAMP估计结果统一，论文作者将此描述为：假设1和假设2是只是state evolution的充分条件。

3 AMP

在开始OAMP之前，先回顾一下AMP。

3.1 AMP算法

假设矩阵$A\text{A}A=[{a\text{a}a}_1,{a\text{a}a}_2,\text{…},{a\text{a}a}_N]$是列归一化的，即，$\forall i\in \{1,\text{…},N\},{a\text{a}a}_i\in {\mathbb{C}}^{M\times 1}$，满足$\mathbb{E}[{\Vert {a\text{a}a}_i\Vert }_2]=1$。AMP的迭代过程如下

$$\begin{gathered} {r\text{r}r}^t={s\text{s}s}^t+{A\text{A}A}^T(y\text{y}y-A\text{A}A{s\text{s}s}^t)+ \\ \underset{onsagerterm}{\frac{N}{M}<{{\eta }_{t-1}}^{{}^{\prime }}({r\text{r}r}^{t-1})>({r\text{r}r}^{t-1}-{s\text{s}s}^{t-1})}\text{\hspace{1em}(4a)} \end{gathered}$$

$$s^{t+1}\text{st+1}{s}^{t+1}={\eta }_t({r\text{r}r}^t)\text{\hspace{1em}(4b)}$$

其中${\eta }_t$是关于${r\text{r}r}^t$的一个Lipschitz连续函数(component-wise)，${s\text{s}s}^t$是最后的估计， ${r\text{r}r}^t-{s\text{s}s}^t$其实就是一般AMP表达的“残差”(residual error)。式(4a)的最后一项就是前言所描述的"onsager"项，这一项是根据松弛信念传播算法（relaxed-Belief-Propagation, relaxed-BP）在极限条件下$M,N\to \infty$时依据大数定律、中心极限定理和消息近似补偿（为了补偿经过近似的$O(\frac{1}{\sqrt{N}})$的消息），以及泰勒展开逐步推导出来的。

"onsager"项隐含的意义："onsager"项的存在确保了AMP-state evolution的正确性，但是在推导AMP之前，relaxed-BP里边的方差项其实跟state-evolution是对应的（只是对应，并不相等），区别在于当$M,N<\infty$时，relaxed-BP的方差项（指消息传递过程中，消息分布的方差逐渐积累）一般记为${\Sigma }_m^n(t)$，这里不去管具体的$n,m$是什么含义了，$t$是指迭代到第$t$步，只是它隐式地强调了$A\text{A}A$和估计${s\text{s}s}^t$具有相关性。而$M,N\to \infty$时借助大数定理和中心极限定理进一步推导可以使得${\lim }_{M,N\to \infty }{\Sigma }_m^n(t)\to \Sigma (t)$，即去掉了相关性。

3.2 AMP-state evolution与等效信号模型

为了方便之后OAMP的讨论，下面的叙述几乎都是基于OAMP原论文的，表达式跟一般的AMP表达式有些差异，是为了类比，在后面方便证明正交性，本质上并无差异。

定义两种误差，第一种误差是非线性估计结果${s\text{s}s}^t$与真实值的差，第二种误差是线性估计结果${r\text{r}r}^t$与真实值的差，分别定义为

$${q\text{q}q}^t={s\text{s}s}^t-x\text{x}x\text{\hspace{1em}(5a)}$$

$${h\text{h}h}^t={r\text{r}r}^t-x\text{x}x\text{\hspace{1em}(5b)}$$

结合(5), (4)可以被展开为

$$\begin{gathered} {h\text{h}h}^t=(I\text{I}I-{A\text{A}A}^{T}A\text{A}A){q\text{q}q}^t+{A\text{A}A}^{T}n\text{n}n+ \\ \frac{N}{M}<{\eta }_{t-1}^{{}^{\prime }}(x\text{x}x+{h\text{h}h}^{t-1})>({h\text{h}h}^{t-1}-{q\text{q}q}^{t-1})\text{\hspace{1em}(6a)} \end{gathered}$$

$${q\text{q}q}^{t+1}={\eta }_t(x\text{x}x+{h\text{h}h}^t)-x\text{x}x\text{\hspace{1em}(6b)}$$

式(6)并不是要给迭代算法，因为真实值$x\text{x}x$作为一个已知的量参与其中。

与AMP对应的evolution由下式直接给出，这里不展开描述，因为AMP-evolution的证明过程极其复杂，但是如果只是理解，有一个简单的思路，就是如上面所述，从relaxed-BP入手，着眼于其方差演变，可以在一定程度上帮助理解。

$${\tau }_t^2=\frac{N}{M}{v}_t^2+{\sigma }^2\text{\hspace{1em}(7a)}$$

$$v_{t+1}^2=\mathbb{E}\{[{\eta }_t(X+{\tau }_{t}Z)-X{]}^2\}\text{\hspace{1em}(7b)}$$

注意式(7b)中的$X,Z$表示随机变量，并且$Z\sim \mathcal{N}(0,1)$与$X$独立。这里的理解对AMP以及AMP-state evolution是至关重要的，因为其独立性，我们可以将每次迭代估计得到的结果模型等效为

$${\hat{X}}^t=X+{\tau }_t^{2}Z,Z\sim \mathcal{N}(0,1)\text{\hspace{1em}(8)}$$

这也意味着

$${\hat{X}}^t\sim \mathcal{N}(X,{\tau }_t^2)\text{\hspace{1em}(9)}$$

${\tau }_t^2$指的是估计后的方差，结合式(7a)可以看出，方差项由高斯噪声的方差${\sigma }^2$和非线性估计结果与真实值之间的MSE构成。这反映了两点，一方面，高斯噪声与其他各个变量都保持独立，另一方面，AMP从始至终虽然都旨在接近真实值，因为${\tau }^t$一直在变小，但是依然没有克服高斯噪声。

等效模型还有一个重要的作用就是，在部分$\eta$函数的推导过程中，使用等效模型的概念可以一定程度上简化推导过程，比如推导MMSE函数，或者退化为LMMSE等。以及，${\tau }_t^2$可能作为其中的一个参数，然而实际的仿真中我们并不知道真实${\tau }_t^2$，这个时候就需要将其近似为${\hat{\tau }}_t^2$，具体表示为

$${\hat{\tau }}_t^2=\frac{1}{N}{\Vert {r\text{r}r}^t-{s\text{s}s}^t\Vert }_2^2\text{\hspace{1em}(10)}$$

4 OAMP

4.1 OAMP产生的动机

在阐述动机之前，先描述论文给出的一个定义

定义1： Divergence-free
对函数$\eta :\mathbb{R}\mapsto \mathbb{R}$，如果满足

$$\mathbb{E}[{\eta }^{{}^{\prime }}(R)]=0$$

那么就认为$\eta$是devergence-free

根据定义1，一个divergence-free的函数可以被构造成

$$\eta (r)=C\cdot (\hat{\eta }(r)-\mathbb{E}[\hat{\eta }(R)]\cdot r)\text{\hspace{1em}(11)}$$

其中$\hat{\eta }$是任意一个一阶可导的函数，C是常数。

如果把AMP迭代公式(4)中的"onsager"项给去掉，$\eta$函数按照式(11)的方式给出，其中$\hat{\eta }$是软阈值函数（压缩感知常用来恢复稀疏信号的函数），在这样的设置下，作者发现即使感知矩阵$A\text{A}A$不是高斯矩阵，而是一个离散余弦变换矩阵，state evolution的结果却意外地与去"onsager"的AMP迭代结果一致。这个发现也就引出了OAMP。

4.2 去相关的线性估计

先给出两个定义

定义2： 酉不变矩阵(Unitarily-Invariant Matrix)
如果矩阵$U\text{U}U,V\text{V}V,\Sigma \text{Σ}\Sigma$三者之间相互独立，并且$U\text{U}U,V\text{V}V$满足Haar分布(随机各向同性)是正交阵，$\Sigma \text{Σ}\Sigma$是对角阵，那么认为$A\text{A}A=U\text{U}U\Sigma \text{Σ}\Sigma V\text{V}V$是酉不变的。

定义3： 去相关矩阵
如果感知矩阵$A\text{A}A=U\text{U}U\Sigma \text{Σ}\Sigma V\text{V}V$是酉不变的，矩阵$W\text{W}W$如果满足$tr(I\text{I}I-W\text{W}WA\text{A}A)=0$，就说$W\text{W}W$是关于$A\text{A}A$的一个去相关矩阵。指定准去相关矩阵

$$\widehat{W\text{W}W}=U\text{U}UG\text{G}G{V\text{V}V}^T\text{\hspace{1em}(12)}$$

那么满足$tr(I\text{I}I-W\text{W}WA\text{A}A)$的去相关矩阵$W\text{W}W$可以被构建为

$$W\text{W}W=\frac{N}{tr(\widehat{W\text{W}W}A\text{A}A)}\widehat{W\text{W}W}\text{\hspace{1em}(13)}$$

其实定义3在论文中并没有直接给出，是我抽出来的，而且跟论文稍有出入，但是问题不大。我刚开始读到这里的去相关概念的时候非常不理解，如果矩阵A的映射是单射或者双射，可能稍微懂个大概，满射可能把$W\text{W}W$乘在右边，但是概念依然很模糊，后来请教了一下数院的学长，大概意思就说作者就是这么叫了而已。所以这里也就理解个大概吧，没有再细究。

下面给出三个常用的准去相关矩阵
（1）匹配滤波器(Matched Filter, MF)

$${\widehat{W\text{W}W}}^{MF}={A\text{A}A}^T\text{\hspace{1em}(14a)}$$

（2）伪逆(Pseudo-inverse, PINV)

$${\widehat{W\text{W}W}}^{PINV}=\{\begin{array}{l}{A\text{A}A}^T(A\text{A}A{A\text{A}A}^T{)}^{-1};M<N\\ ({A\text{A}A}^{T}A\text{A}A{)}^{-1}{A\text{A}A}^T;M>N\end{array}\text{\hspace{1em}(14b)}$$

（3）LMMSE

$${\widehat{W\text{W}W}}^{LMMSE}={A\text{A}A}^T(A\text{A}A{A\text{A}A}^T+\frac{{\sigma }^2}{v^2}I\text{I}I{)}^{-1}\text{\hspace{1em}(14c)}$$

其实式(14c)中$v^2$的含义有些微妙，将在后面合适的地方做更深的阐述。

LMMSE的简述
假设模型为$y\text{y}y=A\text{A}Ax\text{x}x+n\text{n}n$，假设随机向量$X,Y$的均值都为0（实际当中不满足的话可以先减去均值），$n\text{n}n\sim \mathcal{C}\mathcal{N}(0,{\sigma }^{2}I\text{I}I)$，那么LMMSE的估计为

$$\widehat{x\text{x}x}={\Sigma }_{xy}{\Sigma }_y^{-1}y\text{y}y$$

其中

$${\Sigma }_{xy}=\mathbb{E}[x\text{x}x{y\text{y}y}^H]=\mathbb{E}[x\text{x}x(\text{(}(A\text{A}Ax\text{x}x+n\text{n}n{)}^H]=\mathbb{E}[x\text{x}x{x\text{x}x}^{H}A\text{A}A+x\text{x}x{n\text{n}n}^H]={\Sigma }_{x}A\text{A}A$$

$$\begin{array}{rl}{\Sigma }_y& =\mathbb{E}[y\text{y}y{y\text{y}y}^H]\\ & =\mathbb{E}[(A\text{A}Ax\text{x}x+n\text{n}n)(\text{(}(A\text{A}Ax\text{x}x+n\text{n}n{)}^H]\\ & =A\text{A}A{\Sigma }_x{A\text{A}A}^H+{\sigma }^{2}I\text{I}I\end{array}$$

那么LMMSE的估计可以转化为

$$\widehat{x\text{x}x}={\Sigma }_{x}A\text{A}A(A\text{A}A{\Sigma }_x{A\text{A}A}^H+{\sigma }^{2}I\text{I}I{)}^{-1}y$$

该结果还可以继续延申，根据

$$(E\text{E}E+B\text{B}BC\text{C}CD\text{D}D{)}^{-1}={E\text{E}E}^{-1}-{E\text{E}E}^{-1}B\text{B}B({C\text{C}C}^{-1}+D{E\text{E}E}^{-1}B\text{B}B{)}^{-1}D\text{D}D{E\text{E}E}^{-1}$$

将上述公式代入${\Sigma }_y$项即可。

4.3 OAMP算法

OAMP的迭代公式

$${r\text{r}r}^t={s\text{s}s}^t+{W\text{W}W}_t(y\text{y}y-A\text{A}A{s\text{s}s}^t)\text{\hspace{1em}(15a)}$$

$${s\text{s}s}^{t+1}={\eta }_t({r\text{r}r}^t)\text{\hspace{1em}(15b)}$$

其中${W\text{W}W}_t$是去相关矩阵，${\eta }_t$是满足divergence-free的约束，即式(11)。将该式与AMP迭代式(4)做比较，可以发现线性估计中的矩阵${A\text{A}A}^T$变得更一般化，不再局限于匹配滤波，而且末尾缺少了"onsager"项，把“onsager”的作用加在了divergence-free约束里，这也跟OAMP动机部分所阐述的内容一致。

4.4 估计误差迭代与OAMP-state evolution

依然保持式(5a, 5b)所述的误差符号${h\text{h}h}^t,{q\text{q}q}^t$，可以类比AMP中的式(6)写出OAMP的误差迭代，如下

$${h\text{h}h}^t={B\text{B}B}_t{q\text{q}q}^t+{W\text{W}W}_{t}n\text{n}n\text{\hspace{1em}(16a)}$$

$${q\text{q}q}^{t+1}={\eta }_t(x\text{x}x+{h\text{h}h}^t)-x\text{x}x\text{\hspace{1em}(16b)}$$

其中${B\text{B}B}_t=I\text{I}I-{W\text{W}W}_{t}A\text{A}A$，然后如AMP一样，指定

$${\tau }_t^2=\frac{1}{N}\mathbb{E}[{\Vert {h\text{h}h}^t\Vert }_2^2]\text{\hspace{1em}(17a)}$$

$$v_{t+1}^2=\frac{1}{N}\mathbb{E}[{\Vert {q\text{q}q}^{t+1}\Vert }_2^2]\text{\hspace{1em}(17b)}$$

式(17)就是所谓的state evolution，可以对式(17a)做进一步推导
$$\begin{array}{rl}{\tau }_t^2& =\frac{1}{N}\mathbb{E}[{\Vert {h\text{h}h}^t\Vert }_2^2]\\ & =\frac{1}{N}\mathbb{E}[{\Vert {B\text{B}B}_t{q\text{q}q}^t+{W\text{W}W}_{t}n\text{n}n\Vert }_2^2]\\ & =\frac{1}{N}\{\mathbb{E}[{\Vert {B\text{B}B}_t{q\text{q}q}^t\Vert }_2^2]+\mathbb{E}[{\Vert {W\text{W}W}_{t}n\text{n}n\Vert }_2^2]\}\\ & =\frac{1}{N}\{\mathbb{E}[tr(({q\text{q}q}^t{)}^T{B\text{B}B}_t^T{B\text{B}B}_t{q\text{q}q}^t))]+\mathbb{E}[tr({n\text{n}n}^T{W\text{W}W}_t^T{W\text{W}W}_{t}n\text{n}n)]\}\\ & =\frac{1}{N}\{\mathbb{E}[tr({B\text{B}B}_t^T{B\text{B}B}_t)]\cdot E[{\Vert {q\text{q}q}^t\Vert }_2^2]+\mathbb{E}[tr({W\text{W}W}_t^T{W\text{W}W}_t)]\cdot E[{\Vert n\text{n}n\Vert }_2^2]\}\\ & =\frac{1}{N}\{\mathbb{E}[tr({B\text{B}B}_t^T{B\text{B}B}_t)]\cdot N{v}_t^2+\mathbb{E}[tr({W\text{W}W}_t^T{W\text{W}W}_t)]\cdot M{\sigma }^2\}\\ & =\mathbb{E}[tr({B\text{B}B}_t^T{B\text{B}B}_t)]\cdot v_t^2+\frac{M}{N}\mathbb{E}[tr({W\text{W}W}_t^T{W\text{W}W}_t)]\cdot {\sigma }^2\end{array}$$

注意：上面推导出来的结果与OAMP论文式(23)给出的在系数上有差异，感觉应该上面是正确的，不管如何，思路应该没什么问题。那么，据此，就可以轻易地写出OAMP-state evolution

$${\tau }_t^2=\mathbb{E}[tr({B\text{B}B}_t^T{B\text{B}B}_t)]\cdot v_t^2+\frac{M}{N}\mathbb{E}[tr({W\text{W}W}_t^T{W\text{W}W}_t)]\cdot {\sigma }^2\text{\hspace{1em}(18a)}$$

$$v_{t+1}^2=\mathbb{E}[{|{\eta }_t(X+{\tau }_{t}Z)-X|}^2]\text{\hspace{1em}(18b)}$$

其中$X\sim P_X(x)$，与$Z\sim \mathcal{N}(0,1)$独立。

4.5 关于OAMP的合理性以及两个重要假设

关于OAMP的合理性，前言部分已经做了简短的铺垫，这里再详细展开。论文作者提出了两个假设，虽然OAMP的证明并不严格，但是基于两个假设展开的讨论还是比较合理的。

假设1：式(16a)中的${h\text{h}h}^t\sim \mathcal{N}(0,{\tau }_t^2)$，并且独立于真实值$x\text{x}x$。
假设2：式(16b)中的${q\text{q}q}^{t+1}$里的元素是独立同分布的(i.i.d)，并且独立于$A\text{A}A,n\text{n}n$。

一般的条件会有$x\text{x}x$是i.i.d.的，独立于$A\text{A}A,n\text{n}n$，在OAMP中，当迭代次数$t=-1$时，${q\text{q}q}^0=-x\text{x}x$，因此假设2在$t=-1$时是成立的。虽然OAMP的线性迭代式(15a)比AMP的线性迭代式(4a)少了"onsager"这一项，但是只有我们能证明假设2在迭代过程中一直成立，那么式(15a)便是合理的，因为"onsager"的作用就是去除迭代估计结果与$A\text{A}A$的相关性。接下来会提出两个推论来更直观地理解OAMP。

4.5.1 从假设2看假设1

推论1：如果假设2是成立的，矩阵$A\text{A}A$是酉不变的，${W\text{W}W}_t$是去相关矩阵，那么就有${h\text{h}h}^t$的元素与$x\text{x}x$的元素不相关，以及，${h\text{h}h}^t$的元素彼此之间不相关，而且它们拥有共同的方差，均值为0。

证明：从式(16b)${q\text{q}q}^{t+1}={\eta }_t(x\text{x}x+{h\text{h}h}^t)-x\text{x}x$可以看出，${q\text{q}q}^t$与$x\text{x}x$具有相关性，这可能会进一步导致${h\text{h}h}^t$与$x\text{x}x$的相关，因为式(16a)中${h\text{h}h}^t$由${q\text{q}q}^t$生成。但去相关矩阵${W\text{W}W}_t$的引入可以抑制此相关性，具体描述如下。
因为$A\text{A}A=V\text{V}V\Sigma {U\text{U}U}^T$，${W\text{W}W}_t=U\text{U}U{G\text{G}G}_t{V\text{V}V}^T$，$B\text{B}B=I\text{I}I-{W\text{W}W}_{t}A\text{A}A=U\text{U}U(I\text{I}I-{G\text{G}G}_t\Sigma ){U\text{U}U}^T$，那么

$${\mathbb{E}}_U[({B\text{B}B}_t{)}_{i,j}]=\sum _{m=1}^N\mathbb{E}[U_{i,m}{U}_{j,m}]\cdot (1-g_m{\lambda }_m)$$

其中${\lambda }_m,g_m$分别是矩阵$A\text{A}A,{W\text{W}W}_t$的奇异值，并且当$m>M$时，${\lambda }_m=g_m=0$。
对于一个Haar分布的矩阵$U\text{U}U$，有

$$\mathbb{E}[U_{i,m}{U}_{j,m}]=\{\begin{array}{l}0;i\ne j\\ N^{-1};i=j\end{array}$$

那么就有

$${\mathbb{E}}_U[({B\text{B}B}_t{)}_{i,j}]=\{\begin{array}{l}0;i\ne j\\ \frac{1}{N}tr({B\text{B}B}_t);i=j\end{array}$$

因为${W\text{W}W}_t$是去相关矩阵，根据定义3，有$tr({B\text{B}B}_t)=tr(I\text{I}I-{W\text{W}W}_{t}A\text{A}A)=0$，所以

$$\mathbb{E}[{B\text{B}B}_t]=0$$

假设2给出了条件，${q\text{q}q}^t$独立于$A\text{A}A$，显然也独立于${B\text{B}B}_t$，那么

$$\begin{array}{rl}\mathbb{E}[{h\text{h}h}^t]& =\mathbb{E}[{B\text{B}B}_t{q\text{q}q}^t]+\mathbb{E}[{W\text{W}W}_{t}n\text{n}n]\\ & =\mathbb{E}[{B\text{B}B}_t]\mathbb{E}[{q\text{q}q}^t]+\mathbb{E}[{W\text{W}W}_t]\mathbb{E}[n\text{n}n]\\ & ={0\text{0}0}_N\end{array}\text{\hspace{1em}(19)}$$

又${h\text{h}h}^t={B\text{B}B}_t{q\text{q}q}^t+{W\text{W}W}_{t}n\text{n}n$，要证$x\text{x}x$与${h\text{h}h}^t$不相关，只需要证$x\text{x}x$与${B\text{B}B}_t{q\text{q}q}^t$不相关（已经有$\mathbb{E}[{B\text{B}B}_t{q\text{q}q}^t]={0\text{0}0}_N$，所以满足正交性即可）

$$\mathbb{E}[{h\text{h}h}^t{x\text{x}x}^T]=\mathbb{E}[{B\text{B}B}_t{q\text{q}q}^t{x\text{x}x}^T]=\mathbb{E}[{B\text{B}B}_t]\mathbb{E}[{q\text{q}q}^t{x\text{x}x}^T]={0\text{0}0}_{N\times N}\text{\hspace{1em}(20)}$$

所以，根据$\mathbb{E}[{h\text{h}h}^t]={0\text{0}0}_N$和$\mathbb{E}[{h\text{h}h}^t{x\text{x}x}^T]={0\text{0}0}_{N\times N}$（正交性），必然有$x\text{x}x$与${h\text{h}h}^t$不相关。要证${h\text{h}h}^t$的元素彼此之间不相关，而且它们拥有共同的方差，均值为0，只需证明${h\text{h}h}^t$为对角阵的系数，这里省略。

事实上，因为$\mathbb{E}[{B\text{B}B}_t]=\mathbb{E}[n\text{n}n]$都为0，式(19)隐含了${h\text{h}h}^t,{q\text{q}q}^t$的正交性

$$\mathbb{E}[{h\text{h}h}^t({q\text{q}q}^t{)}^T]={0\text{0}0}_{N\times N}\text{\hspace{1em}(21)}$$

从推论1的证明过程中可以看出，去相关矩阵${W\text{W}W}_t$在里边起到了重要的去相关作用(间接地借助了$B\text{B}B=I\text{I}I-{W\text{W}W}_{t}A\text{A}A$)。除此之外，还可以看出OAMP对矩阵$A\text{A}A$的特征值没有任何束缚，所以潜在的应用范围会更广一些相对于AMP。

4.5.2 从假设1看假设2

在这一部分，我们尝试基于假设1，来推出假设2，从式(16)可以看出，如果${q\text{q}q}^{t+1}$与${h\text{h}h}^t$独立，那么${q\text{q}q}^{t+1}$与$A\text{A}A,n\text{n}n$也独立，因为(16b)中${q\text{q}q}^{t+1}$只跟${h\text{h}h}^t$和$x\text{x}x$有关系，那么就存在这样一条马尔可夫链(注意上标$t$)

$$A\text{A}A,n\text{n}n\to {h\text{h}h}^t\to {q\text{q}q}^{t+1}$$

也就是说，如果我们能够证明${q\text{q}q}^{t+1}$与${h\text{h}h}^t$独立，那么假设2就自然而然成立。但遗憾的是我们并不能证明独立性，只能证明正交性，再推广到不相关（推论2将阐述）。

回到定义1里边所阐述的divergence-free函数，利用Lipchitz函数期望的收敛性，我们可以构建一个近似divergence-free函数，如下

$${\eta }_t({r\text{r}r}^t)=C\cdot \{{\hat{\eta }}_t({r\text{r}r}^t)-(\frac{1}{N}\sum _{j=1}^N{\hat{\eta }}_t^{{}^{\prime }}(r_j^t))\cdot {r\text{r}r}^t\}\text{\hspace{1em}(22)}$$

备注：式(22)的近似divergence-free函数与OAMP的迭代公式(15)结合，便是真正的实际所采用的OAMP算法。

推论2：如果$\eta$是divergence-free函数，那么

$$\mathbb{E}[{\tau }_{t}Z\cdot \eta (X+{\tau }_{t}Z)]=0\text{\hspace{1em}(23)}$$

在证明上式之前，先引入一个重要引理
Stein引理：对$\forall \psi :\mathbb{R}\mapsto \mathbb{R}$，使得下式中的期望存在，有

$$\mathbb{E}[Z\cdot \psi (Z)]=\mathbb{E}[{\psi }^{{}^{\prime }}(Z)]\text{\hspace{1em}(24)}$$

让$\varphi (Z)={\eta }_t(X+{\tau }_{t}Z)$，根据Stein引理，

$$\begin{array}{rl}\mathbb{E}[{\tau }_{t}Z\cdot {\eta }_t(X+{\tau }_{t}Z)]& ={\tau }_t\cdot {\mathbb{E}}_X\{{\mathbb{E}}_{Z|X}[Z\cdot {\eta }_t(X+{\tau }_{t}Z)]\}\\ & ={\tau }_t^2\cdot {\mathbb{E}}_X\{{\mathbb{E}}_{Z|X}[{\eta }_t^{{}^{\prime }}(X+{\tau }_{t}Z)]\}\\ & ={\tau }_t^2\cdot \mathbb{E}[{\eta }_t^{{}^{\prime }}(X+{\tau }_{t}Z)]\end{array}$$

因为${\eta }_t$是divergence-free函数，所以$\mathbb{E}[{\eta }_t^{{}^{\prime }}(X+{\tau }_{t}Z)]=0$，也就证明了(23)。而(23)等价于

$$\mathbb{E}[(R^t-X)\cdot ({\eta }_t(R^t)-X)]=0\text{\hspace{1em}(25)}$$

其中$R^t=X+{\tau }_{t}Z$。

式(25)直接推广可以得到

$$\mathbb{E}[{h\text{h}h}^t({q\text{q}q}^{t+1}{)}^T]={0\text{0}0}_{N\times N}\text{\hspace{1em}(26)}$$

强调为什么叫OAMP：式(21)说明了线性估计(16a)中，“input-error”${q\text{q}q}^t$和"output-error"${h\text{h}h}^t$是正交的（由推论1得出）；式(26)说明了非线性估计(16b)中，"before-error"${h\text{h}h}^t$和"after-error"${q\text{q}q}^{t+1}$是正交的（由推论2得出）。这也就是OAMP名字里正交的由来。

4.6 MSE估计和state evolution仿真

在开始这部分之前，先回顾一下式(14c)LMMSE中的参数$v^2$，OAMP迭代公式${r\text{r}r}^t={s\text{s}s}^t+{W\text{W}W}_t(y\text{y}y-A\text{A}A{s\text{s}s}^t)={s\text{s}s}^t+{W\text{W}W}_t(A\text{A}A(x\text{x}x-{s\text{s}s}^t)+n\text{n}n)$，所以LMMSE中的参数$v^2$表示

$$\mathbb{E}[(x\text{x}x-{s\text{s}s}^t)(x\text{x}x-{s\text{s}s}^t{)}^T]=v^{2}I\text{I}I$$

两个MSE：$v_t^2=\frac{1}{N}\mathbb{E}[{\Vert {q\text{q}q}^t\Vert }_2^2]$，${\tau }_t^2=\frac{1}{N}\mathbb{E}[{\Vert {h\text{h}h}^t\Vert }_2^2]$，它们可以看作是去相关矩阵${W\text{W}W}_t$和divergence-free函数${\eta }_t$的两个参数（这也就是为什么${W\text{W}W}_t$有下标$t$的原因）

4.6.1 非线性均方误差的估计

非线性均方误差$v_t^2$的估计表达式

$${\hat{v}}_t^2=\frac{1}{N}$$