本发明属于图信号处理技术领域,具体的说是涉及一种面向小扰动带限图信号的采样集的最优速率分配方法。
背景技术:
图的边缘可以描述物理节点之间的真实互联,图信号被定义为顶点域到实域的映射;图信号处理依赖于图拓扑;例如无向图的图傅里叶变换(gft)是将信号投影到由图拉普拉斯矩阵的特征向量生成的空间上的算子。然而如果图拓扑不确定的,或者近似已知,那么拉普拉斯特征向量空间是不确定的,频域空间的投影也变的不确定。在图信号采样中,主要任务之一是选择一个节点子集即采样集,使图信号只在采样集中被观察到,而在其他所有节点上的值都被插值。
然而,许多物理分布是网络(如传感器网络)中的节点通常收到能量约束和有限的通信带宽的限制,在数据可以传输到一个集中节点进行进一步处理之前,需要进行量化,但是,以往大多数关于图信号采样的工作都没有明确考虑每个节点(传感器)位置上采样数据的量化的影响。
zl2020104749236公开了一种基于滤波器的带限图信号采样方法,此采样方法利用盖尔圆盘定理估计矩阵最小特征值的下限,利用近似滤波器得到低复杂度的重建方法,利用盖尔圆盘定理估计矩阵最小特征值的下限,用近似滤波器得到低复杂度的重建方法,但是这种采样方法的计算较为复杂,容易产生误差影响采样结果。
zl2016100496010公开了一种基于压缩感知的图像亚奈奎斯特采样方法,该采样方法结合了压缩感知理论和图像信号的频谱特点,当信号的带宽较宽,频谱占有率较低时,此采样方法能够在具体非零频段的位置未知的情况下以远低于奈奎斯特速率的采样率对信号进行无失真压缩采样,但此种采样方法需测量矩阵维数过大且重构阶段复杂,并非是最优的采样方法。
技术实现要素:
为了解决上述问题,本发明提供了一种面向小扰动带限图信号的采样集的最优速率分配方法,使量化信号值的信号恢复误差最小化,实验结果表明,所提出的解决方案总能获得比均匀速率分配更好的性能。
为了达到上述目的,本发明是通过以下技术方案实现的:
本发明是一种面向小扰动带限图信号的采样集的最优分配方法,该最优分配方法包括如下步骤:
s1,由n个节点v与一组ε个边组成的无向图g,定义a为邻接矩阵,定义d为节点度的对角矩阵,定义l为拉普拉斯矩阵,拉普拉斯矩阵为节点度的对角矩阵与邻接矩阵的差值即l=d-a,描述图的拓扑,对其特征分解为l=uλut,其中u为列向量为特征向量ui;
s2,定义一个信号x在无向图g上映射:v→r,将每个节点与一个实数联系起来,对于无向图上的图信号,向量x的图傅里叶变换
s3,不在封闭形式下找到精确的扰动,而是在具有多个边缘扰动先验概率的情况下,导出微扰特征值或特征向量对的近似封闭表达式,其中特征值最小为零,多重度为1;
s4,对拓扑不确定性下的图信号分析,将图傅里叶变换观测的信号向量投影到拉普拉斯矩阵特征向量生成的空间上;
s5,对采样集量化,并对采样图信号重构;
s6,基于贪婪算法的节点速率分配,实现对采样集的最优速率分配,考虑到采样集中顶点的速率分配问题,其中每个顶点都假定使用具有不同速率的统一量化器。
本发明的有益效果是:本发明使量化信号值的信号恢复误差最小化,所提出的解决方案总能获得比均匀速率分配更好的性能。
附图说明
图1为本发明的流程图。
图2为随机erdos-renyi图(rerg)边缘连接概率和所有权值等于1,扰动概率为0.002,节点数为500,采样集大小为50,总速率不同的有效采样和随机采样的仿真比较图。
图3为随机erdos-renyi图(rerg)边缘连接概率和所有权值等于1,扰动概率为0.002,节点数为500,总速率大小为50,采样集大小不同的有效采样和随机采样的仿真比较图。
具体实施方式
以下将以图式揭露本发明的实施方式,为明确说明起见,许多实务上的细节将在以下叙述中一并说明。然而,应了解到,这些实务上的细节不应用以限制本发明。也就是说,在本发明的部分实施方式中,这些实务上的细节是非必要的。
本发明是一种面向小扰动带限图信号的采样集的最优分配方法,包括以下步骤:
s1,节点v={1,……,n}与一组ε个边组成的无向图g=(v,ε),定义a为邻接矩阵,如果(i,j)∈ε,i,j∈v,aij不为0,其情况为0。定义d为节点度的对角矩阵,
λ为对角元素为特征值λi,i=1,……,n的对角矩阵。因为图是无向的,所以拉普拉斯矩阵是对称的,其特征值为非负的。
s2,定义一个信号x在图g上映射:v→r,将每个节点与一个实数联系起来。对于无向图上的图信号,向量x的图傅里叶变换
当处理模图时,gft是特别有用的,模图是由一组弱互连的簇组成的,并且信号在每个簇内是平滑的,但可以在不同的簇[40]上自由地假设任意值。在这种情况下,事实上,gft是稀疏或者近似稀疏的,这种稀疏性使得有效的去噪、采样和恢复算法成为可能,然而,从(1)中可以清楚地看出,对图拓扑的不完善认识转化为对拉普拉斯特征向量的不完善认识,进而最终转化为对观测信号的gft的不完善认识,分析不完善的图拓扑知识对gft的影响,并建立有助于减轻这种影响的分析模型。
定义一个名义上的拉普拉斯矩阵l与实际拉普拉斯矩阵
其中
一般来说,在封闭形式下找到精确的扰动是不可能的,但是在单个边缘扰动的情况下,有可能:i)确定哪个特征值/特征向量对被给定的边缘扰动或不被扰动,只要看名义拉普拉斯矩阵l的特征向量;ii)导出微扰特征值/特征向量对的近似封闭表达式,在小微扰假设下有效。
为了简化分析,假设
(a0):名义拉普拉斯矩阵的特征值唯一。
s3,不在封闭形式下找到精确的扰动,而是在具有多个边缘扰动先验概率的情况下,导出微扰特征值/特征向量对的近似封闭表达式;
具体为:假设其中一个边受到扰动,即第m条边,引入列向量am∈rn,am(vm1)=1,am(vm2)=-1,其余为0,其中vm1,vm2为m边的端点,则实际拉普拉斯矩阵
其中,若m边增加则σm=1,若m边去除,则σm=-1。
在不失一般性的情况下,考虑原图是连通的,特征值按递增顺序排列。因为图是连通的,所以最小的特征值为0,多重度为1。
在假设(a0)下,可以这样写0=λ1<λ2<......<λn,因为提前知道,哪个是扰动边,扰动矩阵仍将有最小的特征值等于零和相关的所有的特征向量与向量,作为最初的拉普拉斯算子,这没有扰动第一特征值和特征向量,即
关注于
定理1:如果ui(vm1)=ui(vm2),第i个特征值/特征向量对就不会因m条边的添加/删除而改变。
当满足假设(a1):||δl||f<<||l||f,在(a0)的假设下,可导出扰动特征值特征向量的封闭近似表达式:
现考虑有多边发生扰动的时候,拉普拉斯扰动可写为
εp为扰动边集,在小扰动条件下特征值和特征向量扰动可表示为每个边的扰动之和,即:
假设当边m的去除/添加是一个具有特定概率pm特征的随机事件,如果边扰动概率为pm,其余为0,则小扰动条件下的特征值和特征向量扰动可表示为:
s4,对拓扑不确定性下的图信号分析,将gft观测的信号向量投影到拉普拉斯矩阵特征向量生成的空间上;
具体解释为:对于无向图,gft将观测的信号向量投影到拉普拉斯矩阵特征向量生成的空间上,因此,如果图仅仅是不完全已知的,拓扑上的不确定性就会转化为对观测信号频谱的不确定性。给定一个无向图对的拉普拉斯矩阵l,x为图上定义的信号,其图傅里叶变换被定义为:
如果图拓扑存在不确定,则
其中
其中bm∈rn×k,
用名义特征向量矩阵u计算观测信号x的gft得:
那么x可被表示为:
s5,对采样集量化,并对采样图信号重构;
具体为:扰动带限信号
s矩阵,列为集合s1中节点的指示函数,
采样图信号的重构
量化信号
试图从
假设信号向量s由k个不相关的随机变量组成,均值和方差均为0,则其相关矩阵
考虑一个线性估计,那么估计的向量
在未知扰动情况下,利用观测模型与图扰动的先验信息来最小化mse,某些边可能是图扰动的概率
由于mse是g的凸函数,通过关于g的梯度等于0来获得最佳向量,
设
ree=e[eet]是一个对角协方差矩阵,其中e(eet)其第i个对角元素是
ar,cr已知,mse问题转化为:
是关于ree的函数,
定义一个函数:
转化为求f(ree)的最小值,
s6,基于贪婪算法的节点速率分配,实现对采样集的最优分配,具体步骤为:
6-1:输入:输入函数f(ree)
节点速率初始值r=[0,0,……,0]长度为n
步长β迭代次数k
6-2:输出:节点速率rmin
6-3:while∑ri≤rt且迭代次数<kdo
6-4:结束循环。
本发明主要解决的是当存在小扰动的图信号时,利用小扰动分析来说明边缘扰动对图信号频谱分析的影响,并推导出对图扰动具有鲁棒性的信号估计方法,只需要知道一些边缘可能出现或消失的概率;在此基础上解决速度分配的节点采样集;考虑到抽样集中顶点的速率分配问题,其中每个顶点都假定使用具有不同速率的统一量化器。
本发明寻求一种最佳的速率分配,使量化信号值的信号恢复误差最小化。实验结果表明,所提出的解决方案总能获得比均匀速率分配更好的性能。
以上所述仅为本发明的实施方式而已,并不用于限制本发明。对于本领域技术人员来说,本发明可以有各种更改和变化。凡在本发明的精神和原理的内所作的任何修改、等同替换、改进等,均应包括在本发明的权利要求范围之内。