Eigenvectors of Large-Dimensional Random Matrices and Graphs

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

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.