图是广义的数据表示形式,可用于描述许多应用程序中数据域的几何结构,包括社交,能源,交通,传感器和神经元网络。与图中每个边关联的权重通常代表其连接的两个节点之间的相似度或相关程度。图节点间的连通性和边缘权值可由数据推断,也可由实际物理性质决定。例如,边缘权重可以与图节点之间的物理距离成反比。将信号幅值赋给相应的图节点,则所有图节点信号构成了一个图信号集合,若按某种顺序排列,则图信号集合元素可构成一个信号向量,简称为图信号。图信号处理就是对图信号进行平移、滤波、调制、尺度变换等操作。时域信号的采样与重构是传统信号处理的核心任务之一。同样的,图信号的采样与重构在图信号处理理论研究中也是必不可少的。考虑到图信号结构并不规则,因而其采样相较传统时域信号采样而言更加复杂。主要原因之一是,图信号的底层结构为随机加权图,这样的结构决定了图节点上的信号的顺序也可以是随机排列的,因此如传统时域信号采样中按照节点序号均匀获取采样值的方法将失去效果。此外,频谱混叠效应也无法在图信号的变换域明确定义。因此,对图信号的采样和重构理论的研究是非常有必要的。本文集中研究了图信号的采样与重构算法,主要工作如下:(1)研究了稀疏图信号的恢复问题。首先,利用压缩感知思想将图信号恢复问题转化为一个求解图信号频域系数的最优化问题。其次在考虑含噪声采样的情况下,对误差与图频域系数做分布假设,进而利用贝叶斯分析手段将求解频域系数的最优化问题转化为求解误差与频域系数的最大后验概率。最后,利用相关向量机算法求解参数,并使用归一化的均方误差衡量重构效果。与其他恢复算法进行比较,实验结果证明了基于贝叶斯压缩感知算法在图信号恢复中的优越性。(2)实现了对带限图信号最优采样算子选取算法的改进。考虑噪声时,基于完美恢复理论选取的不同采样对噪声的鲁棒性不尽相同,因此在采样算子里必存在一个最优采样算子,使得恢复后的信号偏差最小。常用贪婪算法求解此类最优采样算子,通过特征分解确定目标矩阵最小特征值,后取最小特征值的最大化得到采样坐标。然而这样的最大最小化方法在目标矩阵较大时(通常都较大)时间复杂度较高。因此考虑通过圆盘定理获取目标矩阵特征值可达域范围,估算最小特征值下界。仿真显示,基于圆盘定理的估算方法时间成本明显低于常用的特征分解方法。(3)研究了近似带限信号的最佳采样算子选取问题。近似带限信号是存在高频泄露或高频干扰的带限信号。在处理近似带限信号时,可以采用严格带限信号现有的处理方法,并对其改进以更好的符合实际信号的特点。本文基于严格带限图信号的采样理论,提出适用于近似带限图信号的最佳采样算子选取算法。通过恢复信号与原始信号的范数逼近,算法有效增强了图信号对其高频干扰的鲁棒性。此外所提出的采样算法同时适用于有向图和无向图,恢复的假设既易于检查又易于满足。