压缩感知问题统计建模及应用

边昂，张建州

四川大学计算机学院，成都 610065

压缩感知问题统计建模及应用

边昂，张建州

四川大学计算机学院，成都 610065

对高斯噪声下的高斯随机观测矩阵压缩感知问题建立了新的统计模型，并在该统计模型的基础上，引入相应的统计检验方法对l0范式约束下的硬阈值加权中值回归重建算法进行分析。提出了基于卡方检验的l1范式支持检测计算顺序排序方法来改进该算法的坐标下降的计算顺序；针对该算法需要通过人工设定最大迭代次数和残差能量下界来控制迭代次数的问题，提出了基于F检验的自适应停止准则，并在仿真实验中证明了改进后算法的有效性。

压缩感知；高斯噪声；l0范式最小绝对偏差；加权中值；假设检验

压缩感知[1-2]旨在通过解决非光滑优化的问题，将稀疏信号从被噪声污染的较少的观测信息中重建出来。在这个领域最大的挑战就是如何在范式约束下，对不适定方程进行求解。

目前针对高斯噪声等有界误差噪声的方法有很多，包括匹配追踪（MP）[3]，正交匹配追踪（OMP）[4]，逐步正交匹配追踪（StOMP）[5]，正则化正交匹配追踪（ROMP）[6]，子空间匹配追踪（SSMP）[7]和压缩感知匹配追踪（CoSaMP）[8]等贪心算法，以及Lasso[9]和Dantzig[10]选择算法这样的凸松弛算法。最近有文章指出，Lasso和Dantzig选择算法可以取到最好的效果[11]。

最近，一个基于稀疏信号服从特定分布的压缩感知混合高斯统计模型在文献[12]中被提出。在这篇文献中，通过对稀疏信号的概率分布的假设，将压缩感知问题作为一个统计问题进行分析，并通过该统计模型下引入线性滤波算法进行分析。在信号服从高斯或高斯混合分布的假设下，线性滤波算法被证实比传统的贪婪算法更高效。但是稀疏信号的特定概率分布假设在现实中比较难以实现和检验，而高斯随机观测矩阵却是比较常用的满足RIP性质的构造观测矩阵[13-14]，因此本文针对被高斯噪声污染的高斯测量矩阵压缩感知问题建立了一个新的高斯统计模型，将观测向量作为服从特定分布的相互独立的样本点，在此基础上，可以引入相应的统计检验方法来分析和解决压缩感知算法中出现的相关问题。

文献[15]提出的坐标下降的加权中值回归估计方法是一种通过坐标下降的线性滤波算子来估计绝对偏差最优解，以正则化参数作为硬阈值来控制解的稀疏性的l0范式约束下的优化算法。该算法被证实对重尾噪声，高斯噪声，混合高斯噪声等不同类型的噪声都是稳健的。然而，根据算法的设定，随着迭代次数的增加，硬阈值呈指数级下降，导致解的非零元个数也会随之不断增加以致远远超出真实稀疏度。因此，自适应的迭代停止准则成为通过加权中值回归估计得到真实稀疏解的必要条件。本文在高斯统计模型的基础上引入相应的统计检验方法，提出了新的计算顺序排序方法和自适应的迭代停止准则，有效地避免加权中值回归迭代算法中的需要手动控制迭代次数和残余能量下界的弊端。

本文接下来将首先介绍压缩感知问题的统计建模，然后分别介绍加权中值回归估计，以及建立在统计模型基础上的基于卡方检验的计算顺序排序方法和基于F分布的迭代停止准则，并在此基础上提出改进后的算法，再通过仿真实验结果说明算法的有效性，最后给出总结和进一步展望。

1 压缩感知问题的高斯统计模型

观测信号受到加性噪声干扰的压缩感知问题可以表示为如下数学模型进行考虑：

其中，X是N维的稀疏信号，也是目标向量，非零元素个数为K；Y是M维观测信号；A是M×N的观测矩阵，且M≪N；ξ为噪声向量。高斯随机矩阵是压缩感知问题中最常用的满足RIP性质的随机观测矩阵之一，高斯噪声也是比较常见的噪声，因此可以建立起相应的统计模型来描述这种情况下的压缩感知问题。

当M足够大时，可以选用一些合适的统计检验方法来帮助分析和解决压缩感知算法中出现的一些问题。

2 统计模型在加权中值回归估计中的应用

按照压缩感知问题模型式（1），信号重建可以表述为根据少量观测信号和给定的观测矩阵对稀疏信号求逆的过程。但方程（1）是不适定的，无法直接对其进行逆运算。用优化的方法来重建信号是一类比较常见的压缩感知算法，加权回归估计算法（WM算法）即是其中之一。

2.1 加权中值回归估计

在噪声服从重尾分布或高斯分布的情况下，可以用l1范式约束解的精确性，用l0范式约束解的稀疏性，将相应的优化问题表示如下：

其中，τ是约束解的稀疏性在优化过程中重要性的正则化参数，也是求解中衡量解的显著性的硬阈值参数。但是优化问题式（2）是一个NP难解问题。为解决这一难题，文献[10]提出了硬阈值坐标下降回归估计的方法来解决这一难题。算法描述如下：

输入：观测向量Y，高斯或伯努力随机观测矩阵A，阈值控制参数0＜β＜1，预设迭代次数K和目标残余能量ε。

大量实验表明，该算法在信噪比较高的情况下，对不同类型的噪声都是稳健的。但是，算法的迭代停止准则——最大迭代次数和残余能量下界都需要在迭代开始前人工来设定。由于硬阈值着迭代次数的增加呈指数下降的，因此，较多的迭代次数会使硬阈值过小，无法有效判定向量元素是否为零，使得解的非零元素个数超过真实个数，无法得到最优解。如果控制迭代的次数较少，又会使得算法对较小的非零元素不敏感，影响了解的精确性。因此，在噪声方差和信号稀疏性未知的情况下，有必要寻找一个合适的，自适应的迭代停止准则来帮助算法在找到最优解的时候自行中止迭代。

2.2 χ2检验下的l1支持检测

相对于原算法的坐标下降的计算顺序，提出了基于卡方检验的l1支持检测方法，通过该方法对元素的显著性进行判定，并按照元素显著性从大到小的次序进行计算。

2.3 F检验停止准则

WM算法的迭代停止准则通过人工设置迭代最大次数和误差下限的方式来实现。由于WM算法的硬阈值是随迭代次数增加指数级下降的，因此随着迭代次数的增多，算法检出的非零元素就会越来越多。如果次数过少，解的精度达不到；如果迭代次数过多，得到的解的稀疏度又会大大超过真实解的稀疏度。因此最优迭代次数是很难进行人工判断的，需要找到合适的自适应的停止准则进行代替。

WM算法将解向量初始化为零向量。在仿真实验中可以观察到，随着迭代次数的增加，残余能量曲线首先短暂下降，然后，由于硬阈值的指数级下降而迅速上升，且曲线的下降和上升都不是单调递减或单调递增的。因此需要设计一个双向的停止准则使得算法能够适应零初值的设定，也可以在残余能量快速上升之前停止迭代。

3 算法综述

考虑固定不同的正则化参数会得到不同的最优解，因此本文增加了正则化参数控制机制，只在检出非零元素个数不变的情况下才允许硬阈值下降。具体算法如下：

输入：观测向量Y，高斯随机观测矩阵A，阈值控制参数0＜β＜1，置信水平α，其中β的最优取值范围为[0.75，0.95]。在参数缺失的情况下，默认β=0.8，α=0.05。

复步骤（1），（2）；否则，停止迭代。

4 仿真实验

本章将通过仿真实验来展示改进后的算法的性能。实验1展示了改进后算法的收敛情况，实验2则展示了在不同信噪比下的还原信号的精确程度。以下实验均采用服从均值为0，方差为1的高斯分布的高斯随机观测矩阵。

4.1 实验1

本实验通过重建信号的稀疏程度对比展示改进后的算法的收敛情况。

在图1中展示了信噪比为24 dB下的两种方法在两组噪声服从方差为1的高斯分布，信号长度，稀疏度，观测信号个数分别为(250，12，100)和(512，20，256)，信噪比为35 dB的随机信号上的重建信号的残余能量的变化曲线。可以看到，WM算法的重建信号的残余能量随着迭代步数的增加先是快速下降然后不断攀升至一个稳定值，但残余能量稳定值并不是l1范式下最优的。因此可以通过对最小残余能量进行限制的方式控制迭代次数，而改进后的方法确实可以辅助输出l1范式最优解或局部较次优解。

图1 信噪比为35 dB下的重建信号残余能量对比

图2 稀疏元素为常值情况下的重建信号非零元素个数增长情况对比

图3 稀疏元素值服从N(0，10)情况下的重建信号非零元素个数增长情况对比

为了更好地说明改进后算法的收敛情况，首先在图2中对比了两种算法在两组非零元素值为常数10的随机信号上的重建信号的非零元素个数变化情况，然后在图3中展示了两种算法在非零元素值服从方差为10的高斯分布的随机信号的重建信号非零元素增长及收敛情况。可以看到随着迭代步数的增加WM算法重建信号的非零元素个数先是缓慢上升，然后快速增长，最后趋向于稳定，最终重建信号几乎全部非零，远远超过真实稀疏度。而改进后的算法可以在非零元素个数突增之前稳定下来。

从以上三组实验结果也可以看出，改进后算法的非零元素检出速度变慢了，因此可以说明支持检测算法和硬阈值下降控制机制对每步迭代的结果有所改变。

4.2实验2

图4 不同信噪比下的平均迭代次数和信号重建效果

从实验结果可以看出在信噪比较高的情况下，算法均能自适应收敛且收敛次数也是较为稳定的，重建信号的均方误差也没有较大的波动，也并没有随着信噪比变大而趋于下降。

5 结论

本文提出了高斯统计模型来解释高斯随机观测矩阵与高斯噪声下的压缩感知重建问题，并在此基础上，根据相应的统计检验方法对l0范式约束下的加权中值回归估计算法的坐标下降计算顺序和人工设定的迭代停止准则问题提出了l1支持检测计算顺序和F检验停止准则，并通过数字仿真实验验证了其有效性。

新算法本身也有一些可以继续改进的地方，尤其是针对估计向量的初始化对算法的影响和高信噪比下F检验停止准则可否在实践中推广到其他类型噪声的情况等问题还可以进一步讨论，将在今后的工作中继续探索这些问题的解决方法。

[1]Candes E J，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information[J].IEEE Trans on Information Theory，2006，52（2）：489-509.

[2]Donoho D L.Compressed sensing[J].IEEE Trans on Information Theory，2006，52（4）：1289-1306.

[3]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Trans on Signal Processing，1993，41（12）：3397-3415.

[4]Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Trans on Information Theory，2007，53（12）：4655-4666.

[5]Donoho D L，Tsaig Y，Drori I，et al.Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit[R].2006.

[6]Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J].Foundations of Computational Mathematics，2009，9（3）：317-334.

[7]Dai W，Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Trans on Information Theory，2009，55（5）：2230-2249.

[8]Needell D，Tropp J A.CoSaMP：iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis，2009，26（3）：301-321.

[9]Chen S S，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit[J].SIAM J Scientific Computing，1998，20（1）：33-66.

[10]Candes E J，Tao T.The Dantzig selector：statistical estimation when p is much larger than n[J].The Annals of Statistics，2007，35（6）：2313-2351.

[11]Candès E J，Davenport M A.How well can we estimate a sparse vector?[J].Appl Comput Harmonic Anal，2013, 34（2）：317-323.

[12]Yu G，Sapiro G.Statistical compressed sensing of Gaussian mixture models[J].IEEE Trans on Signal Processing，2011，59（12）：5842-5858.

[13]徐志强.压缩感知[J].中国科学：数学，2012，42（9）：865-877.

[14]Candes E J，Tao T.Decoding by linear programming[J]. IEEE Trans on Information Theory，2005，51（12）：4203-4215. [15]Paredes J L，Arce G R.Compressive sensing signal reconstruction by weighted median regression estimates[J].IEEE Trans on Signal Processing，2011，59（6）：2585-2601.

[16]Press W H，Teukolsky S A，Vetterling W T，et al.Numerical recipes in C++；The art of scientific computing[M]. 2nd ed.Beijing：Publishing House of Electronics Industry，2003：614-655.

BIAN Ang,ZHANG Jianzhou

College of Computer Science,Sichuan University,Chengdu 610065,China

In this paper,a novel statistical model is proposed to describe the Gaussian noisy compressed sensing problem with Gaussian random measurement matrix,and under the statistical framework,some hypothesis tests are used to analyse the performance of the weighted median regression estimate compressive sensing signal reconstruction with an iterative hard threshold under thel0-regularized constraint.Theχ2test based computation sequence is proposed to improve the performance of its coordination descent computation sequence,and F test based data adaptive stopping criterion is presented to take the place of its manual stopping conditions of the maximal number of iterations and the lower bound of the residual energy.Practical performance of the proposal is evaluated via numerical experiments.

compressing sensing;Gaussian noise;l0-regularized least absolute deviation;weighted median;hypothesis testing

A

TN911.7

10.3778/j.issn.1002-8331.1212-0374

BIAN Ang,ZHANG Jianzhou.Statistical model and applications of compressed sensing.Computer Engineering and Applications,2014,50（21）：218-223.

边昂，女，硕士，研究方向：计算机视觉；张建州，男，博士，教授，研究方向：模式识别，计算机视觉，机器学习，计算机应用技术，密码函数和计算复杂性。E-mail：bmdbianang@gmail.com

2013-01-04

2013-03-11

1002-8331（2014）21-0218-06