基于压缩感知的期望最大化贝努利非对称高斯近似信息传递算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于压缩感知的期望最大化贝努利非对称高斯近似信息传递算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：期望最大化贝努利高斯（BG）近似信息传递（EMBGAMP）算法中的BG模型因为具有对称性，在逼近实际信号先验分布时会受到限制；而期望最大化高斯混合近似信息传递（EMGMAMP）算法中的GM模型是BG模型的高阶形式，复杂度较高。为了解决以上问题，提出贝努利不对称高斯模型（BAG），进而推导得到期望最大化贝努利不对称高斯近似信息传递（EMBAGAMP）算法。该算法的主要思路是假设输入信号服从BAG模型，然后使用广义近似信息传递（GAMP）重构信号并在算法迭代中同时更新模型参数。实验证明，在处理不同图像数据时，EMBAGAMP和EMBGAMP相比，时间增加了1.2%，峰值信噪比（PSNR）值提升了0.1～0.5dB，尤其在处理纹理较少以及色差变化明显的图像时峰值信噪比（PSNR）值提升了0.4～0.5dB。EMBAGAMP是对EMBGAMP算法的扩展和延伸，更适合实际信号的处理。
关键词：压缩感知；广义近似信息传递算法；期望最大化；信号模型；贝努利不对称高斯
中图分类号： TN911.73 文献标志码：A
英文摘要
Abstract：BernoulliGaussian （BG） model in ExpectationMaximization BernoulliGaussian Approximate Message Passing （EMBGAMP） algorithm is constrained by its symmetry and restricted in the approximation of the actual signal prior distribution. GaussianMixture （GM） model in ExpectationMaximization GaussianMixture Approximate Message Passing （EMGMAMP） algorithm is a highorder model of BG model and has quite high complexity. In order to solve these problems， the BernoulliAsymmetricGaussian （BAG） model was proposed. Based on the new model， by further derivation， the ExpectationMaximization BernoulliAsymmetricGaussian Approximate Message Passing （EMBAGAMP） algorithm was obtained. The main idea of the proposed algorithm was based on the assumption that the input signal obeyed the BAG model. Then the proposed algorithm used Generalized Approximate Message Passing （GAMP） to reconstruct signal and update the model parameters in iteration. The experimental results show that， when processing different images， compared to EMBGAMP，the time and the Peak SignaltoNoise Ratio （PSNR） values of EMBAGAMP are increased respectively by 1.2% and 0.1-0.5dB， especially in processing images with simple texture and obvious color difference changing， the PSNR values are increased by 0.4-0.5dB. EMBAGAMP is the expansion and extension of EMBGAMP and can better adapt to the actual signal.So the BAG model proposed in the paper has good research prospect and can also be the groundwork for further study of Asymmetric Gaussian Mixture model.
英文关键词
Key words：
compressed sensing； generalized approximate message passing algorithm； expectation maximization； signal model； Bernoulli asymmetric Gaussian
0 引言
随着现在数据传输量的日益增大，压缩感知（Compressed Sensing，CS）[1-4]作为一种新的高效的信号采集技术受到了越来越多的关注，它能够将数据的采样和压缩过程合二为一，以较少的数据量来恢复原信号，为解决数据冗余和资源浪费的瓶颈问题开拓了一条新道路。
目前，近似信息传递算法是压缩感知信号重建算法中的一个热点，近似信息传递（Approximate Message Passing，AMP）算法[5-8]是最先由Maleki等[9]提出的一种低复杂度、高性能的迭代阈值算法，它是在大系统极限的条件下通过信息传递算法和中心极限定理的近似推导得到的[10-11]。AMP算法因为其低复杂度和高性能的特点受到广泛关注，然而这种算法在推导时并未考虑到不同的输入信号先验分布，因而算法性能受到输入信号分布的限制。为了解决这一问题，文献[12]提出了广义近似信息传递（Generalized Approximate Message Passing，GAMP）算法，它考虑到了任意的输入信号先验分布，以及输出信道模型，使得AMP理论更加系统。但是GAMP算法只是一种理论框架，它需要已知输入信号先验分布和输出信道模型，在不同的信号先验分布和输出信道模型下所推导出的具体算法也是不同的。实际上，很难知道信号和噪声的精确的分布方式，针对这一问题，文献[13]和文献[14]分别提出了期望最大化贝努利高斯近似信息传递（ExpectationMaximization BernoulliGaussian Approximate Message Passing，EMBGAMP）算法和期望最大化高斯混合近似信息传递（ExpectationMaximization GaussianMixture Approximate Message Passing，EMGMAMP）算法，这两个算法分别假设信号先验分布服从贝努利高斯（BernoulliGaussian，BG）和高斯混合（GaussianMixture，GM），噪声服从0均值的高斯分布，并通过期望最大化（ExpectationMaximization，EM）算法迭代更新模型中的参数。文献[15]在这两个算法的基础上提出了非负高斯混合（NonNegative GaussianMixture）模型来专门处理非负稀疏信号。由此可见，信号模型的假设是至关重要的，考虑到BG模型具有对称性，而日常生活中的大部分信号或是自然图像的分布方式并非完全对称的，且GM模型是BG模型的高阶形式，有较高的复杂度，且局部上依然无法摆脱对称性的约束，本文提出了一种贝努利不对称高斯（BernoulliAsymmetricGaussian，BAG）模型，BG模型的均值θ左右的概率密度函数（Probability Density Function，PDF）是对称的，而BAG模型在θ左右的概率密度函数是由参数控制的，仅当左右参数相同时，BAG模型等于BG模型，因而BAG模型是BG模型的延伸，能够用它来逼近表示的输入信号的种类得到了扩展。进而，本文基于BAG模型，在期望最大化广义近似信息传递（ExpectationMaximization Generalized Approximate Message Passing，EMGAMP）的框架下，使用贝努利不对称高斯广义近似信息传递（BernoulliAsymmetricGaussian Generalized Approximate Message Passing，BAGGAMP）推导出了EMBAGAMP算法。实验结果表明，EMBAGAMP算法以较小的时间复杂度为代价，提高了EMBGAMP算法的重构精度，并且在处理纹理较少以及色差变化明显的图像时有较大的优势。
1 EMGAMP框架
无论是EMBGAMP算法还是EMGMAMP算法，都是在EMGAMP的框架下进行具体的推导得到的。EMGAMP框架的主要思想总结如下：
步骤1 对输入信号模型以及输出信号模型的参数进行初始化。
步骤2 使用GAMP算法恢复信号直到满足GAMP算法迭代终止条件。
步骤3 判断是否满足EM迭代终止条件：若满足，算法终止，输出重构信号；若不满足，对输入信号模型以及输出信号模型的参数使用EM算法进行更新并跳转至步骤2。
由文献[12-14]可知，可以将EMGAMP框架分为两部分。第一部分是在具体的信号模型下的GAMP算法，这是每一次EM迭代过程中都要使用的算法，对于不同的信号模型，GAMP算法的具体形式不同，这主要是由GAMP算法中的四个输入输出估计函数gin（・）、g′in（・）、gout（・）和g′out（・）决定的，gin（・）和gout（・）都是通过最大后验概率准则分别对输入信号以及无噪声干扰的实际测量值的估计，g′in（・）和g′out（・）则分别是gin（・）和gout（・）的导数。第二部分是对信号模型参数的EM估计，通过迭代使得假设模型中的参数达到最优的状态。与GAMP算法相比，EMGAMP框架不需要已知输入信号先验分布以及具体的参数值，而是通过假设一个信号模型并迭代更新模型参数来逼近实际信号的先验分布的。由此可见信号模型的假设至关重要，假设的信号模型要能够尽可能地逼近生活中或自然界中的大部分信号。EMBGAMP和EMGMAMP就是分别假设信号模型为BG和GM条件下的具体算法。EMBGAMP以及EMGMAMP相对于GAMP的时间复杂度的增加主要体现在信号模型参数的更新上，BG模型每次迭代需要更新的参数有稀疏度λ，均值θ和方差φ三个，而GM模型以三阶为例需要更新的参数有稀疏度λ，均值θ1、θ2、θ3，方差φ1、φ2、φ3七个。由此可见，GM相对于BG，时间复杂度明显提升，为了在较少的参数更新下提高BG模型的普适性和算法的性能，提出了BAG模型和EMBAGAMP算法。
2 BAGGAMP
EMBAGAMP与EMBGAMP和EMGMAMP算法一样都是基于EMGAMP框架的具体算法，其算法步骤与第1章中EMGAMP算法主要思想一致。不同点在于第一步中的输入信号模型变为了具体的BAG模型，第二步使用的GAMP算法变成了具体的BAGGAMP算法，这是在BAG信号模型下的GAMP算法，是本文所提出的算法的核心。BAG模型每次迭代需要更新的参数有稀疏度λ、均值θ、左方差φl和右方差φr四个，与BG模型相比只多了一个参数，时间复杂度的增加有限，但用左右两个方差来代替BG模型中的一个方差，可以更好地逼近非对称信号。BAG模型中的参数更新公式将在下一章中给出，本章将主要给出BAG模型的具体函数和BAGGAMP的四个输入输出函数。
这里与BG模型不同的是使用πl和πr代替了π来分别表示采用信号模型左边部分和右边部分得到的信号不为零的概率；γl和γr分别表示信号不为零的条件下采用信号模型左边部分和右边部分得到的信号估计值；υl和υr分别表示与信号估计值γl和γr所对应的方差。由文献[12]可知n可以看作是信号xn的有噪情况下的近似，所以不同于BG模型，这里以n与θ的大小关系作为判决条件来决定是使用BAG模型的θ左边的参数进行估计，还是使用BAG模型的θ右边的参数进行估计。
3 BAG信号模型的EM参数估计
由第2章可知在EMGAMP框架的第二部分中需要推导的是信号模型参数的具体更新公式，这里采用的是期望最大化（EM）算法，与BG模型和GM模型中使用的参数更新算法一致，但在具体的模型下推导出的公式以及推导过程中使用的近似方法不同。由上一章可知，在BAG模型下需要更新的参数可以表示为q=[λ，θ，φl，φr，ψ]，EM算法是一种迭代法，逐步使得期望达到局部最大值。
4 数值仿真
为了测试在BAG模型下推导的EMBAGAMP算法的性能，对二维信号进行了仿真实验，这里使用了4幅典型的纹理复杂程度相差较大的图像，分别为boat、lena、cameraman和milkdrop测试图像。先对图像进行小波变换，然后重建小波系数，再通过小波反变换重建原图像，实验中使用的是4层db1小波变换，考虑到这里仿真时是将图像数据作为一列进行处理，256×256的图像作为一列处理时对内存要求较高，所以这里的测试图像的大小均为128×128，测量矩阵为随机高斯矩阵，输入信号设为无噪状态，重建性能用峰值信噪比（Peak SignaltoNoise Ratio，PSNR）来评定，对于深度为8位的灰度图像而言，其灰度级为256，处于0到255之间，此时，PSNR=10lg
（2552/MSE），其中均方误差（Mean Square Error，MSE）为MSE=x-22/N。上式中x是否应黑？数值仿真中的x应为黑斜体
实验中，EM算法的迭代次数最大值取10，GAMP算法的迭代次数最大值取4，EM迭代终止阈值τEM=10-5，GAMP迭代终止阈值τGAMP=10-5，对4幅图像分别进行了100次重构取平均值，EMBGAMP、EMBAGAMP与EMGMAMP算法的重建结果如表1～4所示。图1 和图2分别给出了boat图和camera图分别使用EMBGAMP算法和EMBAGAMP算法在0.5采样率下的重构图像。
比较表1～4中重建图像的PSNR和重建时间time可以发现对于4幅典型的纹理复杂程度相差较大的图像：在不同的采样率下，EMBAGAMP算法的重建性能都好于EMBGAMP算法，时间有1.2%左右的增加。当采样率取0.4或0.5时，对于纹理较复杂的lena图，PSNR有0.1～0.2的提升；对于纹理较复杂的boat图，PSNR有0.3～0.4的提升；对于纹理较少的cameraman和milkdrop图，PSNR有0.4～0.5的提升。这是因为lena图的灰度值变换均匀，对称性强，boat图虽然纹理复杂，但其灰度值变换不均匀，与纹理较少的cameraman和milkdrop图一样颜色主要聚集在一到两个灰度上，其不对称性相对lena图有所提升，因而BAGEMAMP算法在处理纹理较少的图像以及色差变换明显的图像时优势会更明显。分别观察图1和图2中的两幅恢复图像，可以发现图1的船尾部分和船头的桅杆等细节部分，图2的脸部、衣服边缘和支架等细节部分，EMBAGAMP的重建质量高于EMBGAMP。
比较EMBAGAMP和EMGMAMP算法时，可以发现 EMGMAMP算法的重建性能好于EMBAGAMP，而时间复杂度高于EMBAGAMP这一结果是可以预料的，因为EMGMAMP算法是在假设输入信号为高斯混合模型下推导出的，它是高斯模型的高阶形式，BAG模型只是BG模型的一阶形式的扩展；但是通过一阶下性能对比情况，以及考虑到所需估计的参数的个数，可以预想到高阶情况即混合BAG模型下推导的算法的性能较EMGMAMP算法会有所提升，并且有相当的时间复杂度。
5 结语
本文在EMGAMP的框架下针对贝努利高斯（BG）模型的对称性这一约束，提出了贝努利不对称高斯（BAG）模型，它是BG模型的一种扩展，并推导出了这一模型下的具体算法EMBAGAMP算法。实验表明，BAG模型相对于BG模型可以更好地逼近图像数据的分布函数，EMBAGAMP算法的重建精度高于EMBGAMP算法。并且根据一阶BG模型向高阶的高斯混合（GM）模型发展这一方向，本文所提出的BAG模型为进一步研究其高阶形式即不对称高斯混合模型作了铺垫，不对称高斯混合模型也是下一步的研究方向。
参考文献：
[1]CANDES E J， ROMBERG J， TAO T. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory， 2006， 52（2）： 489-509.
[2]DONOHO D L. Compressed sensing [J]. IEEE Transactions on Information Theory， 2006， 52（4）： 1289-1306.
[3]SHI G， LIU D， GAO D， et al. Advances in theory and application of compressed sensing [J]. Acta Electronica Sinica， 2009， 37（5）： 1070-1081. （石光明，刘丹华，高大化，等.压缩感知理论及其研究进展[J].电子学报，2009，37（5）：1070-1081.）
[4]LI S， WEI D. Summary of compressed sensing [J]. Acta Automatica Sinica， 2009， 35（11）： 1369-1377.（李树涛，魏丹.压缩传感综述[J].自动化学报，2009，35（11）：1369-1377.）
[5]DONOHO D L， MALEKI A， MONTANARI A. Messagepassing algorithms for compressed sensing [J]. Proceedings of the National Academy of Sciences， 2009， 106（45）： 18914-18919. [2014-12-04]. http：//www.ece.rice.edu/～mam15/pnas_full.pdf.
[6]DONOHO D L， MALEKI A， MONTANARI A. Message passing algorithms for compressed sensing： I. motivation and construction [C]// Proceedings of the 2010 IEEE Information Theory Workshop on Information Theory. Piscataway： IEEE， 2010： 1-5.
[7]DONOHO D L， MALEKI A， MONTANARI A. Message passing algorithms for compressed sensing： II. analysis and validation [C]// Proceedings of the 2010 IEEE Information Theory Workshop on Information Theory. Piscataway： IEEE， 2010： 1-5.
[8]MALEKI A， ANITORI L， YANG Z， et al. Asymptotic analysis of complex LASSO via Complex Approximate Message Passing （CAMP）[J]. IEEE Transactions on Information Theory， 2013， 59（7）： 4290-4308.
[9]MALEKI A， DONOHO D L. Optimally tuned iterative reconstruction algorithms for compressed sensing [J]. IEEE Journal of Selected Topics in Signal Processing， 2010， 4（2）： 330-341.
[10]RANGAN S. Estimation with random linear mixing， belief propagation and compressed sensing [C]// Proceedings of the 2010 44th Annual Conference on Information Sciences and Systems. Piscataway： IEEE， 2010： 1-6.
[11]BAYATI M， MONTANARI A. The dynamics of message passing on dense graphs， with applications to compressed sensing [J]. IEEE Transactions on Information Theory， 2011， 57（2）： 764-785.
[12]RANGAN S. Generalized approximate message passing for estimation with random linear mixing [C]// Proceedings of the 2011 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2011： 2168-2172.
[13]VILA J， SCHNITE P. Expectationmaximization BernoulliGaussian approximate message passing [C]// Proceedings of the 2011 Conference Record of the Forty Fifth Asilomar Conference on Signals， Systems and Computers.Piscataway： IEEE， 2011： 799-803.
[14]VILA J， SCHNITE P. Expectationmaximization Gaussianmixture approximate message passing [C]// Proceedings of the 2012 46th Annual Conference on Information Sciences and Systems. Piscataway： IEEE， 2012： 1-6.
[15]VILA J， SCHNITER P. An empiricalbayes approach to recovering linearly constrained nonnegative sparse signals [C]// Proceedings of the 2013 IEEE 5th International Workshop on Computational Advances in MultiSensor Adaptive Processing. Piscataway： IEEE， 2013： 5-8.