传统的信号采样遵循奈奎斯特采样定理，否则将可能出现混叠现象[1]，从而严重影响信号的恢复。若要高质量地重构出原始信号需要很高的采样速率，但这样会产生大量的信息冗余，浪费资源。
近年来，华裔科学家陶哲轩等人提出了压缩感知理论[2]。与奈奎斯特采样理论相比，该理论在采样端将信号采样和压缩过程并行处理，可以保证不会丢失太多原始信号的关键信息[3]。压缩感知理论由信号稀疏表示、观测矩阵及重构算法3个核心部分组成[4]，其中重构算法尤为重要，它决定着压缩感知理论是否实际可行。目前，压缩感知重构算法主要分为以下3类：贪婪算法、凸优化算法及组合算法，其中分段弱正交匹配追踪(SWOMP)算法是贪婪算法中最具代表性的算法之一。
传统的SWOMP算法采用內积准则度量方法，通过计算向量x和y的夹角余弦值来描述2个向量的相似性[5]，但用该算法重构信号时，观测矩阵中任意2个相似的原子都会影响残差信号的匹配过程，从而导致原始信号部分信号丢失。针对上述缺点，本文将引入Dice系数匹配度量准则，更好地从冗余字典中选择最佳匹配因子，从而有效地改善内积准则方法在匹配过程中原始信号部分丢失的问题。
1 SWOMP算法原理 1.1 压缩感知理论压缩感知理论表明：假设有一个长度为N的一维离散时间信号，若该信号稀疏或者在某一正交基上能稀疏表示，那么将该稀疏信号投影到另一个与正交基不相干的观测矩阵上，得到观测值，再通过观测值的传输和逆稀疏过程，便可以精确重构原始信号[6]。
如果在时域上不稀疏的信号可以在某个可逆的基上进行投影，然后得到稀疏信号，那么就满足了应用压缩感知理论的前提。而这一投影过程被称为信号的稀疏表示：
|
(1) |
式中，β=[β1, β2, …, βN]是权重系数向量，Ψ=[Ψ1, Ψ2, …, ΨN]表示稀疏基，满足ΨΨT=ΨTΨ=I；若Ψ中只有K个非零的值，另外N-K个值等于零，且K远远小于N，那么就可以把X看作是K维稀疏的信号[7]。
在用稀疏表示获取K维稀疏的信号后对信号进行观测，也就是利用M×N维的观测矩阵实行线性转换，从而获得M维的观测向量y：
|
(2) |
式中，Θ=ΦΨ，Θ为传感矩阵。观测就是把维度个数为N的初始信号X通过观测矩阵Φ以后，获得维度个数等于M的观测向量y，以便重构出维度个数为N的重构信号
信号重构是压缩感知的最后一个环节，Candes等人于2006年证明了压缩感知理论中的信号X可以通过求解最小10范数重构出：
|
(3) |
式中，X是待重构信号，y是观测以后获取的信号，‖β‖0是β的10范数，也就是β内不等于零的值的个数。
理论证明，在满足稀疏变换基与观测矩阵不相关的前提下，求解最小11范数和求解最小10范数是等价的[8]，而且前者是凸优化问题，可以转化成线性规划问题求解，即：
|
(4) |
目前针对10范数最小化的一系列贪婪算法中具有代表性的算法有OMP算法、ROMP算法、SWOMP算法等重构算法[9]。
1.2 SWOMP算法的内积准则度量法SWOMP算法按照信号重构残差值确定选择原子的最低标准，构造出候选集，再利用正交化候选集选出用来描述信号的原子，将其存入支撑集中。在候选集是空集的情况下，选取相关因子最高的原子进入支撑集，最后将支撑集内的元素通过求最小二乘法完成信号的趋近以及残差值的更换。
传统的SWOMP算法按照内积准则度量方法的要求，将冗余字典库中选择的最优因子用于架构或者更改索引集矩阵，然后与信号的残差值进行匹配，假定索引集矩阵为Ω，公式的步骤如下：
1) 组建索引集矩阵
2) 
在上式中，sim()函数表示2个向量之间的相似度，r表示残差值，φ表示冗余字典中的因子，挑选φ存在于索引集矩阵Ω中。
内积准则为：
其中g代表当前迭代过程中与残差值最相似的因子，Φ表示冗余字典库集合。内积方法计算出来的绝对值越大，说明残差值和挑选的因子两向量越相似。
SWOMP算法重建原始信号时，应用内积准则度量相似度的实质是通过计算从冗余字典库中寻找到的匹配因子与残差值的夹角余弦值。夹角余弦值越大，夹角越小，2个向量越相似。对任意2个向量x与y，内积匹配准则为：
|
(5) |
信号重构的实质是对最优因子索引集矩阵进行重构计算。SWOMP算法是按照内积准则对原始信号进行重构，很难从冗余字典库中挑选出适合残差值信号的最优因子，不易达到较高的还原性能，因此如何在算法中挑选出与残差值匹配的最优因子索引集矩阵是一个重要的问题。为了发现索引集矩阵，提升SWOMP算法的重构性能，需要寻找一种更好的方法来挑选与残差值匹配的最优因子。
2 基于Dice系数匹配准则的SWOMP算法 2.1 Dice系数匹配准则SWOMP算法重构信号时，在每次迭代过程中都需要重新确定残差信号的组成元素，并从冗余字典中选出与残差信号匹配的最佳原子。利用内积准则度量相似性时，分母是对向量分量的平方和求几何平均值，不能很好地保留每个向量分量的原始状态，进而会影响对相似原子的区分，使观测矩阵中任意2个相近似的原子都可能会影响残差信号的匹配过程，导致部分原始信号丢失，降低信号的重构质量。为解决这一问题，引入Dice系数，对任意2个向量x和y，Dice系数的定义为:
|
(6) |
Dice-SWOMP算法与传统的SWOMP算法的不同点就在于它引入了Dice系数作为衡量匹配的准则，优化后的算法如下：
|
(7) |
|
(8) |
由此可知，Dice-SWOMP算法在每一次迭代时都需要重新计算所有冗余的匹配因子与残差值的相似度。利用Dice系数匹配准则度量相似性时，分母是对向量分量的平方和求算术平均值，与几何平均值相比，算数平均数能更多地保留每个向量的原始特征，突出向量的组成元素。针对任意2个向量x与y，Dice系数均可最大化的有效运用向量中的各个数值来求解相关性，解决了几何平均值方法在匹配过程中导致原始信号部分丢失的问题。因此相对于内积准则，在原子间相关性较高的字典中，Dice-SWOMP算法可以更显著地区分2个相似的原子，更好地从冗余字典中挑选出与残差向量匹配的原子，极大地提升了信号的重构性能。
2.2 基于Dice系数的分段弱正交匹配追踪(Dice-SWOMP)算法流程Dice-SWOMP算法的具体步骤如下：
1) 初始化
2) 计算
3) 令∧t=∧t-1∪J0, At=At-1∪aj(for all j∈J0)；若∧t=∧t-1，也即无新列被选中，则停止迭代进入第7)步；
4) 求y=Atβt的最小二乘解：
|
5) 更新残差
6) t=t+1，如果t≤K，则返回第2)步继续迭代；如果t>K或者残差rt=0，那么终止重复代入直接进行第7)步；
7) 重构所得
其中，rt代表残差，t代表迭代次数，传感矩阵A=ΦΨ，K代表信号的稀疏度，Φ代表空集，∧t代表t次重复代入的索引(列序号)集，λt表示t次迭代找到的索引(列序号)，aj表示矩阵A的第j列，信号稀疏表示系数估计
实验平台基于MATLAB R2014a，Windows7操作系统。CPU选用奔腾3558u双核处理器，主频1.7G，内存4GB。本节通过仿真实验得出了SWOMP算法与Dice-SWOMP算法在重构性能上的对比图，评估了SWOMP算法与Dice-SWOMP算法在以下几个方面的性能: ①单次重构的恢复残差；②在稀疏度一定时，信号在不同观测维数下的重构成功概率；③在观测维数一定时，信号在不同稀疏度下的重构成功概率。
信号重构成功率定义为:
|
实验利用SWOMP算法与Dice-SWOMP算法分别从观测矩阵中选取匹配原子，并比较了2种不同重构算法对信号恢复残差的影响。对长度为N=256，稀疏度K=12，观测维数M=128的信号进行重构，取M×N的高斯随机矩阵作为观测矩阵。
通过对比图 1、图 2及表 1中2种不同算法的仿真结果可知：与传统的SWOMP算法相比，优化后的Dice-SWOMP算法具有更小的单次重构恢复残差，重构精度更高。
|
| 图 1 SWOMP算法单次重构 |
|
| 图 2 Dice-SWOMP算法单次重构 |
实验比较了当稀疏度一定时，SWOMP算法与Dice-SWOMP算法在不同观测维数下的重构成功率。取信号长度N=256，观测维数M，稀疏度K，并采用高斯随机矩阵作为观测矩阵。在每个测试点(K, M)上，重复实验1 000次，以便观察在不同观测维数M下的信号重构成功率。
图 3和图 4分别为当选取若干稀疏度K值时，Dice-SWOMP算法与SWOMP算法在不同观测维数M值下的重构成功率。当稀疏度K值一定时，随着观测维数M的增加，Dice-SWOMP算法与SWOMP算法的信号重构成功概率均在逐渐增加；当观测维数M值一定时，随着稀疏度K值的增加，Dice-SWOMP算法与SWOMP算法的重构成功概率均在逐渐减小；当重构概率达到1时，随着稀疏度K值的不断变大，Dice-SWOMP算法与SWOMP算法所需要的观测维数均在不断增加。
|
| 图 3 SWOMP算法 |
|
| 图 4 Dice-SWOMP算法 |
如图 5所示，当稀疏度K=20，仿真验证了2种算法下观测维数M和重构成功率的关系。由仿真结果可知，随着观测维数M逐渐的增大，SWOMP算法与Dice-SWOMP算法的信号重构成功率均在逐渐增大。在观测维数M相同的情况下，与SWOMP算法相比，Dice-SWOMP算法具有更高的重构成功率。当重构概率达到1时，相比SWOMP算法，Dice-SWOMP算法所需的观测维数M更少。
|
| 图 5 SWOMP与Dice-SWOMP算法在不同观测维数M下的重构成功率 |
实验比较了当观测维数一定时，SWOMP算法与Dice-SWOMP算法在不同稀疏度下的重构成功率。实验中取信号长度N=256，观测维数M，稀疏度K，采用的观测矩阵为高斯随机观测矩阵。在每一个测试点(K, M)上，重复实验1 000次，以便观察在不同稀疏度K下的信号重构成功率。
图 6和图 7分别为选取若干观测维数M值，SWOMP算法与Dice-SWOMP算法在不同稀疏度K下的重构成功率。由仿真结果可知：当观测维数M值一定时，随着稀疏度的增加，SWOMP算法和Dice-SWOMP算法的信号重构成功概率均在逐渐减小；当稀疏度K值一定时，随着观测维数M的增加，SWOMP算法和Dice-SWOMP算法的重构成功概率在逐渐增大；当重构概率达到1时，随着观测维数M的不断变大，SWOMP算法和Dice-SWOMP算法所能适应的稀疏度K也在不断增加。
|
| 图 6 SWOMP算法 |
|
| 图 7 Dice-SWOMP算法 |
如图 8所示，当观测维数M=100时，仿真验证了在2种算法下稀疏度K和信号重构成功率的关系。由仿真结果可知，随着稀疏度K不断增加，SWOMP算法与Dice-SWOMP算法的信号重构成功率均逐渐减少。当稀疏度K一定时，与SWOMP算法相比，Dice-SWOMP算法具有更大的重构成功率。当重构概率等于1时，相比SWOMP算法，Dice-SWOMP算法所能适应的稀疏度K更大。
|
| 图 8 观测维数M=100, 2种算法在不同稀疏度K下的重构成功率 |
本文在传统的SWOMP算法基础上，引入了Dice系数匹配准则后，在原子间相关性较高的字典中，能更好地辨别2个相似的原子并挑选出与残差信号匹配的最佳原子，从而提高信号的恢复质量。通过仿真实验可知，在相同的条件下，与SWOMP算法相比，Dice-SWOMP算法具有更小的恢复残差以及更高的信号重构成功率。
| [1] |
焦李成, 杨淑媛, 刘芳, 侯彪. 压缩感知回顾与展望[J]. 电子学报, 2011, 7(39): 1651-1662.
Jiao Licheng, Yang Shuyuan, Liu Fang, Hou Biao. Development and Prospect of Compressive Sensing[J]. Acra Electronica Sinica, 2011, 7(39): 1651-1662. (in Chinese) |
| [2] |
杨海蓉, 张成, 丁大为, 韦穗. 压缩传感理论与重构算法[J]. 电子学报, 2011, 39(1): 142-148.
Yang Hairong, Zhang Cheng, Ding Dawei, Wei Sui. The Theory of Compressed Sensing and Reconstruction Algorithm[J]. Acra Electronica Sinica, 2011, 39(1): 142-148. (in Chinese) |
| [3] | Gao R, Zhao R Z, Hu S H. Variable Step Size Adaptive Matching Pursuit Algorithm for Image Reconstruction Based on Compressive Sensing[J]. Acta Optica Sinica, 2010, 30(6): 1639-1644. DOI:10.3788/AOS |
| [4] | Baraniuk R G, Cevher V, Duarte M F, et al. Model-Based Compressive Sensing[J]. IEEE Trans on Information Theory, 2010, 56(4): 1982-2001. DOI:10.1109/TIT.2010.2040894 |
| [5] | Jacques L, Laska J N, Boufounos P T, et al. Robust 1-bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors[J]. IEEE Trans on Information Theory, 2013, 59(4): 2082-2102. DOI:10.1109/TIT.2012.2234823 |
| [6] | Zhao S, Zhang Q Y, Yang H. Orthogonal Matching Pursuit Based on Tree Structure Redundant Dictionary[J]. Communications in Computer and Information Science, 2011, 2: 310-315. |
| [7] | Karahanoglu N B, Erdogan H. A* Orthogonal Matching Pursuit:Best-First Search for Compressed Sensing Signal Recovery[J]. Digital Signal Processing:A Review Journal, 2012, 22(4): 555-568. DOI:10.1016/j.dsp.2012.03.003 |
| [8] | Needell D, Vershynin R. Signal Recovery from Incompleteand Inaccurate Measurements via Regularized Orthogonal Matching Pursuit[J]. IEEE Journal on Selected Topics in Signal Processing, 2010, 4(2): 310-316. DOI:10.1109/JSTSP.2010.2042412 |
| [9] |
戴琼海, 付长军, 季向阳. 压缩感知研究[J]. 计算机学报, 2011, 34(3): 425-434.
Dai Qionghai, Fu Changjun, Ji Xiangyang. Research on Compressed Sensing[J]. Chinese Journal Computers, 2011, 34(3): 425-434. (in Chinese) |
