Eigenvectors of Large-Dimensional Random Matrices and Graphs

现代社会产生了大量的数据，其中大部分需要进行分析和分类，以做出明智的决策。 该项目的动机是在研究和分析大型数据集时自然出现的基本问题;出现此类问题的一些例子包括检测大型网络中的社区结构，以及将大型过采样数据集减少为更小，更易于管理的集合，从中可以进行推断。 设计、分析和研究这些任务的算法通常依赖于随机图和随机矩阵理论。 例如，研究表明，许多重要的网络（如社交网络、生物网络和电力网络）可以用随机图来建模。 该项目将开发有关这些对象的特征向量的理论结果，这将有助于工程师和科学家实施算法，并从大型数据集进行可靠的推断。 本研究项目部分建立在研究人员最近的工作，以获得大矩阵特征向量的属性和行为的清晰图像，包括那些非常离散的性质（例如，随机图的邻接矩阵）。 考虑的一些主题包括维格纳矩阵的特征向量的研究以及扰动维格纳矩阵的特征向量的行为。 这些问题的动机是由不同的应用程序，包括社区检测，矩阵完成，矩阵稀疏化。 为了解决这些问题，研究人员将开发和利用一系列技术，包括分析技术（例如，预解式技术，测度的集中），代数工具（例如，线性代数），和概率方法（例如，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern society produces massive amounts of data, much of which needs to be analyzed and categorized to make informed decisions. This project is motivated by fundamental questions that arise naturally in the study and analysis of large datasets; some examples where such questions arise include the detection of community structure in large-scale networks and the reduction of large oversampled datasets to smaller, more manageable collections from which inferences can be made. Designing, analyzing, and studying algorithms for these tasks often rely on random graph and random matrix theory. For example, studies have shown that many important networks (such as social networks, biological networks, and power networks) can be modeled by random graphs. This project will develop theoretical results concerning the eigenvectors of such objects, which will help engineers and scientists implement algorithms and make reliable inferences from large datasets. This research project builds in part on the investigator's recent work to obtain a clear picture of the properties and behaviors of eigenvectors of large matrices, including those of a very discrete nature (for example, the adjacency matrix of random graphs). Some of the topics considered include the study of eigenvectors of Wigner matrices as well as the behavior of eigenvectors for perturbed Wigner matrices. Such questions are motivated by a diverse collection of applications including community detection, matrix completion, and matrix sparsification. To address these problems, the investigator will develop and utilize a collection of techniques including analytic techniques (e.g., resolvent techniques, concentration of measure), algebraic tools (e.g., linear algebra), and probabilistic methods (e.g., Littlewood-Offord theory).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.