用于自回归噪声下信号检测的基于动态规划的高效稀疏采样方法

《Signal Processing》：Efficient Sparse Sampling using Dynamic Programming for Signal Detection Under Autoregressive Noise

　　扎伊娜·L·卡拉乌恩|考沙利亚·阿迪卡里|史蒂文·凯重点内容：•详细推导了嵌入有色高斯噪声中的确定性信号的另一种偏转系数表达式。•构建了一个可应用于任意AR(p)过程的广义动态规划框架。•给出了在不同自回归噪声模型下该替代偏转系数的示例，以及广义动态规划的示例。1. 引言在大数据时代，人们越来越关注寻找替代性的采样方法，以降低高计算强度、大内存需求以及整体硬件能耗[1]、[2]。自1915年香农-尼奎斯特采样理论提出以来，它一直被用于信号采样[3]、[4]。然而，为了降低计算复杂度、减少硬件成本或提升处理速度，人们开始探索低于尼奎斯特速率的采样方式，即稀疏采样。现有的稀疏采样方法包括压缩采样、广义采样、互质采样、嵌套采样以及移位不变稀疏阵列采样等多种形式[1]、[5]、[6]、[7]、[8]。关于如何从原始数据集中选择合适的样本子集（或稀疏样本），目前存在诸多争议。这类争议在检测问题中尤为突出——我们需要确保从原始数据集中选取的样本子集能够实现最佳的检测性能。本研究聚焦于在高斯噪声中检测已知信号的问题。众所周知，在这种情况下，检测器的性能指标就是偏转系数；较低的偏转系数意味着较差的检测性能，而较高的偏转系数则代表更优的检测效果[9]。因此，要提升此类场景下的检测性能，就需要尽可能提高偏转系数[2]、[9]、[10]、[11]、[12]。理想情况下，用于检测的稀疏样本选择应通过直接最大化偏转系数来实现。但由于偏转系数属于非凸函数，直接优化会带来极大的计算难度。因此，现有方法通常采用两种路径之一：第一种是用其他替代性标准取代原有目标函数，但这些标准的最优性仅能在极限情况下成立（即当N→∞时）[13]、[14]；第二种则是使用一些更易于优化的替代目标函数，但这些函数与由偏转系数衡量的实际检测性能之间仅存在弱关联。常见的替代度量指标包括库尔贝克-莱布勒散度、切尔诺夫距离、I散度、J散度以及巴塔查里亚距离[11]、[13]、[14]、[15]、[16]、[17]、[18]、[19]、[20]。例如，[19]通过最大化I散度、J散度、巴塔查里亚距离和切尔诺夫距离来设计稀疏采样模式，而[15]则以库尔贝克-莱布勒散度和切尔诺夫距离作为优化准则，并证明了相应问题的复杂性为NP难问题。尽管[15]提出了样本选择算法，但所得解相对于原始检测目标而言并非最优。类似地，[11]、[16]、[17]中的方法则在次模优化框架下，将库尔贝克-莱布勒散度和巴塔查里亚距离作为高斯观测值的优化准则。因此，[11]、[13]、[14]、[15]、[16]、[17]、[18]、[19]、[20]中的方法并未直接优化偏转系数，因而通常无法达到真正的检测目标最优解。与现有方法不同，我们的工作通过直接最大化偏转系数，为稀疏样本选择问题提供了精确解。该问题的主要难点在于其组合特性：从N个总样本中选择M个稀疏样本，需要遍历所有可能的子集，其数量为N!M!(N?M)!。虽然对于小规模问题，穷举法或许可行，但在实际应用中，可能的配置数量很快就会变得难以处理。例如，当N=50且M=25时，候选子集的总数超过了1.26×101?，使得暴力优化在计算上几乎不可行。此外，评估每个候选子集通常都需要计算偏转系数，而这涉及矩阵求逆操作，进一步增加了计算负担。为解决这一难题，我们推导出了偏转系数的另一种表达形式，该形式便于通过动态规划进行优化。这一重构使得我们能够在避免枚举所有可能子集的情况下，高效地探索组合搜索空间。因此，所提出的方法能够精确找到使偏转系数最大化的全局最优稀疏采样模式，无需依赖渐进近似、替代目标函数或贪心策略。这样一来，我们的方法为检测问题中的稀疏样本选择提供了非渐进式的最优性保证。该方法基于将噪声建模为p阶自回归高斯过程。实际上这一假设并不具有限制性，因为只要p值足够大，AR(p)模型就能够以任意期望功率谱密度的高精度近似随机过程[2]、[12]、[21]。与现有的稀疏采样方法相比，所提出的方法具有以下几项重要优势：•该方法提供了完全解析的解决方案，无需依赖迭代优化流程或启发式搜索技术。•由此得到的稀疏采样方案能够确保精确最大化偏转系数，因而可以给出全局最优的精确解，而非基于替代目标函数或渐进准则的近似解。•通过结合所提出的偏转系数重构形式与动态规划技术，该算法的计算复杂度仅与M和N呈线性关系，因此即便面对大规模问题也能保持较高的计算效率。本研究的具体贡献可总结如下：1. 我们推导出了更便于优化的偏转系数表达形式。2. 我们构建了基于动态规划的框架，该框架能够精确最大化偏转系数，并得出解析意义上的最优稀疏采样方案。3. 我们将所提出的基于动态规划的稀疏采样方法的检测性能与现有的解析型稀疏采样方法进行了对比。本文的其余结构如下：第2节介绍了本文所考虑的信号模型及相关假设的基本描述；第3节阐述了创新框架并推导出了替代偏转系数；第4节给出了如何运用该替代偏转系数的示例；第5节建立了动态规划框架，第6节则展示了如何使用我们所推导出的动态规划表达式；第7节是对我们方法的数值模拟分析，最后是结论部分。2. 信号模型、假设与问题描述我们考虑以下离散时间二进制假设问题：已知确定性信号嵌入加性噪声中，问题形式如下：(1)H0：x[n]=w[n] H1：x[n]=s[n]+w[n]，其中n=1,2,?,N。这里H0和H1分别代表零假设和备择假设，w[n]被视为零均值有色高斯噪声，可建模为满足p阶差分方程的AR(p)过程：w[n]=∑i=1p(?a[i])w[n?i]+u[n]，其中u[n]为方差为σu2、均值为0的白高斯噪声。我们也可以将w[n]表示为一阶向量差分方程的形式：(2)w[n]=Aw[n?1]+u[n]，其中n=1,2,?,N。由此可知，(1)也可以用向量形式表示为：(3)H0：x[n]=w[n] H1：x[n]=s[n]+w[n]，其中n=1,2,?,N。这里的A是一个非奇异的p×p矩阵，其表达式为：(4)A=[0 1 0 ? 0 0 0 1 ? 0 ? ? ? ? 0 0 0 ? 1 ?a[p] ?a[p?1] ?a[p?2] ? ?a[1]]。需要注意的是，(2)可以改写为：(5)[w[n?p+1] w[n?p+2] ? w[n?1] w[n]]=A[w[n?p] w[n?p+1] ? w[n?2] w[n?1]]+[0 0 ? 0 u[n]]，而(3)也会呈现类似的结构，即：(6)s[n]=[s[n?p+1] s[n?p+2] ? s[n?1] s[n]]。我们将二进制假设检测问题转化为向量形式，是为了利用其结构特性。具体而言，将假设检验转换为状态空间形式后，能够明确体现时间依赖性，同时体现出AR(p)过程所固有的马尔可夫结构。在下一节中我们将展示，可以通过以下方式分离出状态空间模型的最后一行：(7)hT=[0 1 ×(p?1) 1]，这样我们就可以将状态向量映射回我们感兴趣的实际标量测量值，即x[n]=hTx[n]。通过这种表述方式，我们将利用(3)的结构为(1)推导出另一种偏转系数表达形式，使得该替代偏转系数能够以递归形式呈现，从而便于应用动态规划技术。为此，我们在整个研究过程中会做出若干假设，具体如下：1. 噪声过程w[n]（以及等价的w[n]）被假设为宽平稳过程。这一假设的优势在于能够确保存在稳态协方差矩阵，进而使得创新项的表达式可以以封闭形式得到[21]、[22]。宽平稳假设的优势将在第3节和第4节中进一步阐述。2. 对于稀疏采样模式，我们从N个尼奎斯特速率观测值中选择M个样本，同时需满足以下排序约束：(8)1≤n1< />< />因此，y[n1]和y[nm]的期望值分别表示为(29)μ1=E{y[n1]}=s[n1]，以及(30)μm=E{y[nm]}=s[nm]?Anm?nm?1s[nm?1]，其中2≤m≤M。所以在假设H1下，y[nm]的概率密度函数为(31)y[nm]～{N(μ1,∑k=0∞AkQ(Ak)T) form=1/N(μm,∑k=0nm?nm?1?1AkQ(Ak)T)，其中2≤m≤M。这样，我们就可以将二进制检测问题转化为基于这些不相关创新样本的问题，将其记为ym。即(32)H0:ym～N(0,Cm) form=1,2,?,M H1:ym～N(μm,Cm) form=1,2,?,M，此处ym的协方差矩阵记为Cm，均值记为μm，m=1,2,?,M。注意，我们可以将所有的ym组合成一个大型向量，即(33)ξ=[y1y2?yM]，其维度为dim(ξ)=pM×1；我们使用ξ来区分它与ym。此时ξ的协方差矩阵可表示为(34)C=E{ξξT}，由于这些创新向量是不相关的，因此有(35)C=[C100?00C20?000C3?0?????000?Cm]，这是一个块对角形式的协方差矩阵。3.3 替代偏转系数的评估通过将Neyman-Pearson（NP）检测定理应用于(32)，我们可以得到任意p值时替代偏转系数的解析表达式。我们发现，当似然比超过阈值γ时，NP检测器会判定H1成立，即(36)l(ξ)=lnp(ξ;H1)p(ξ;H0)=ξTC?1μ>lnγ+12μTC?1μ。因此，当(37)T(ξ)=ξTC?1μ>γ′时，NP检测器会判定H1成立。需注意，T(ξ)代表我们的检验统计量，同时也是最优检测器。利用(37)和(38)d2=(E{T(ξ);H1)}?E{T(ξ);H0)})2var(T(ξ);H0)，偏转系数可表示为(39)d2=μTC?1μ。随后我们可以将这个表达式转化为另一种形式，称之为替代偏转系数，其表达式为(40)dd2=∑m=1MμmTCm?1μm，其中如附录A所示，Cm的表达式为(41)Cm=R[0]?Anm?nm?1R[0](Anm?nm?1)T。接着，我们通过将(7)与创新样本相乘，得到(1)对应的dd2表达式，即(42)z[n1]=hTy[n1]=hTx[n1]z[n2]=hTy[n2]=hT(x[n2]?An2?n1x[n1])z[n3]=hTy[n3]=hT(x[n3]?An3?n2x[n2])?z[nM]=hTy[nM]=hT(x[nM]?AnM?nM?1x[nM?1])，此时z[n1],z[n2],?,z[nM]均为(1)中的创新样本（或不相关的标量样本）。因此，通过将(7)与(32)中的向量相乘，我们就将(32)转化为了基于标量的二元假设问题，即(43)H0:z[nm]～N(0,hTCmh) for 1≤m≤M H1:z[nm]～N(hTμm,hTCmh) for 1≤m≤M。将NP检测器应用于(43)后，我们发现当似然比超过阈值γ时，NP检测器会判定H1成立，即(44)l(z)=lnp(z[nm];H1)p(z[nm];H0)=∑m=1Mz[nm]hTμmhTCmh?μmThhTμm2(hTCmh)>lnγ″，这实际上等同于(45)T(z[nm])=∑m=1Mz[nm]hTμm>γ″′。进而，通过将(38)应用于(45)，可以得到替代偏转系数dd2的表达式，即(46)dd2=∑m=1MμmThhTμmhTCmh=∑m=1M[μm]p2var(z[nm])，此处下标p表示所采用的AR(p)模型的阶数。因此，(46)就是我们针对原始问题(1)所寻求的替代偏转系数。接下来我们将通过示例展示如何运用(46)。4. 示例：AR(1)和AR(2)噪声的创新值、统计矩及替代偏转系数本节阐述如何借助基于创新的框架，通过两个案例获得替代偏转系数：将w[n]建模为AR(1)模型和AR(2)模型。这些示例具有双重作用：其一，展示了随着自回归模型阶数的变化，创新值、其统计矩以及替代偏转系数的通用表达式是如何简化的；其二，阐明了AR过程所假设的阶数如何直接决定偏转系数的依赖结构，而这又决定了第6节中动态规划递归的结构。需要注意的是，第一个示例的结果与[2]中所呈现的一致。4.1 示例1 AR(1)：创新值、统计矩及封闭形式偏转系数采用与(1)相同的问题的表述，我们将w[n]建模为AR(1)过程，其表达式为(47)w[n]=(?a[1])w[n?1]+u[n]，其中u[n]为高斯白噪声。w[n]在滞后0时刻和滞后k时刻的自相关函数分别为rww[0]=σu21?a2[1]，以及rww[k]=(?a[1])krww[0]。由于假设w[n]是AR(1)模型，因此(4)和(7)可表示为(48)A1×1=?a[1]，hT=1。接着，我们按照(42)中所示的相同方法，得到x[n]的不相关稀疏样本，并结合(48)中的关系式，得到(49)z[n1]=x[n1]z[n2]=x[n2]?(?a[1])n2?n1x[n1]?z[nM]=x[nM]?(?a[1])nM?nM?1x[nM?1]。此时，标量检验统计量可由(45)给出，应用(38)后可得(50)dd2=∑m=1M[μm]12var(z[nm])，其中[μ1]1=s[n1]，var(z[n1])=rww[0]，此外还有(51)[μm]1=s[nm]?(?a[1])nm?nm?1s[nm?1]，以及(52)var(z[nm])=rww[0]?(?a[1])2(nm?nm?1)rww[0]，适用于2?≤?m?≤?M的情况。将(51)和(52)代入(50)后，即可得到替代偏转系数的精确表达式，即(53)dd2=s2[n1]rww[0]+∑i=1M?1(s[ni+1]?(?a[1])ni+1?nis[ni])2rww[0]?(?a[1])2(ni+1?ni)rww[0]，这一表达式与[2]中的结果一致。4.2 示例2 AR(2)：创新值、统计矩及封闭形式偏转系数仍采用与之前相同的问题的表述，现在假设w[n]为AR(2)模型，其表达式为(54)w[n]=(?a[1])w[n?1]+(?a[2])w[n?2]+u[n]，其中u[n]同样为高斯白噪声。此时w[n]的自相关函数为(55)rww[k]=(?a[1])rww[k?1]+(?a[2])rww[k?2]，且(56)rww[0]=σu2(1+a[2])(1?a[2])[(1+a[2])2?a2[1]]。由于假设w[n]是AR(2)模型，因此(4)和(7)可表示为(57)A=[01?a[2]?a[1]]，hT=[01]。与AR(1)示例类似，我们通过类似的方法得到x[n]的不相关稀疏样本，此时的标量创新样本表达式为(58)z[n1]=x[n1]z[n2]=x[n2]?[An2?n1]22x[n1]z[n3]=x[n3]?[An3?n2]22x[n2]?[An3?n2]21x[n2?1]?z[nM]=x[nM]?[AnM?nM?1]22x[nM?1]?[AnM?nM?1]21x[nM?1?1]，其中AnM?nM?1中的元素是通过将AnM?nM?1化为若尔当标准形得到的（详细内容见附录B）。注意，对于z[n2]，由于只有一个之前的稀疏样本n1，所以我们设定x[n1?1]=0。接着，利用(45)给出的标量检验统计量，并应用(38)，可得(59)dd2=∑m=1M[μm]22var(z[nm])，此时[μ1]2=s[n1]，[μ2]2=s[n2]?[An2?n1]22s[n1]，此外还有(60)[μm]2=s[nm]?[Anm?nm?1]22s[nm?1]?[Anm?nm?1]21s[nm?1?1]，适用于3?≤?m?≤?M的情况。var(z[nm])的表达式则为(61)var(z[n1])=rww[0]，var(z[n2])=rww[0]?[An2?n1]222rww[0]?，而var(z[nm])对于3?≤?m?≤?M的表达式为var(z[nm])=rww[0]?[Anm?nm?1]212rww[0]?[Anm?nm?1]222rww[0]?2[Anm?nm?1]21[Anm?nm?1]22rww[1]，其中rww[1]=?a[1]1+a[2]rww[0]。注意(61)可通过(41)得到。将(60)和(61)代入(59)后，即可得到替代偏转系数(62)dd2=s2[n1]rww[0]+(s[n2]?[An2?n1]22s[n1])2rww[0]?[An2?n1]22rww[0]+∑i=1M?2(s[ni+2]?[Ani+2?ni+1]22s[ni+1]?[Ani+2?ni+1]21s[ni+1?1])2(rww[0]?[Ani+2?ni+1]212rww[0]?[Ani+2?ni+1]222rww[0]?2[Ani+2?ni+1]21[Ani+2?ni+1]22rww[1])。通过观察(62)可以发现，dd2的前两项与AR(1)假设下的表达式相似，这是因为我们的噪声模型具有特定的结构。因此，无论w[n]采用何种噪声模型，由于高斯白噪声的特性，dd2的前p项都会保持一致。5. 动态规划通过(53)和(62)所示的形式表达偏转系数，可以看出这两种形式都具有独特的结构。由于创新值将依赖结构限制在最多p个之前的样本上，偏转系数具有马尔可夫特性，这使其非常适合用动态规划来处理。首先，我们来看(53)的结构。通过观察可知，(53)中求和项的每一项计算都需要涉及两个连续的样本，即s[ni+1]和s[ni]。显然，(53)中的这些项是相互关联的，因此无法单独计算其中一个。再来看(62)，其前两项结构与(53)类似，但(62)的求和涉及三个连续样本的计算，即s[ni+2]、s[ni+1]和s[ni+1?1]。与之前类似，这三个样本也是相互关联的，计算其中一个都需要先知道另外两个的值。这种特性源于AR(p)过程的马尔可夫性质，也正是由于这一特性，dd2的计算非常适合用动态规划来完成。其主要优势在于，寻找最优稀疏样本的计算时间不再是随M呈指数增长，而是变为线性增长。接下来我们将通过推导通用动态规划表达式，展示如何将(46)用动态规划形式表示出来。5.1 推导通用动态规划表达式为了在稀疏样本集合n1,n2,?,nM上最大化(46)，我们将其重写为一个函数形式，即(63)J(n1,n2,?,nM)=g(0,0,?,0,n1)+g(0,?,0,n1,n2)+?+g(0,n1,?,np?1,np)+g(n1,n2,?,np,np+1)+g(n2,n3,?,np+1,np+2)+?+g(nM?p,nM?(p?1),?,nM?1,nM)，其中g(0,0,?,0,n1)=[μ1]p2var(z[n1])，g(0,?,0,n1,n2)=[μ2]p2var(z[n2])，?，g(nM?p,nM?(p?1),?,nM?1,nM)=[μM]p2var(z[nM])。随后我们将(63)改写为(64)J(n1,n2,?,nM)=g(0,0,?,0,n1)+g(0,?,0,n1,n2)+?+g(0,n1,n2,?,np)+∑i=1M?(p+1)g(ni,ni+1,?,ni+p?1,ni+p)+g(nM?p,nM?(p?1),?,nM?1,nM)，该表达式可视为以下最大化问题(65)IM?p(nM?(p?1),nM?(p?2),?,nM)=maxn1,n2,?,nM?p1≤n1< />< />我们以类似的方式继续处理I3(n3,n4)、I4(n4,n5)、?、IM?2(nM?1,nM)，其中每次迭代中各个稀疏样本的可能取值分别为：3≤n3≤(N?M)+3，4≤n4≤(N?M)+4，4≤n4≤(N?M)+4且5≤n5≤(N?M)+5，?，M≤nM≤N。最后，通过回溯算法对这些迭代进行处理，从而分别得到nM*、nM?1*、?、n1*。我们首先求解maxnM?1,nMIM?2(nM?1,nM)，由此得到nM?1*和nM*，接着通过解(79){nM?2*,nM?1*}=maxnM?2IM?3(nM?2,nM?1*)来找到nM?2*。随后通过依次最大化IM?3(nM?3,nM?2*)、IM?4(nM?4,nM?3*)、?、I1(n2,n3*)、I0(n1,n2*)，重复类似步骤得到nM?3*、nM?4*、?、n2*、n1*。如之前的动态规划示例所示，我们再考虑如下示例信号(80)J(n1,n2,n3,n4,n5)=sinπ6n1+sinπ6(n2?n1)+sinπ6(n3?n2?n1)+sinπ6(n4?n3?n2)+sinπ6(n5?n4?n3)，其中(84)的设计思路与(62)类似。我们利用(81)来计算(84)，并通过回溯算法得到最优稀疏样本集。我们可以通过三维格状结构来可视化动态规划和回溯过程，如图2所示。从图2中可以看出所有能使dd2达到最大值的潜在路径，其中最优路径以绿色标出。此时回溯不再是一维的，而是要在二维空间中寻找能够同时向两个方向移动的稀疏样本。如果一个样本只能朝一个方向移动而无法朝另一个方向移动，那么它就无法成为最优路径，因为它无法达到dd2的最大值。此时，稀疏样本必须在二维空间中共享一条潜在路径，这一路径与我们假设的AR(2)过程的顺序相对应（见图2）。对于(84)，最优稀疏样本集被确定为ni*={2,4,8,9,10}。

下载：下载高分辨率图像（547KB）
下载：下载全尺寸图像

图2. 在求解(81)时用于回溯的三维格状结构。可见，回溯需要在nM?1和nM两个方向上寻找最优样本。

7. 仿真实验
7.1 正弦信号的检测
考虑正弦信号s[n]=sin(2πf0n)，其中n=1,2,?,N。我们采用与[2]中讨论和展示的类似仿真流程，不过这里将w[n]建模为AR(2)过程。首先设定f0=0.05，a[1]=?0.65，a[2]=0.10，从N=50个样本中选择M=25个作为稀疏样本，通过动态规划得到的这些样本如图3所示。接着我们改变s[n]的频率分量，范围为f0=0.0025≤f≤0.0050，同时固定N的值并改变M的值。这些参数变化对检测性能的影响如图4所示。我们还会按照[2]中的方法进行更多仿真，以此作为对比指标，研究当p=2时检测性能的变化情况。观察图4可以发现，与[2]中的类似结果相比，当f0=0.30且M=10时，检测性能的下降幅度更大。由于w[n]被建模为AR(2)过程，这些样本会依赖于之前的2个样本。因此，当我们从N个样本中只选择较少的M个样本，比如M=10时，AR(2)模型可能无法充分了解这2个先前样本之间的相关性[21]。换句话说，我们可以选择的最佳样本数量相对有限。对于更高阶的AR(p)模型，也会出现类似的情况。

下载：下载高分辨率图像（96KB）
下载：下载全尺寸图像

图3. 在假设为AR(2)结构的彩色高斯噪声中，用于检测正弦信号的最佳M=25个样本，共从N=50个样本中选取。

下载：下载高分辨率图像（132KB）
下载：下载全尺寸图像

图4. 当从N=50个样本中选择不同数量的M个样本时，f0对应的检测性能变化情况。

7.2 与穷举（暴力）搜索的比较
我们可以将动态规划方法与穷举搜索方法进行比较，后者使用公式(81)d2=μTC?1μ，其原理是期望在得到相同稀疏样本的情况下，d2和dd2具有同等意义。首先考虑一个规模较小的问题，即N=10，M=5，假设的确定性信号与前一节相同，f0=0.05。我们先用(85)进行穷举搜索，再使用动态规划进行相同搜索，最终得到如表1所示的结果。之后我们将问题规模扩大到N=25，仍希望选出最佳的M=15个稀疏样本，此时仍假设s[n]=sin(2πf0n)且f0=0.05。我们对所有可能的3.268×106种组合再次进行穷举搜索，同时对同一问题应用动态规划。通过穷举搜索和暴力搜索得到的最优稀疏样本结果一致，均为ni*={3,4,5,6,7,8,12,13,14,15,16,17,23,24,25}，此时d2=dd2=28.9823。该数值仿真是在配备英特尔(R)酷睿(TM) i9?9900K处理器、运行频率为3.60 GHz的工作站上完成的。在该硬件条件下，穷举搜索的总计算时间为130.108973秒，而结合回溯算法的动态规划总计算时间仅为0.027844秒。

表1. 对具有前五大最大值的偏转系数值及其对应的稀疏样本配置进行穷举搜索的结果。注意，该表的第二行和第三行存在两种相同的配置。

ni* d2
3, 4, 5, 6, 7 11.8944
4,5,6,7,8 10.9441
2,3,4,5,6 10.9441
3,4,5,6,9 99.9095
4,5,6,7,10 99.6433

7.3 与其他稀疏采样方案的比较
我们简单地将我们的动态规划方法与互质采样、嵌套采样以及SISA采样这三种其他稀疏采样方案进行了比较。在[23]中，我们也进行了类似的比较，但那是针对分类问题，结果表明动态规划的性能优于这些采样方案。在这次仿真中，我们设定N=33，通过动态规划、互质采样、嵌套采样以及SISA采样方案分别选择M=20个样本子集。相应的偏转系数值如表2所示，所选的奈奎斯特样本的时间子集则显示在图5中。显然，动态规划的性能优于这三种稀疏采样方法，进一步体现了其在性能方面的优势，以及其在为检测任务提供最优样本子集方面的能力。

表2. 图5中所展示的稀疏采样配置对应的偏转系数值。这些结果表明，动态规划得到的偏转系数大于互质采样、嵌套采样或SISA采样得到的系数。

稀疏样本配置 d2 动态规划样本
27.3370 27
互质采样 14.2077
嵌套采样 10.0183
SISA采样 15.9793

下载：下载高分辨率图像（551KB）
下载：下载全尺寸图像

图5. 对嵌入在AR(2)噪声中的确定性信号所采用的几种稀疏采样策略的比较。顶部面板展示了动态规划算法得出的最优稀疏采样模式，下方面板则展示了三种常用的稀疏采样方案——互质采样、嵌套采样和SISA采样在相同信号上的应用效果。

8. 结论
本文提出了一种计算效率高且具有理论依据的框架，用于确定嵌入在由AR(p)过程建模的彩色高斯噪声中的确定性信号的最优稀疏采样方案。通过利用AR(p)模型的结构，我们构建了创新序列，将这些相关的观测值转化为相互独立的成分。这一转换使得我们能够推导出另一种偏转系数，其依赖结构仅限于最多p个先前的样本，从而形成了非常适合用于动态规划的马尔可夫形式。由此产生的动态规划算法将稀疏样本选择的组合复杂度从指数级降低到了线性级，同时依然能够保证得到全局最优解。我们通过AR(1)和AR(2)噪声的详细示例，展示了如何通过该创新框架得到另一种偏转系数的封闭形式表达式，以及动态规划递归是如何由这些表达式推导出来的。数值仿真结果表明，所提出的方法始终优于互质采样、嵌套采样和SISA等其他采样策略。未来的工作将探讨当s[n]被视为随机变量时dd2的变化情况，以及动态规划是否适用于此类场景。

CRediT作者贡献说明
Zaynah L. Kalaoun：撰写——初始稿件、验证、软件实现、实验研究、形式化分析。
Kaushallya Adhikari：撰写——审阅与编辑、验证、软件实现、方法设计、形式化分析。
Steven Kay：撰写——审阅与编辑、方法设计、概念构思。