一种压缩感知中的改进的正则化牛顿算法.doc

一种压缩感知中的改进的正则化牛顿算法摘要：在结合牛顿法和正则化正交匹配追踪(Regularized Orthogonal Matching Pursuit，ROMP)的基础上，提出了一种新的正则化牛顿算法，并对其中的正则化过程进行了改进。仿真结果表明，本文提出的算法在重构精度上要高于正交匹配追踪(Orthogonal Matching Pursuit，OMP)和正则化正交匹配追踪(ROMP)，而在迭代次数和重构时间上要低于牛顿法和正交匹配追踪(OMP)。关键词：压缩感知；牛顿法；正则化；匹配追踪An Improved Regularized Newton Algorithm for Compressive SensingAbstract：A new Regularized Newton Algorithm is proposed based on the combination with Newton Algorithm and Regularized Orthogonal Matching Pursuit(ROMP), and the regularized process is also improved. Simulation results show that, the algorithm proposed is better than Orthogonal Matching Pursuit (OMP) and ROMP in recovery accuracy and also lower than Newton and OMP in the iteration number and reconstruction time.Key words: compressive sensing; Newton Algorithm; Regularized；Matching Pursuit1引言 压缩采样(Compressed Sampling，CS)1-3针对具有稀疏性或在特定域上可转化为稀疏性的信号，通过实施远低于奈奎斯特采样率的的随机采样，可准确完成原始信号的重构。由于CS有效降低了信号获取、存储及传输的代价，该理论一经出现即得到广大研究人员的密切关注。设x是一个长度为N的实向量，即。x中只有不超过K个非零元素，x被称作K-稀疏。研究表明，对x进行随机线性投影，即，其中y是M维观测向量(M N)，是MN的测量矩阵，则基于y可有效完成信号x的重构。 如何在已知y和的条件下快速、有效的重建x是CS研究的一个重要方面。目前已有的方法可包括已有多种用于压缩感知重建的算法发表4，如梯度投影法、基追踪法、匹配追踪法等等几类。这些算法中，贪婪算法由于算法结构简单、运算量小等特点受到重视。传统贪婪算法匹配追踪(MP)、正交匹配追踪(OMP)5已在压缩采样中得到了应用。改进的算法包括分段正交匹配追踪(Stage-wise OMP, StOMP)、正则化正交匹配追踪(Regularized OMP, ROMP)以及引入回溯思想的SP(Subspace Pursuit)6和CoSaMP(compressive Sampling Matching Pursuit)7。牛顿法8是一种收敛速度快于最速下降法的寻优算法，其收敛速度快且重建效果也较好，牛顿算法中采用类似于MP、OMP的原子选择原则，每次也是选择一个原子，但其收敛速度要低于OMP。如果我们引入正则化思想，则可以大大加快算法的收敛速度，并且具有较好的重建效果。2 压缩感知与重建算法设x为长度为N的原始信号，y为长度M的观测信号， (M (可取0.0001), iter=iter+1,转步骤2；否则停止迭代，并输出；（2）计算相关系数,将u中k个绝对值最大的值对应的索引存入id中；（3）对id中索引值对应原子的相关系数进行正则化，并将正则化结果存入集合中，该集合中原子的相关系数必须满足式(9)和式(10)；（4），得到支撑集；（5）利用（3）式对进行更新，其中，；（6）更新迭代余量,转步骤（1）；4 仿真结果4.1 一维稀疏信号首先定义重构信噪比，当时，重构信号与原信号在视觉上没有差异，认定算法实现了精确重构。事实上，若信号重构失败，SNR不超过10；而若信号能够实现精确重构，SNR都在300dB左右徘徊，所以将门限设置在60是合理的。构造一个N=500，K=50的一维信号。观测矩阵采用高斯随机矩阵，分别采用牛顿法、正则化牛顿法、OMP、ROMP对其进行重构。每次实验均取运行500次的平均值。图1 不同算法重构概率的比较从图1可以看出，随着压缩比的增大，重构概率呈指数增长趋势。其中牛顿法的重构性能最好，正则化牛顿法保持了牛顿法高重构率的优点，重构概率大于OMP算法和ROMP算法。图2 不同算法残差r的比较图2是残差r跟迭代次数的关系。可以看出，随着迭代次数不断增加，残差r呈指数减小趋势。正则化牛顿法和ROMP算法比牛顿法和OMP的残差衰减速度明显变快。在满足相同的迭代终止条件，正则化牛顿法和ROMP算法的迭代次数远远小于牛顿法和OMP方法。图3 不同算法在不同稀疏度下的重构概率从图3可以看出，随着稀疏度增加，重构概率在不断下降。正则化牛顿法在不同稀疏度下的重概率高于OMP和ROMP，低于牛顿法。并且当K50后，ROMP算法基本失效（重构概率几乎为0），但是正则化牛顿直到K80后才彻底失效。可见正则化牛顿法对于稀疏度的要求放宽。图4 不同算法在不同稀疏度下的重构时间从图4中可以很明显看出，在相同稀疏度下正则化牛顿法的重构时间要小于其他三种算法，并且随着稀疏度K的增加，其重构时间增加很缓慢，具有较快的重构速度。图中ROMP的重构时间在K50后迅速上升是因为ROMP算法失效，每次重构需要经历过很大的迭代次数，才能达到终止条件。4.2 图像实验实验中实用的图像是256*256的标准Lena图，采样矩阵是高斯随机矩阵。表1 不同算法重建时间和性能比较M/N0.60.7PSNRTIMEPSNRTIMEPSNRTIMEPSNRTIMEPSNRTIME牛顿法20.7122.5725.8923.6826.0836.2728.7339.8031.3140.37正则化牛顿法18.671.8824.763.1627.565.1629.817.9431.9111.81OMP13.884.3624.136.1626.717.3428.3310.1129.9512.46ROMP14.941.7916.852.5716.843.7517.855.3322.407.05从表1中可以看出，重建时间最快的是ROMP，但ROMP重建性能较差，而正则化牛顿法的重构时间与ROMP相差无几，但PSNR要比ROMP高很多，能达到牛顿法和OMP的重构性能甚至超过。而跟牛顿法和OMP相比，在重构性能差不多的前提下，重构时间得到了显著下降。5 结论本文在牛顿法和ROMP的基础上提出了正则化牛顿法，结合了牛顿法收敛较快以及ROMP较好的重构性能的特点，并对传统正则化过程进行了改进，从而进一步提高了重构精度。实验证明，正则化牛顿法在保证重构性能较优的基础上，重构时间得到了很大改善，可见具有较强的实用性。牛顿法涉及求矩阵的逆，计算量很大，如果我们将最优化中的拟牛顿法结合正则化思想，可以进一步提高算法的重构时间，在以后工作中值得尝试。参考文献1 D. L. Donoho, “Compressed sensing,” IEEE Trans. on Information Theory, 2006.vol. 52, pp. 12891306.2 DONOHO D.Compressed sensing J. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.3 Cands E, Romberg J, and Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.4 金坚,谷源涛,梅顺良. 压缩采样技术及其应用J.电子与信息学报，2010. vol.32 no.2. pp.470-4755 J. Tropp and A. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit.,” IEEE Trans. Info. Theory, vol. 53, pp. 46554666, Dec 2007.6 W. Dai and O. Milenkovic, “Subspace pursuit for compressive sensing: Closing the gap between performance and complexity,” Preprint, Mar 2008.7 D. Needell and J. A. Tropp, “Cosamp: Iterative signal recovery from incomplete and inaccurate samples” Preprint, Mar 2008.8 解可新, 韩健, 林友联. 最优化方法M. 天津：天津大学出版社，