基于压缩感知的贪婪类重构算法原子识别策略综述

刘素娟 崔程凯 郑丽丽 江书阳

(北京工业大学微电子学院 北京 100124)

1 引言

压缩感知(Compressed Sensing, CS)理论的提出避免了奈奎斯特采样定理在信号处理领域的局限性，实现了稀疏信号的亚奈奎斯特频率采样[1-3]。根据稀疏信号的稀疏特性，利用不相干的测量矩阵将高维稀疏信号投影到低维后进行处理，在滤波之后使用远低于奈奎斯特频率的模数转换器(Analog to Digital Converter, ADC)进行采样，采样后的数字信号包含了原始信号的全部信息。最后，通过利用重构算法求解线性优化问题重构原始信号。

压缩感知重构算法主要包括贪婪算法、凸优化算法和其他算法。贪婪类算法由于其硬件实现的简便易行得到了广泛学者的青睐。匹配追踪算法(Matching Pursuits, MP)[4]奠定了贪婪算法的基础，其核心思想是利用原子向量的线性运算去逐渐逼近信号向量，经过不断迭代，最后选择出以稀疏度为参考个数的原子。但是在迭代过程中，如果残差在已选择原子上的垂直投影是非正交的，则迭代后得到的结果将不是最优的而是次优的。这会导致在后续迭代过程中可能会重复选择到相同的索引，算法收敛需要更多的迭代次数。正交匹配追踪算法(Orthogonal Matching Pursuit, OMP)[5]作为贪婪类算法继续发展的重要基础，克服了MP算法的缺陷。 在OMP算法的迭代过程中，残差总是能够与已经选择过的原子正交，这保证了相同的索引不会被重复选择，迭代过程将会在有限的几步内收敛。在OMP算法基础之上，正则化正交匹配追踪算法(Regularized Orthogonal Matching Pursuit,ROMP)[6]及其变体[7]，广义正交匹配追踪算法(generalized Orthogonal Matching Pursuit,gOMP)[8]及其变体[9]，分段正交匹配追踪算法(Stagewise Orthogonal Matching Pursuit,StOMP)[10]及其变体[11]，稀疏度自适应匹配追踪算法(Sparsity Adaptive Matching Pursuit,SAMP)[12]及其变体[13-15]，基于投影的原子选择正交匹配追踪算法(Projection-based atom selection in Orthogonal Matching Pursuit, POMP)[16-18]，压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit, CoSaMP)[19,20]及其变体[21,22]，子空间追踪算法(Subspace Pursuit, SP)[23,24]及其变体[25-28]，向前展望正交匹配追踪算法(Look Ahead Orthogonal Matching Pursuit, LAOMP)[29]及其变体[17,30-32]等算法陆续被提出。算法的更新趋势是在已存在的算法原型上进行改进，使新算法在提高恢复性能、降低计算复杂度以及减少计算时间成本等方面更加具有优势。

作为贪婪类算法的核心，原子识别策略的差异往往决定了算法重构性能的优劣。虽然重构算法种类繁多，但嵌入到各类算法中的原子识别策略种类是有限的。据此，本文在稀疏信号压缩感知模型的基础上对贪婪类重构算法的原子识别策略进行了归纳与总结，着重综述了算法在不同处理阶段可以运用的原子选择策略。目的是通过归纳综述这些原子识别策略增进对贪婪类算法的理解，通过对原子识别策略的组合优化及运用，提出性能更加优越的新算法。

2 压缩感知模型

压缩感知理论摒弃先采样后压缩的传统做法，实现了采样和压缩的同步进行，降低了采样速率，减少了处理成本和存储成本[1]。如式(1)所示，原始信号x在正交基矩阵θ上被稀疏表示为θα，其中α为仅包含有限非0元素的投影系数向量。使用与正交基矩阵θ满足约束等距条件(Restricted Isometry Propetry, RIP)的观测矩阵Ψ∈RM×N对稀疏信号x进行线性测量，并将观测矩阵与正交基矩阵的乘积称为感知矩阵A∈RM×N。滤波采样后得到从维度为N的高维向量x压缩到维度为M的低维观测向量y ∈RM×1,y包含了原始信号的全部信息。其中，

3 贪婪类重构算法原子识别策略

作为贪婪类算法最重要的一环，原子识别过程指的是通过以内积、投影或残差等变量作为判断依据，在感知矩阵A中选择出以稀疏度作为参考个数的列向量构成索引集。将索引集中的列向量称为原子，则可以通过求解最小二乘问题得到原始观测向量y在由这些原子所构成的矩阵上的投影系数向量α，继而通过等式x=θα恢复出原始信号。

为了便于描述，每次迭代过程中所选择出的列向量集合称为最终支撑集，最终支撑集以外的其他列向量所构成的集合称为潜在支撑集，最终支撑集与潜在支撑集的并集中需要进一步识别处理的原子集合称为候选支撑集。A代表感知矩阵，y表示观测向量，K表示信号稀疏度，M表示感知矩阵的行数，N表示感知矩阵的列数，r表示残差，t表示迭代次数。t作为下标时表示变量处于第t次迭代状态。集合符号作为矩阵下标时表示取矩阵中集合所指定位置的列向量。AT表示A矩阵的转置，A†表示A矩阵的伪逆矩阵。l ength()表示取向量的长度。下文中信号估计值的计算过程是对最小二乘问题的求解，如式(4)所示

图1 压缩感知模型

本文根据原子识别策略的不同应用场景将其分为两类。其中，3.1节与3.2节所涉及策略对应稀疏度已知的应用场景，本文称其为直接原子识别策略；3.3节所介绍的策略对应稀疏度未知的应用场景，本文称其为原子个数识别策略。

3.1 一步式原子识别策略

此类策略可以将选中的索引直接并入最终索引集，也可以作为后续原子识别的中间媒介。

3.1.1 内积原则选取策略

内积原则选取策略依据感知矩阵A的列向量与残差r的内积绝对值大小选择原子，根据St=arg max(|〈A,rt-1〉|)从内积绝对值中选择最大元素对应的一个索引并入最终支撑集，这里称为内积原则，它是所有贪婪算法的起点。此外，为了进一步加快算法收敛速度，可以通过内积原则并行选择出前L个内积绝对值较大元素对应的原子并入最终支撑集以减少迭代次数。用到该策略的贪婪类算法有很多，区别在于不同算法对于L值大小的要求是不同的，例如：OMP[5,33-35]要求L=1，gOMP[8]要求1≤L ＜min{K,M/K}，POMP[21-23]要求其满足1≤L ≤K，CoSaMP[20,36]要求L=2K，而SP[23,24]要求L=K。为方便在本文后续的其他策略中调用此原则，将其记为式(5)中的函数supp_max_L

3.1.2 弱选择策略

原子的弱选择策略以当前迭代过程中最大内积绝对值的ρ倍为判断标准，将内积绝对值中大于该标准的原子选择出来，其中，0＜ρ ＜1[11]，其形式如式(6)所示

该操作将其他原子对应的内积绝对值与最大的内积绝对值在大小关系上联系起来。由于最大内积绝对值在每次的迭代过程中是动态变化的，使得算法每次选取索引的个数也保持动态变化。

3.1.3 阈值分段选择策略

阈值分段选择策略的核心思想是通过设定一个动态更新的阈值作为原子的选择标准来并行地更新最终索引集，可用式(7)表示

其中，Pt=〈A,rt-1〉表示感知矩阵和残差的内积，tht为预先设定的阈值参数。σt表示形式噪声水平。由于残差在每一次的迭代过程中是动态变化的，所以即便阈值参数 tht是一个固定值，阈值t htσt仍然可以保持动态变化。阈值分段选择策略在每次迭代过程中可以实现多个原子的并行选择，但阈值参数针对高斯矩阵只有经验值，一般为 tht ∈[2,3]，且还没有充分的理论推导确保该范围的精准性。实际应用中需要根据实际情况进行选取。

3.2 进阶式原子识别

进阶式原子识别策略是在选择出潜在支撑集或候选支撑集的基础上进一步精确挑选原子，以此提高算法的重构准确度。

3.2.1 模糊阈值策略

模糊阈值策略的核心思想是通过设定一个动态变化的阈值，将标准之外的原子剔除掉，以此减少在后续求解最小二乘问题中的计算负担。阈值的大小在每次迭代过程中与内积相关，其浮动设定保证了原子选择的准确性。其伪代码如算法1所示。

算法1 模糊阈值策略[37]

在阈值的设定标准中，α=P2/P1， 其中P1,P2代表每次迭代过程中内积向量P降序排列后前2个元素值。τ表示阈值，其理想范围为τ∈[0.3,0.5]。缩减过程中，该策略只保留潜在支撑集中内积值大于阈值标准的原子。模糊阈值策略可以被应用于潜在支撑集原子数目过多的情况，Λt作为输出表示潜在支撑集中满足阈值标准的原子集合。

3.2.2 部分最小二乘投影策略[38]

部分最小二乘投影策略的核心思想是将投影值作为原子选择的判断标准。通过比较投影值的大小，将最大的投影值所对应的原子作为当前迭代过程选中的结果，其过程如式(8)所示

3.2.3 增量最小二乘投影回溯策略

索引集原子逐渐增加的算法在执行前期找到的索引大概率是正确的，但随着迭代次数增加，执行后期找到正确索引的概率越来越小。增量最小二乘投影回溯策略的核心思想是通过回溯的手段，在算法的执行后期将原子增补方式改为每2次迭代新增1个原子，以提高原子选择的准确度。其伪代码如算法2所示。

算法2 增量最小二乘投影回溯策略[41]

增量最小二乘投影回溯策略中， T R表示开始标志，即为算法执行前期与执行后期的分界线，且TR＜K。在迭代次数大于开始标志后，该策略每两次迭代回溯1次，即增加2个索引后再通过回溯剔除掉1个，剔除的标准以投影值的大小为依据。

此外，与此类似的原子识别方法还有最小二乘投影阈值回溯策略[39,40]，该策略将模糊阈值策略与投影回溯策略有机融合，其核心思想是在得到投影向量以后，通过设定一个动态变化的投影值标准作为原子的选择依据，将不满足此标准的原子全部剔除掉，以此提高算法的重构精度，且该策略适用于稀疏度不先验的情况。

3.2.4 基于投影的原子选择策略

基于投影的原子选择策略的核心思想是以投影值作为原子选择标准，将投影值较大的原子所对应的索引并入最终支撑集。其伪代码如算法3所示。

算法3 基于投影的原子选择策略[17]

基于投影的原子选择策略将潜在支撑集Ct并入上一次迭代后得到的最终索引集It-1，组成候选支撑集St，并求出其投影值向量。其次，将潜在支撑集Ct之外的索引所对应的投影值置0，则本次迭代过程中选中的结果为处理后的投影值中较大的L个值所对应的索引。文献[17]中L的取值大于1，表示每次迭代并行选择出多个原子，但是选择出来的原子会被后续操作处理，最后从L个原子中选择出1个最相关的原子。

3.2.5 压缩采样原子选择策略

压缩采样原子选择策略在每次迭代过程中通过内积原则选择 2K个原子并入最终索引集，而后通过比较投影系数的大小，回溯掉K个投影系数较小值对应的原子。压缩采样原子选择策略的核心思想是采用并行原子选择的方式使算法运行得更快，而其回溯手段使算法在重构精度方面也得到了保证。压缩采样原子选择策略的伪代码如算法4所示。

算法4 压缩采样原子选择策略

此外，子空间追踪算法[23,24]采取的原子选择策略与压缩采样原子选择策略类似，核心本质均是采用并行原子选择以减少迭代次数，再通过回溯手段提高重构成功率。二者的区别在于，子空间追踪原子选择策略每次迭代过程中通过内积原则选择K个原子，而不再是 2K个。其次，子空间追踪原子选择策略在更新残差时需要重新计算投影系数，即每次迭代过程中需要求解两次最小二乘问题。

3.2.6 展望策略

展望策略的核心思想在于它的原子选择标准不仅取决于内积绝对值的大小，还取决这些原子将来对最小化最终残差的影响能力。通过选择能够最小化最终残差的一组索引作为最终支撑集，展望策略在同类算法中的重构准确度首屈一指。其伪代码如算法5所示。

算法5 展望策略[17,29]

展望策略相当于已知部分支撑集的OMP算法，对于潜在索引i，在其并入最终支撑集后，该策略每次迭代从内积中选择一个相关性最大的原子索引，直到满足迭代停止的判断条件，并评估该原子在迭代过程中对最小化最终残差影响能力的大小。因此，在给定稀疏度K、最终支撑集It-1和潜在索引i的情况下，算法可以在最后找到包含K个元素的最终支撑集，并返回最终残差。该策略可被记为式(9)

3.2.7 并行展望策略

并行展望策略以展望策略为基础，其核心思想在于每次迭代过程中并行选取原子以减少迭代次数。并行展望策略的伪代码如算法6所示。

算法6 并行展望策略[30]

并行展望策略在迭代过程中需要输出相应的索引集Λj，当确定支撑集选取对象后，将该索引集Λt与 潜在支撑集Ct的 交集中所包含的索引集Γt并入最终支撑集中完成并行选取。

3.2.8 正交最小二乘一步展望策略

正交最小二乘一步展望策略与展望策略的核心思想类似，不同之处在于前者以待选原子在当前迭代过程中最小化残差的能力大小为标准来选择原子，即正交最小二乘一步展望策略侧重于当前迭代过程对下一个原子选择的影响，而展望策略侧重于当前迭代过程对最终结果的影响。其伪代码如算法7所示。

算法7 正交最小二乘一步展望策略[17]

在文献[17]中，OLS算法调用该策略的形式可称为剩余支撑集遍历策略，如式(10)所示

剩余支撑集遍历策略调用正交最小二乘一步展望策略，遍历了所有未被选入最终支撑集的索引，即将每个索引放入最终索引集后，计算其残差l2范数，最后将残差l2范数最小值所对应的索引选择出来。剩余支撑集遍历策略的计算量非常大，适合对长度较短的稀疏信号进行恢复。

3.3 稀疏度自适应策略

本节所介绍的内容与直接原子识别策略不同。当稀疏度未知时，需要通过自适应策略得出信号稀疏度的估计数值。稀疏度的估计值决定了原子识别过程所选取的原子个数。将稀疏度自适应的过程称为原子个数识别。在稀疏度未知的情况下，对稀疏度的准确估计能够保证重构信号的精度。

3.3.1 固定步长稀疏度自适应策略

固定步长稀疏度自适应策略的核心思想是设定一个固定步长s作为步进标准，并以残差为判断依据匹配稀疏度的具体数值。其伪代码如算法8所示。

算法8 固定步长稀疏度自适应策略[12,26]

固定步长稀疏度自适应策略中的步长s(1≤s≤K)是一个在迭代过程中不会发生改变的固定值。该策略以当前迭代过程中得到的残差与上一次迭代后得到的残差的能量大小作为支撑集长度是否更新的依据。策略执行过程中若不满足停止条件，则说明支撑集里的索引还没有找全面，需要继续计算。若当前残差的能量比上一次迭代后得到的残差能量大，说明当前支撑集长度较短，则保持步长不变，增加状态数使支撑集的长度增加。若残差的能量减小，说明当前支撑集长度合适，但是需要继续迭代淘汰错误的原子。固定步长稀疏度自适应策略的估计精度往往和步长s的设置有关。s越小，估计的准确度越高，但需要迭代的次数就会越多。

3.3.2 变步长稀疏度自适应策略

变步长稀疏度自适应策略的核心思想是在迭代初期选择大步长快速逼近真实稀疏度，后续迭代过程中步长逐渐缩小，慢速逼近真实稀疏度，以此避免算法对稀疏度产生过估计或欠估计的问题。变步长稀疏度自适应策略主要有3种估计稀疏度的方法：运用相邻阶段估计信号的能量差，运用测量值向量与估计信号能量的比值自适应调节步长，根据残差能量的阶段大小自适应调节步长。其伪代码如算法9所示。

算法9 两阈值变步长稀疏度自适应策略[16]

两阈值变步长稀疏度自适应策略引进了两个阈值ε1,ε2(ε1＞ε2)以控制步长变换和算法的终止迭代。ε1越 接近ε2，其执行效率越高，但精度越低。因此，综合效率与精度的要求，每次的步长变化取上一次迭代时步长的1/2。当支撑集长度未达到稀疏度K时，相邻两个阶段中重建信号的能量差是不断减小的，并且此能量差下降速度随着阶段数的增加而逐渐变缓，最终趋于稳定。

3.3.3 基于能量的变步长稀疏度自适应策略

基于能量的变步长稀疏度自适应策略的核心思想是以测量向量与估计信号能量的比值为依据自适应地调整步长。其伪代码如算法10所示。

此基础建立在约束等距条件之上，为了提高稀疏度估计值的准确度，往往将判断标准值ρ设置得比1.307大。在该策略小步长变换的步骤中(如算法10中(1), (2)所示)，不同文章的方法各有不同。文献[15]采用支撑集长度每次增加原始步长1/2的方式更新步长；文献[42]采用的策略是支撑集长度每次减半增加的方式更新步长。文献[15]没有摆脱会产生过估计或欠估计的弊端，但可以使算法快速收敛；文献[42]中步长动态更新减半的方法更为精确，但是需要更长的时间完成收敛。

算法10 基于能量的变步长稀疏度自适应策略[12,33]

3.4 重构性能结果分析

为了直观地比较各原子识别策略的重构性能，本文将每种策略所对应的原始算法在相同的实验设置与硬件条件下进行了仿真对比。原始信号x为 随机生成的高斯信号；感知矩阵A的参数选择为M=32, N=128；稀疏度的仿真范围为1～20，每个稀疏度下的重复实验次数为1000次。所有的实验均在运行于macOS big Sur 11.6操作系统、8GB RAM和Apple M1的MATLAB R2020b上实现。

第1组实验比较了直接选取策略以及进阶式原子识别策略所对应的原始算法的重构成功率与迭代次数。其中，重构成功率的定义采用了平均支撑集基数误差，它用于测量恢复算法得到的估计支持集与原始信号的实际支持集间的平均误差，其定义为

其中，I表示实际支持集，Iˆ表示估计支持集。在参数设置中，阈值分段选择策略中的阈值参数ts设置为10；弱选择策略中的阈值参数ρ设置为0.75。

原子识别策略原始算法重构性能对比结果如图2所示。图2(a)为重构成功率的仿真结果，图2(b)为迭代次数的仿真结果。由图2(a)可得如下结论：

(1)采用正交最小二乘投影回溯策略的BAOMP在投影的基础上利用回溯的手段而获得了最优秀的恢复效果。采用投影原子选择策略的POMP、采用部分最小二乘投影策略的OMP-LS以及采用展望类策略的LAOMP, BLAOMP与OLS同样以高额计算量为基础获得了良好的恢复成功率。其中，LAOMP的重构成功率最高，但其计算量与其他算法相比较高；BLAOMP采用并行选取手段在恢复精度上虽不如LAOMP，但极大地缩减了迭代次数；POMP在重构精度上略低于LAOMP，而由于在迭代过程中仅需比较投影系数值大小而不需要比较残差值，其计算量远小于LAOMP；OLS的重构精度同样低于LAOMP，因其在每一次迭代过程中需要遍历所有剩余原子，该算法的计算负担较高。

(2)阈值类策略的重构精度因阈值设定方式的不同而略有差别。其中，采用弱选择策略的SWOMP算法通过多原子选取方式并行更新投影系数，其恢复效果比OMP更加具有优势；采用阈值分段选择策略的StOMP与采用模糊阈值策略的Fuzzy-OMP因其更简单的计算复杂度牺牲了部分恢复精度。

(3)与采用压缩采样原子选择策略的CoSaMP算法相比，采用子空间追踪原子选择策略的SP算法在更新残差时多求解一步最小二乘问题，这使得后者的重构精度略高于前者。

迭代次数的仿真结果如图2(b)所示。采用并行原子选择方式的StOMP, Fuzzy-OMP, SWOMP以及BLAOMP算法均在6～8次迭代内收敛； BAOMP与GOMP使迭代次数相比于稀疏度量级降低了1～2次； CoSaMP以及SP算法均在5次迭代左右收敛，其中，前者的迭代次数略低于后者1～2次。此外，采用串行原子选取方式的OMP, POMP, LAOMP以及OLS算法，其迭代次数与稀疏度量级保持一致。

图2 原子识别策略原始算法重构性能对比结果

第2组实验比较了稀疏度自适应策略类算法的重构性能。在参数选择中，步长统一设定为S=6。变步长稀疏度自适应策略中的阈值参数ε1,ε2分别设定为2和0.001；基于能量的变步长稀疏度自适应策略中能量阈值参数ρ设定为2，支撑集长度的更新方式采用了文献[15]所提出的策略。

稀疏度自适应策略类算法重构成功率结果如图3(a)所示。3种原子个数识别策略的重构成功率趋同。其中，采用基于能量的变步长稀疏度自适应策略的e-SAMP算法因其在变步长的基础上以能量作为更新步长的依据，其重构成功率最高；采用固定步长稀疏度自适应策略的SAMP算法由于更新步长时的局限性，其恢复精度最低。

稀疏度自适应策略类算法迭代次数结果如图3(b)所示。其中，采用基于能量的变步长稀疏度自适应策略的e-SAMP需要更多的迭代次数完成收敛； 采用变步长稀疏度自适应策略的MSAMP利用更精确的步长更新方式，使其恢复精度高于采用固定步长稀疏度自适应策略的SAMP，同时前者的迭代次数略高于后者。

图3 稀疏度自适应策略类算法重构性能对比结果

4 结论

本文以贪婪类算法的原子识别策略为研究对象，对贪婪类重构算法的原子识别策略进行了归纳与总结，着重综述了算法在不同处理阶段可以运用的原子识别策略，并对其所对应原始算法的重构性能进行了分类仿真对比。在该综述的基础上，稀疏信号压缩感知模型的重构算法创新更加便于实现，综述中的原子识别策略也可以被拓展到联合稀疏信号压缩感知模型[43]以及块稀疏信号压缩感知模型的信号恢复算法中，从而实现跨模型算法的创新。