大学科研成果论文(18)

1、fujian agriculture and forestry university科研成果论文论文题目基于压缩感知的的信号重构算法学 院:计算机与信息学院专业年级：电子信息工程2010级学 号：姓 名：指导教师、职称：2012年11月15日基于压缩感知的的信号重构算法摘要: 针对支撑集未知且变化时的稀疏信号的重构问题，本文基于卡尔曼滤波思想，结合压缩感知算法，给出了一种改进的卡尔曼一压缩感知(modified kalman fiher compressive sensing, mkfcs)信号重构算法，该算法首先利用kalman滤 波获得信号残差的有效估计，然后根据残差变突情况，用改进的cs

2、算法估计突变位置以确定信号的新的支撑集，最后用最小 二乘方法重构信号，从而自适应的实现支撑集未知且变化的稀疏信号的重构。最后对所改进的通过重构精度、重构误差、稳 健性等方面进行了仿真，仿真结果表明所提算法重构信号具有需要量测个数少、重构精度高、鲁棒性强等特点。关键词： 压缩感知；坡小范数；信号重构：引言至今，己有众多国内外学者在重建算法领域做出了新的研宄和探索。candes等证明了信号重建问题可以通过求解最小l范数问题解决，但donoho指出，求解最小范数是一个np问题，需要穷举x中非零值的所有尺中排列可能，因而无法直接求解。此后，研宄人员提出了一系列求得次最优解的算法，主要包括最小/,范数法

3、、贪婪迭代匹配追踪系列算法等。其中，匹配追踪类方法为其近似求解提供了有力工具，文献中指出了该类方法用于稀疏信号重建时具有一定的稳定性。重建算法的关键是如何从压縮感知得到的低维数据中精确地恢复出原始的高维数据，即由m维测量 向量重建出长度为;v(m<2v)的信号x的过程。传统的匹配追踪算法能够精确的重建出原始信号，但同时又有不同方面的缺陷，因此有关压縮感知重建算法的研宄还有很多值得探索和研宄的地方,二最小z。范数模型从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数量少于待解的未知数)的最简单解的问题，i范数刻画得就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏

4、。通常我们采用下式描述最小范数最优化问题：(3. 1)y = x实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中d是一个极小的常量：(3.2)minllxllo ,t.卜叫但是这类问题的求解数值计算极不稳定，很难直接求解。三匹配追踪类算法匹配追踪类稀疏重建算法解决的是最小范数问题，最早提出的有匹配追踪(mp)算法和正交匹配追踪(omp)算法。mp的基本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在

5、己选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。omp算法则有效克服了这个问题，该算法沿用了匹配追踪算法中的原子选择准则，在重建时每次迭代得到s的支撑集的一个原子，只是通过递归对己选择原子集合进行正交化以保证迭代的最优性，从而减 少迭代次数。实验表明对固定&-稀疏的维离散时间信号 ,用高斯随机矩阵时，只要m= 0(k'°sn)，正交匹配追踪算法将以极大概率准确重构信号，而且运行时间远比最小&范数模型短。但是，正交匹配追踪算法精确重构的理论保证比最小&范数算法弱，并

6、非对所有信号都能准确重构，而且 对于感知矩阵的要求比约束等距性更加严格。needell 等在 omp 的基础上提出了正则正交匹配追踪(regularized orthogonal matching pursuit,romp)算法，对于所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。之后，needell等人又 提出了引入回溯思想的压缩采样匹配追踪(compressive sampling matching pursuit, cosamp)算法，不仅提供了比omp算法更全面的理论保证，并且能在采样过程中对噪声有很强的鲁棒性。同样引入回溯思想的还有子空间追踪(subspace pursui

7、t, sp)算法，在得到义的支撑集之前先建立一个候选集，之后再从候 选集中舍弃不需要的原子，形成最终的支撑集，它们理论重建质量与相当，同时重建复杂度低，但是这些 算法都是建立在稀疏度k己知的基础上。然而实际应用中，&往往是未知的，由此出现了对夂自适应的稀疏自适应匹配追踪(sparsity adaptive matching pursuit, samp)算法，它通过固定步长逐步逼近进行重建，可以在厂未知的情况下获 得较好的重建效果，速度也远快于omp算法。综合考虑，匹配追踪系列算法对于维数较低的小尺度信号问题运算速度很快，是一种效果较好的信号重建算法。3.1 omp算法omp算法作为最早

8、的贪婪迭代算法之一,它的思想对之后出现的各种贪婪算法都有着不容忽视的意义。 omp仍然沿用了 mp算法中的原子选择准则，不同的是omp算法要将所选原子利用gram-schmidt正交化方法进行正交处理，再将信号在这些正交原子构成的空间上投影，得到信号在各个己选原子上的分量和余量,然后用相同方法分解余量。在每一步分解中，所选原子均满足一定条件，因此余量随着分解过程迅速减小。通过递归地对已选择原子集合进行正交化保证了迭代的最优性，从而减少了迭代次数。另一方面，omp的重建算法是在给定迭代次数的条件下重建，这种强制迭代过程停止的方法使得omp需要非常多的线性测量来保证精确重建。总之，它以贪婪迭代的方

9、法选择力的列，使得在每次迭代中所选 择的列与当前的冗余向量最大程度地相关，从测量向量中减去相关部分并反复迭代，直到迭代次数达到稀疏度强制迭代停止。首先需要说明的是，匹配追踪类算法通过求余量r与感知矩阵$中各个原子之间内积的绝对值，来计 算相关系数u:u =(3. 3)并采用最小二乘法进行信号逼近以及余量更新:(3.4)x =argmin|r-oax|9new(3.5)omp算法的具体步骤如下:(1) 初始余量4 =迭代次数 =1,索引值集合a = 0, j=0;(2) 计算相关系数u，并将u中最大值对应的索引值存入7中;(3)更新支撑集其中a = aujo;(4)应用式(3. 3)得到x ,同

10、时用式(3. 4)对余量进行更新；若令/7 = /1 + 1,转步骤；否则，停止迭代。为了进一步说明omp算法的重建效果，采用大小为512x512的lena图像作为测试图像，为便于测量矩阵的生成，将该图像数据分成1024个大小为16x16的块，进而生成大小为256x1024的图像数据。利用该方法对原图像进行预处理之后，采用离散余弦变换作为稀疏变换以及高斯随机矩阵作为测量矩阵。表3.1和图3-1直观地给出了 lena图像在采样率分别为m/n=0. 7、0. 5、0. 3时的重建图像。0mp算法保证了每次迭代的最优性，减少了迭代的次数。但是，它在每次迭代中仅选取一个原子来更新原子集合，这样必然会付

11、出巨大的重建时间代价。迭代的次数与稀疏度x或采样个数m密切相关，随着迭代次数的増大，耗时也将大幅増加。因此之后出现了许多改进的匹配追踪算法，如romp、stomp、cosamp算法等等，都希望在重建时间和重建质量之间取得一个较好的平衡，保证重建质量的同时提高重建效率。3.2 romp 算法正则正交匹配追踪(romp)算法对所有满足rip条件的矩阵和所有稀疏信号都可以精确重建，且重建速度较快。对于稀疏度为夂的信号重建问题，romp算法首先根据相关原则进行原子的一次筛选，通过求余 量r与测量矩阵$中各个原子之间内积的绝对值，来计算相关系数u ,并将按照此方法筛选出的夂个原子的索引值存到候选集7中以

12、便进行原子的二次筛选。romp算法采用正则化过程进行原子的二次筛选，即根据式(2. 6)将7中索引值对应的原子的相关系数分成若干组:i，jd(3. 6)然后选择能量最大的一组相关系数对应的原子索引值存入中。该正则化过程可以使得化romp算法最多经过夂次迭代便可以得到一个原子数i a |小于2夂的支撑集0a用于精确重建信号，对于没有选入支 撑集的原子，正则化过程则能保证它们的能量一定远小于被选入原子的能量，是一种简单有效的原子筛选方法。经过一定的迭代得到用于信号重建的支撑集后，再釆用最小二乘法进行信号逼近以及余量更新。romp算法的基本步骤如下：(1) 初始余量估计信号稀疏度为厂，迭代次数 =1

13、,索引值集合a = 0，/=0;(2) 用式(3.3)计算相关系数u，并从u中寻找夂个最大值对应的索引值存入7中；(3) 对7中索引值对应原子的相关系数进行正则化，并将正则化结果存入集合中，该集合中原子的 相关系数必须满足式(3. 6);(4) 更新支撑集中八，其中a = au/。；(5) 应用式(3.4)得到f，同时用式(3. 5)对余量进行更；若la>2/c,则停止迭代；否则令f =n = n + lf转步骤。从上述算法的步骤中可以看出，只有首先对信号稀疏度进行适当估计才能进一步精确重建信号，但大量实验表明，如果对信号的稀疏度预先估计过小，那么迭代多次依然无法达到停止迭代条件；如果对

14、稀疏度估计的过大，那么重建质量无论从视觉效果还是从客观数据上都很差，远不能达到精确重建的效果。3.3 cosamp 算法0mp算法每次只选择一个与余量相关的原子，从原子的选择方式上看实现了单个原子的精确选择。引 入回溯思想的压缩采样匹配追踪(compressive sampling matching pursuit, cosamp)算法则从原子库中选择多个较相关的原子同时剔除部分原子，从而提髙算法效率。cosamp算法保证了候选集合最多不会超过3&个原子，每次迭代支撑集拥有2夂个原子，同时剔除的原子数目最多不超过夂个。cosamp算法具体算法如下：(1) 初始余量估计信号稀疏度为尺，迭

15、代次数 =1,索引值集合a = 0，y =0;(2) 用式(3. 3)计算相关系数u ,并从u中寻找2夂个最大值对应的索引值存入7中；(3) a = auj,应用(3.4)得到取前k个最大元素对应的原子放入支撑集$八。(4) 应用式(3.4)得到x，同时用式(3. 5)对余量进行更；若la>2/c,则停止迭代；否则令f = n = n + lf转步骤。表3.2和图3-2给出了cosamp算法下lena图像在采样率分别为m/n=0.7、0.5、0. 3时的重建图像。cosamp算法每次迭代中都要同时选中多个原子，而且最终用于重建的支撑集大小是确定的，这就需要我们在迭代过程中不断选中原子的同

16、时剔一部分以前选中的原子。那么这种方式能否保证每轮迭代中至少选中一个最终用于信号重建的原子而不会被剔除，这是一个值得质疑的问题。本文就其原子的选择方式对算法准确性的影响进行了分析和推导。结论说明即便剔除了己经选定的部分原子依然可以保证留下的原子是最优的从而精确重建信号。正则化自适应匹配追踪算法虽然cosamp算法引入了回退筛选的思想，其重建质量与lp相当，同时重建复杂度低，但是这些算法都是建立在稀疏度&己知的基础上。然而实际应用中信号的稀疏度&往往是未知的，由此出现了对稀疏 度&自适应的samp算法，它通过设置一个可变步长，逐步对信号稀疏度进行估计，因此可以在&

17、未知的 情况下获得较好的重建效果，速度也远快于0mp算法。基于romp算法和samp算法的突出优势，本文提出了正则化自适应匹配追踪算法，该算法解决了稀疏度夂未知的情况下信号精确重建问题，同时也是一种近 似解决&范数最小问题的贪婪迭代算法。正则化自适应匹配追踪算法(regularized adaptive matching pursuit, ramp)在采用romp算法中正则化过程的基础上，结合了 samp算法的自适应思想。该算法在稀疏度问题上克服了正则化过程的局限性,算法本身可以在迭代过程中自动调整所选原子数目来重建稀疏度未知的信号。算法中釆用转换阶段的方式逐步增加该原子数，将同一个迭

18、代过程分成多个阶段，设置一个可变步长代替所选原子数目，相邻两个阶段所对应的支撑集的大小之差即为当前步长，随着步长的増加和支撑集的不断増大，实现了在未知稀疏度的前提下步长逐步逼近夂进而精确重建出原始信号的目的。正则化自适应匹配追踪算法结合了 romp算法正则化思想以及ramp算法自适应思想的新的重建算法，保证了全局优化的同时提髙了算法的运算速度。下列步骤具体说明了该算法的过程，其中&与&分别为 控制迭代次数与阶段转换的闳值，为达到较好的重建精度以及严格控制阶段转换的目的，根据所处理信号 的具体信息适当地选择阈值的大小，算法具体步骤如下:(1) 初始余量r°=y,初始步长

19、* 0 ,阶段wzd ,迭代次数n = if索引值集合a = 0,j=0；(2) 若m2<,则停止迭代，利用得到的原子进行最终的信号重建；否则进入步骤(3);(3) 利用式(3. 3)计算相关系数u ,并从u中寻找hze个最大值对应的索引值存入/中；(4) 对j中索引值对应原子的相关系数进行正则化，并将正则化结果存入集合中，该集合中原子的 相关系数必须满足式(3. 6);(5) 更新支撑集其中a =(6) 应用式(3. 4)得到,同时用式(3. 5)对余量进行更新；若|。一dnq ,则令size = size stage、转步骤(3);否则，令 =、，" = " +

20、转步骤(2)。正如上述ramp算法中的步骤和步骤(2)所示，通过设置两个阈值，整个实验过程可以自适应地判断是否需要调整当前步长，以决定是否进入下一个阶段或是下一次迭代。因此该算法不需要将稀疏度&作为先 验知识进行信号重建，避免了由于步长选定的过小(远小于信号稀疏度)导致的迭代多次依然无法达到停止迭代条件的问题，同时也避免了同类其它算法中阈值选得太小造成的需要较多次迭代才能达到所需重建精度的过匹配现象。步骤的正则化过程保证了最多经过夂次迭代就可以得到用于信号精确重建的支撑集，使 得该算法能获得较好的重建质量的同时，大大缩短了运行时间。参考文献1 donoho d l. compresse

21、d sensingj. ieee transactions oil information theory, 2006, 52(4): 1289一1306.2 cand6se, romberg j, tao t- robust uncertainty principles： exact signal reconstruction from highly incomplete frequency informationj. ieee transactions on information theory, 2006, 52(4): 489509.3 cand6s e, tao t. near optimal signal recovery from random projections： universal encoding strategies j. ieee trans一actions on information theory, 2006, 52(12): 5406一5425.4 cancps e, wakin m b. an introduction to compressive samplingj. ieee signal processing magazine, 2008, 25(2)： 2130.5 mallats, zhang z