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

项目名称： 谱图理论及其在压缩感知中的应用

项目编号： No.11371028

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 范益政

作者单位： 安徽大学

项目金额： 62万元

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

中文关键词： 图；随机图；谱；压缩感知；概率方法

英文摘要： 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 theor

英文关键词： Graph；random graph；spectrum；compressed sensing；probabilistic method