基于低比特采样的图信号恢复方法

1.本发明涉及图信号处理技术领域，具体涉及一种基于低比特采样的图信号恢复方法。

背景技术：

2.现代信息处理不可避免地涉及由各种数据源生成的大量复杂的数据，这种复杂性来自这些数据所在网络的内在关系和结构。图作为一种强大的数学工具，提供了对这种复杂数据 (表示为图信号)的关系和结构进行有效建模的能力，这使得图信号处理(graph signalprocessing,gsp)成为一个新兴的研究领域。图信号处理的基本问题之一是从不准确和不完整的数据中重建图信号。通常，图信号是带限的，或者图信号相对于图拓扑是平滑的，即相邻节点之间的信号变化很小，利用这种空间关系，我们可以从采样数据中重建与未采样节点相关的未知数据。
3.在过去的几年里，已经有很多工作致力于从采样、带噪、丢失或损坏的测量数据中重建图信号。大多数图信号恢复算法由于使用高分辨率的模数转换器，假设量化误差忽略不计。然而，高分辨率模数转换器昂贵且耗电，这会导致高硬件成本和高功耗的信息传输、处理和存储。

技术实现要素：

4.本发明旨在研究从少量图节点上的低分辨率低比特测量数据中恢复平滑图信号的问题。在这种情况下，与高分辨率或全精度量化情况相反，包含大量化误差的可用测量不能直接用于图信号恢复。因此，我们考虑用于图信号恢复的正则化最大似然优化算法，并采用期望最大化的迭代方案来检索未量化的观测数据，该方案利用从图节点的随机子集中收集的量化观测值，有效地实现了低比特图信号恢复(mb-gsr)。仿真结果表明，与1比特采样情况相比，提高采样分辨率(每个采样2比特或者3比特)可以显著提高图信号恢复性能，同时功耗和实现成本仍远低于高分辨率情况。
5.本发明提供一种基于低比特采样的图信号恢复方法包括以下几个步骤：
6.步骤1：收集采样数据，建立信号模型；
7.步骤2：提出最大似然问题，其解提供对图信号x的估计；
8.步骤3：正则化最大似然函数；
9.步骤4：计算对数似然函数的辅助下界；
10.步骤5：采用期望最大化方案估计图信号x。
11.作为优选，步骤1中，无向连通加权图g＝(v,ε,w)，其中节点集v:＝{1,
…
,k}，边集边集权重矩阵
12.图信号是从节点集v到的映射，每个节点i∈v关联一个图信号则图信号排列成一个长度为k的向量如果x是平滑的，则相邻节点的图信号具有相似性，从节点的随机子集上获取的m《k个含有噪声的采样数据中恢复图信号x，其中 m个噪声
样本可表示为：
[0013][0014]
随机子集：
[0015][0016]
表示在n时刻被随机采样的m个节点，噪声样本ys[n]与x有关，则有
[0017]ys
[n]:＝s[n]y[n]
[0018]
其中
[0019]
y[n]＝[y1[n],y2[n],
…
,yk[n]]
t
:＝x+v[n]
[0020][0021]
表示长度为k的单位向量，该向量的第k
mn
个元素为1，其余项为0；
[0022]
v[n]:＝[v1[n],v2[n],
…
,vk[n]]
t
[0023]
定义为空间和时间上独立的零均值高斯噪声，协方差是
[0024][0025]
这里diag{x1,
…
,xk}表示生成对角矩阵，其中主对角线元素是x1,
…
,xk；
[0026]
设每个节点k∈v都配备一个随机变量发生器和量化器，在n时刻，每个随机变量发生器可以提供服从标准正态分布的随机因子ξk[n]，保证量化器的输入值具有零均值的统计特性，利用ξk[n]，量化器可以产生低分辨率低比特输出dk[n]＝q(zk[n])，k∈v；
[0027]
其中
[0028]
zk[n]＝ξk[n]yk，yk[n]:＝xk+vk[n]
[0029]
q表示按元素量化操作，定义为：
[0030]
q(z)＝γh(αh≤z＜α
h+1
)
[0031]
α1《α2《
…
《0《
…
《α
2q-2
《α
2q-1
表示2
q-1个阈值水平。
[0032]
作为优选，步骤2中，提出最大似然问题，其解使用q比特量化观测数据提供对x的估计；
[0033]
观测值可表示为：
[0034][0035]
这里，
[0036][0037][0038]
其中：
[0039]
z[n]:＝[z1[n],
…
,zk[n]]
t
[0040]
λ[n]:＝diag(ξ1[n],
…
,ξk[n])
[0041]
υ[n]:＝s[n]λ[n]v[n]
[0042]
υ[n]是零均值高斯随机向量，协方差是
[0043]
作为优选，步骤3中，通过正则化最大似然函数来恢复x：
[0044]
l(x)＝logp(ds|x)-γx
t
lx
[0045]
其中：
[0046][0047]
是衡量平滑度的正则化项，这里log(x)表示对x取对数，l是拉普拉斯矩阵，γ是平衡平滑度和数据拟合的权衡因子。
[0048]
作为优选，步骤4中，对于似然函数l(x)，利用jensen不等式的对数函数形式，使用logp(ds|x)的辅助下界：
[0049][0050]
其中《x》
p(x)
表示x对分布p(x)的期望。
[0051]
作为优选，步骤5中，采用期望最大化(em)方案，给定初始化参数em迭代在下界上执行坐标上升，则有
[0052][0053]
最大化l(x)求解参数x的最大似然估计，更新参数x。
[0054]
本发明的实质性特点在于：本发明考虑了信息传输、处理和存储的低硬件成本和低功耗的情况，使其能应用在更广泛的领域。本发明使用期望最大化方法进行参数估计，所提供的技术方案在收敛速度和估计的准确性方面均有优异的表现。
附图说明
[0055]
图1是低分辨率低比特量化信号模型；
[0056]
图2是本方法的具体实现流程图；
[0057]
图3是具有k＝200个节点的图上的信号x0；
[0058]
图4是采样率m/k分别为10％(m＝20)、30％(m＝60)、50％(m＝100)时的图信号恢复的散射图，其中(a)、(d)和(g)中未填充圆表示未采样节点；
[0059]
图5是k＝2000个节点的图上的海面温度数据集；
[0060]
图6是本方法的均方误差(mse)与采样比m/k的关系；
[0061]
图7是本方法的均方误差(mse)与信噪比snr的关系；
[0062]
图8是本方法的均方误差(mse)与观测数据的关系。
具体实施方式
[0063]
下面通过具体实施例，并结合附图，对本发明的技术方案作进一步的具体说明。
[0064]
步骤1：收集采样数据，建立信号模型；
[0065]
步骤2：提出最大似然问题，其解使用q比特量化观测数据ds提供对x的估计；
[0066]
步骤3：正则化最大似然函数，求解l(x)＝logp(ds|x)-γx
t
lx恢复x；
[0067]
步骤4：由于很难直接最大化logp(ds|x)，因此，利用jensen不等式的对数函数形式，到了logp(ds|x)的辅助下界
[0068]
步骤5：采用期望最大化(em)方案，给定初始化参数em迭代在下界上执行坐标上升，最大化求解参数x的最大似然估计，更新参数x。
[0069]
本实施例通过数值结果来评估所提出的基于低比特采样的图信号恢复方法的性能，该算法从低分辨率低比特(q＝1，2，3，4)量化观测数据中恢复平滑图信号x0。对于q＝∞的情况(即从非量化观测数据中恢复图信号)，相应的算法与基于平滑度惩罚的现有算法类似。恢复性能根据归一化均方误差(mse)进行量化：
[0070][0071]
信噪比定义为
[0072][0073]
下面描述的所有结果都是通过对采样集和噪声的100多个独立实现进行平均获得的。此外，在不失一般性的情况下，我们使用grasp工具箱在k＝200个节点的图上生成信号x0，如附图3所示。
[0074]
在系数γ＝0.9，snr＝20db，量化/非量化观测数据t＝800的情况下，考虑采样率m/k分别为 10％、30％和50％的三种情况，即在200个节点中分别采样m＝20、60和100个节点，比较 2比特和∞比特gsr算法的恢复性能。结果如附图4所示，并显示：随着采样率m/k的增加，使用2比特gsr算法和∞比特gsr算法获得的图信号恢复结果类似于真正的图信号，这表明2比特gsr算法的性能与∞比特的gsr算法相当。
[0075]
我们考虑一个由物理科学实验室发布的海洋表面温度(sst)的真实数据集。该数据集从1881 年10月到1989年12月每周收集一次，空间分辨率为经纬度1
°×1°
。我们从经度西经0
°
到西经360
°
，纬度南纬90
°
到北纬90
°
的范围内随机选择k＝2000个节点的sst。如附图5所示，利用4-近邻算法将2000个节点的sst构造为图g＝(v,ε,w)，每条边的权重与其两个节点之间距离的平方成反比。我们从m个低分辨率低比特量化数据中恢复sst，进一步评估gsr 算法的性能。
[0076]
在量化/非量化观测数据t＝800和snr＝20db的情况下，计算mse随着在m/k＝10％、
···
、 90％范围内变化的关系。结果如附图6所示，并显示：所有方案的恢复性能都随着采样率的增加而提高，此外，4比特gsr的mse非常接近从非量化观测数据中恢复图信号的∞比特 gsr算法的mse。
[0077]
在m/k＝0.4，量化/非量化观测数据t＝600的情况下，计算mse随着snr在-5db到15db 范围内变化的关系。结果如附图7所示，并显示：使用3比特或4比特量化观测数据的gsr 算法与使用未量化观测值的∞比特gsr算法具有几乎相似的恢复精度。
[0078]
在m/k＝0.4和snr＝20db的情况下，计算mse随着观测数据t在100到10000范围内变化的关系。结果如附图8所示，并显示：如果要实现2
×
10-3
的mse，∞比特、4比特、3比特、 2比特和1比特的情况分别需要大约100、120、150、300和1000个观测值。这表明对于4 比特、3比特、2比特和1比特的量化情况，实现2
×
10-3
的mse所需的总比特数分别为480、450、600和1000比特。
[0079]
应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，而做出替换或变形，均落入本发明的保护范围之内，本发明的
请求保护范围应以所附权利要求为准。

技术特征：

1.基于低比特采样的图信号恢复方法，其特征在于，包括以下几个步骤：步骤1：收集采样数据，建立信号模型；步骤2：提出最大似然问题，其解提供对图信号x的估计；步骤3：正则化最大似然函数；步骤4：计算对数似然函数的辅助下界；步骤5：采用期望最大化方案估计图信号x。2.根据权利要求1所述的基于低比特采样的图信号恢复方法，其特征在于，步骤1中，无向连通加权图g＝(v,ε,w)，其中节点集v:＝{1,
…
,k}，边集权重矩阵图信号是从节点集v到的映射，每个节点i∈v关联一个图信号则图信号排列成一个长度为k的向量如果x是平滑的，则相邻节点的图信号具有相似性，从节点的随机子集上获取的m<k个含有噪声的采样数据中恢复图信号x，其中m个噪声样本可表示为：随机子集：表示在n时刻被随机采样的m个节点，噪声样本y
s
[n]与x有关，则有y
s
[n]:＝s[n]y[n]其中y[n]＝[y1[n],y2[n],
…
,y
k
[n]]
t
:＝x+v[n]:＝x+v[n]表示长度为k的单位向量，该向量的第k
mn
个元素为1，其余项为0；v[n]:＝[v1[n],v2[n],
…
,v
k
[n]]
t
定义为空间和时间上独立的零均值高斯噪声，协方差是这里diag{x1,
…
,x
k
}表示生成对角矩阵，其中主对角线元素是x1,
…
,x
k
；设每个节点k∈v都配备一个随机变量发生器和量化器，在n时刻，每个随机变量发生器可以提供服从标准正态分布的随机因子ξ
k
[n]，保证量化器的输入值具有零均值的统计特性，利用ξ
k
[n]，量化器可以产生低分辨率低比特输出d
k
[n]＝q(z
k
[n])，k∈v；其中z
k
[n]＝ξ
k
[n]y
k
，y
k
[n]:＝x
k
+v
k
[n]q表示按元素量化操作，定义为：q(z)＝γ
h
(α
h
≤z＜α
h+1
)表示2
q-1个阈值水平。3.根据权利要求1所述的基于低比特采样的图信号恢复方法，其特征在于，步骤2中，提出最大似然问题，其解使用q比特量化观测数据提供对x的估计；观测值可表示为：这里，
其中：z[n]:＝[z1[n],
…
,z
k
[n]]
t
λ[n]:＝diag(ξ1[n],
…
,ξ
k
[n])υ[n]:＝s[n]λ[n]v[n]υ[n]是零均值高斯随机向量，协方差是4.根据权利要求1所述的基于低比特采样的图信号恢复方法，其特征在于，步骤3中，通过正则化最大似然函数来恢复x：l(x)＝logp(d
s
|x)-γx
t
lx其中：是衡量平滑度的正则化项，这里log(x)表示对x取对数，l是拉普拉斯矩阵，γ是平衡平滑度和数据拟合的权衡因子。5.根据权利要求1或4所述的基于低比特采样的图信号恢复方法，其特征在于，步骤4中，对于似然函数l(x)，利用jensen不等式的对数函数形式，使用logp(d
s
|x)的辅助下界：其中<x>
p(x)
表示x对分布p(x)的期望。6.根据权利要求1所述的基于低比特采样的图信号恢复方法，其特征在于，步骤5中，采用期望最大化(em)方案，给定初始化参数em迭代在下界上执行坐标上升，则有最大化l(x)求解参数x的最大似然估计，更新参数x。

技术总结

本发明针对传统图信号恢复算法的高分辨率采样实现，从而导致该算法是高成本且高功耗的情况，提出了一种基于期望最大化的低比特图信号恢复的循环迭代算法。本发明所提出的方法根据图上相邻节点之间信号变化很小的空间关系，利用正则化的最大似然优化算法从采样数据中重建与未采样节点相关的未知数据，采用基于期望最大化的迭代方案来检索未量化的观测数据，并从低分辨率低比特测量数据中恢复图信号，该方法可以显著提高图信号的恢复性能，而与高分辨率采样实现相比，功耗和实现成本仍然要低得多。要低得多。要低得多。