Random Matrices and Functional Inequalities on Spaces of Graphs

图空间上的随机矩阵和函数不等式

• 批准号: 2331037
• 负责人: Konstantin Tikhomirov
• 金额: $ 26.06万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2331037&HistoricalAwards=false
• 关键词: Random; Matrices; Functional; Inequalities; Spaces

This research project focuses on two fundamental notions of probability theory: random matrices (rectangular arrays of random data) and random walks on graphs. Random matrices naturally appear in problems within computer science, statistics, and mathematical physics. Studying random matrices enables one to develop better tools to analyze data, to understand properties of complex quantum systems, and to estimate performance of algorithms. The Principal Investigator (PI) will consider various models of random matrices with the goal of obtaining results that hold with very high probability. Graphs (collections of points connected by edges) have been extensively used as models of communication networks and of data organization. For example, social networks and the World Wide Web can be efficiently modeled as random graphs. Understanding characteristics of random walks on graphs helps to evaluate the speed of information exchange in networks. Moreover, random walks on certain graphs have been used for sampling, that is, constructing typical instances of complex objects. The PI will study properties of random walks on graphs by employing tools of functional analysis. The project provides research training opportunities for graduate students. The two main parts of this research are analysis of singular spectrum and eigenvalues of certain models of square random matrices, and functional inequalities on graphs. The PI will focus on studying the singularity probability of random square matrices, which is of interest in numerical analysis and combinatorics. Further, the PI will consider limiting laws for the spectrum of random matrices for previously unexplored models. The tools developed as part of this research should find applications in other problems within combinatorial and non-asymptotic random matrix theory. Secondly, the PI will apply functional analytic tools to study concentration and mixing on various graphs, including spaces of regular graphs, and Catalan structures. The goal of this part of the project is to obtain sharp estimates for mixing and relaxation times for random walks on those graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

这个研究项目集中在概率论的两个基本概念上：随机矩阵(随机数据的矩形阵列)和图上的随机游动。随机矩阵自然而然地出现在计算机科学、统计学和数学物理的问题中。研究随机矩阵使人们能够开发更好的工具来分析数据，了解复杂量子系统的性质，并估计算法的性能。首席调查员(PI)将考虑随机矩阵的各种模型，以获得概率非常高的结果。图(由边连接的点的集合)已被广泛用作通信网络和数据组织的模型。例如，社交网络和万维网可以高效地建模为随机图。了解图上随机游动的特征有助于评估网络中信息交换的速度。此外，某些图上的随机游动被用于采样，即构造复杂对象的典型实例。PI将利用泛函分析工具研究图上随机游动的性质。该项目为研究生提供了研究培训机会。这项研究的两个主要部分是正方形随机矩阵模型的奇异谱和特征值分析，以及图上的函数不等式。PI将专注于研究随机方阵的奇异性概率，这在数值分析和组合学中是很有意义的。此外，PI将考虑以前未探索的模型的随机矩阵谱的限制律。作为这项研究的一部分开发的工具应该在组合和非渐近随机矩阵理论的其他问题中找到应用。其次，PI将应用泛函分析工具来研究各种图上的集中和混合，包括正则图的空间和加泰罗尼亚结构。该项目这一部分的目标是获得对这些图表上随机行走的混合和放松时间的准确估计。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。