Far apart: outliers, extremal eigenvalues, and spectral gaps in random graphs and random matrices

相距较远：随机图和随机矩阵中的异常值、极值特征值和谱间隙

• 批准号: 2154099
• 负责人: Ioana Dumitriu
• 金额: $ 22.5万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-09-01 至 2025-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154099&HistoricalAwards=false
• 关键词: Far; apart; outliers; extremal; eigenvalues

Technological and scientific advances in the last few decades have completely changed the way in which society operates. Massive amounts of data is produced and collected. This creates the need for data to be classified and categorized in order to extract meaningful and useful information. To model enormous networks, whether social, biological, or electrical, mathematicians and computer scientists have introduced the concepts of graphs and hypergraphs, with their tensors, adjacency matrices, and spectra, and have connected properties of the latter to properties of the former in order to better understand the structure of the current technological world. The goal of this project is to advance basic understanding of outliers in the spectra of random networks; such outliers have been connected to applications from Machine Learning to Bioinformatics and Coding Theory, as their presence or absence can be used to deduce various network properties. The results of this project can be used to develop algorithms, theoretical algorithmic guarantees, and benchmarks for a variety of applications in science and technology. Through its educational component (which includes research training opportunities for graduate and undergraduate students), this project will contribute to creating and ensuring the success of the next generation of mathematicians and data scientists. The PI will study general network models with certain symmetry properties (e.g., homogeneous and inhomogeneous bipartite random graphs, uniform and non-uniform hypergraphs, and the Hypergraph Stochastic Block Model). One part of the project involves creating and analyzing a randomized generalized eigenvalue algorithm, based on finding tight bounds on the smallest singular value for a random matrix model. Methods to be employed include concentration techniques and the non-backtracking operator, in addition to other techniques from combinatorics, probability, linear algebra, and statistics, to find sharp thresholds for regimes in which outliers may or may not exist in the variety of graph and hypergraph models. The PI will also study thresholds for community recovery and detection problems in the Hypergraph Stochastic Block Model.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还将研究Hypergraph Stochastic Block Model中社区恢复和检测问题的阈值。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。