谱图理论及其在压缩感知中的应用

The spectral graph theory mainly investigates the spectral property of some matrices associated with a graph, and establishes the relationship between the spectral property and the structural property, which is an important field in algebraic graph theory and combinatorial matrix theory. The project will discuss the fundamental problem in spectral graph theory from the viewpoints of extremal behavior and general behavior of the spectral property of graphs respectively: one is to characterize the extremal property of extreme spectral parameters (i.e., the extremal spectral property), and use eigenvalues to bound the structural paremeters such as chromatic number, diameter, connectivity, domination number and bondage number, or characterize the structural property such as Hamiltonian property; the other is to establish random graph models with prescribed structural property or apply some known random graph models to characterize the spectral property and its connection with structural property that most of the graphs in the models obey (i.e., the general spectral property). We try to clarify the difference between extremal property and general property of the spectra. On the other hand, the project will apply spectral graph theory in the reseach of compressed sensing, construct the structured measurement matrices based on random graphs, discuss the restricted isometry property of the measurement matrices by spectral graph theory and probability method, and also apply compressed sensing theory to acquire the spectral property or structural property of sparse graphs. The project will have both theoretical and paratical values in algebraic graph theory, combinatorial matrix theory, probability method and compressed sensing.

谱图理论主要研究图的矩阵表示的谱性质，建立谱性质和结构性质的联系，是代数图论与组合矩阵论的重要研究领域。本项目将分别从图的谱性质的极值行为和普遍行为两个角度，探讨谱图理论的基本问题：（1）刻画图的极端谱参数的极值性质（即极值谱性质），以特征值界定图的结构参数（如色数、直径、连通度、控制数、约束数）或刻画结构性质（如Hamilton性）；（2）建立给定结构性质的随机图模型或应用已有的随机图模型，刻画模型中绝大数图所具有的谱性质以及与结构性质的联系（即普遍谱性质），弄清谱的极值性质与普遍性质的差异。 另一方面，本项目拟把谱图理论应用于压缩感知研究中，构建基于随机图的具有结构的测量矩阵，应用谱图理论和概率方法讨论测量矩阵的受限等距性，应用压缩感知理论获取稀疏图的谱性质或结构性质。 本项目的研究对代数图论、组合矩阵论、概率方法、压缩感知理论等都有很好的理论意义和应用价值。

本项目主要研究谱图理论中的极值谱性质与普遍谱性质、以及谱图理论在压缩感知的应用。理论成果包括: (1) 建立图的非平凡最小特征值、谱半径等极值谱参数与图的控制数、匹配数、边覆盖数、色数等联系；(2)应用图的符号差、秩、正（负）惯性指数、Estrada指数、Kirchhoff指数等探讨图的普遍谱性质，建立这些参数与图的匹配数、圈空间维数、点二部度等联系。应用成果为: 提出随机对称Toeplitz矩阵、随机对称Bernoulli矩阵作为压缩感知的测量矩阵，并应用概率方法证明它们具有RIP性质；提出基于矩阵QR分解的点模式匹配方法以及基于线图的谱匹配算法。.项目组成员共发表论文33篇, 其中SCIE收录28篇、EI收录3篇。举办国际国内学术会议7次，参加18次国际国内学术会议或研讨班，应邀作学术报告5次。研究成果“谱图理论研究”获得安徽省自然科学三等奖。培养了6名硕士生，4名博士生。