TL;DR
This survey provides a comprehensive overview of the properties of eigenvectors of random matrices, focusing on their behavior in combinatorial and theoretical computer science contexts. It bridges the gap between theoretical random matrix theory and practical applications by detailing how eigenvectors behave like uniformly distributed random vectors on the unit sphere, with specific results on their coordinate distributions, norms, and delocalization.
What Problem Does This Paper Address?
Eigenvectors of large matrices and graphs are fundamental to many areas of combinatorics and theoretical computer science, underpinning algorithms for spectral clustering, partitioning, and community detection. However, understanding the behavior of these eigenvectors when the underlying matrix is random presents a significant challenge. This survey addresses the need for a unified and up-to-date account of the properties of eigenvectors for various models of random matrices, particularly Wigner matrices and their perturbations, which are central to many applications. The core question is: how do the entries and norms of eigenvectors behave when the matrix is random, and how does this behavior relate to the ideal case of uniformly distributed random vectors?
Methods
The survey employs a range of mathematical tools and techniques from probability theory and linear algebra. Key methods include:
- Universality Results: Direct comparison theorems are used to show that eigenvectors of general Wigner matrices behave similarly to those of the Gaussian Orthogonal Ensemble (GOE), which serves as an "ideal" benchmark due to its rotational invariance.
- Concentration Inequalities: Tools like Chebyshev's inequality and exponential Markov inequalities are used to bound the probability of deviations for various quantities, such as the magnitude of eigenvector coordinates or the mass distribution on subsets of coordinates.
- Order Statistics: The analysis of smallest and largest coordinates (l∞-norm and l_min-norm) relies on understanding the behavior of order statistics of random variables.
- Low-Rank Perturbations: Techniques for analyzing matrices that are deterministic perturbations of Wigner matrices are employed, particularly for understanding the behavior of adjacency matrices of random graphs.
- Probabilistic Method and Union Bound: These are standard techniques for proving existence and bounding probabilities over large sets of random variables or events.
- Spectral Theory: The Courant-Fisher minimax theorem and Cauchy's interlacing inequalities are fundamental tools for analyzing eigenvalues and their relationship to eigenvectors.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Eigenvectors as Random Vectors: A central theme is that eigenvectors of many random matrices behave like random vectors uniformly distributed on the unit sphere. This provides a powerful intuition and a benchmark for understanding their properties.
- Universality: The survey highlights that for many random matrix ensembles, particularly Wigner matrices with sub-exponential or sub-gaussian entries, the behavior of eigenvectors is remarkably universal, meaning it depends less on the specific distribution of the entries (beyond basic moment conditions) and more on the general structure of the matrix.
- Delocalization: For many random matrix models, eigenvectors are delocalized, meaning their mass is spread across many coordinates, rather than concentrated on a few. This is contrasted with heavy-tailed or band matrices where localization can occur.
- Extremal Coordinates: The largest and smallest coordinates of eigenvectors exhibit specific behaviors, often related to logarithmic factors of the matrix dimension, which are crucial for understanding their overall spread.
- Connection to Graph Theory: The survey explicitly connects random matrix theory to graph theory by analyzing eigenvectors of random graph adjacency matrices, showing how their properties relate to Wigner matrices.
Key Results
The survey presents numerous theorems and corollaries detailing the behavior of eigenvectors. Some key quantitative findings include:
- l∞-norm of Eigenvectors: For Wigner matrices with sub-gaussian entries, the largest coordinate of an eigenvector $v_j$ is bounded by $O(\sqrt{\log n / n})$ with high probability.
- l_p-norm of Eigenvectors: For $1 < p < 2$, the $l_p$-norm of eigenvectors is bounded by $O(n^{1/p - 1/2})$ with high probability.
- Mass Distribution: For a subset $S$ of coordinates of size $|S| = \delta n$, the squared $l_2$-norm of the eigenvector restricted to $S$, $||v||_S^2$, is distributed according to a beta distribution, with mean $\delta$ and variance $\delta(1-\delta) / (n/2+1)$.
- Delocalization for Random Graphs: For Erdős-Rényi random graphs, eigenvectors are shown to be delocalized, with any subset of size $\delta n$ containing a non-negligible fraction of the vector's $l_2$-norm.
- Heavy-Tailed Matrices: For heavy-tailed random matrices, eigenvectors corresponding to the largest eigenvalues can become localized, concentrating most of their mass on at most two coordinates.
Limitations and Future Work
- Optimal Bounds for Non-Sub-Gaussian Entries: While significant progress has been made for sub-gaussian and sub-exponential entries, obtaining optimal bounds for eigenvectors when entries are not sub-gaussian remains an open question.
- Universality of Limiting Distributions: The universality of the limiting distribution of the smallest coordinate ($||v_j(W)||_{min}$) and the $l_\infty$-norm ($||v_j||_{ex}$) is also posed as an open question.
- Extension of Concentration Results: Extending concentration of the extreme order statistics to eigenvectors of Wigner matrices with non-Gaussian entries is suggested.
- Common Strengthening of Estimates: The authors note the desirability of a common strengthening of estimates for no-gaps delocalization, bridging the gap between different approaches.
- General Perturbations: While diagonal perturbations are well-studied, understanding eigenvectors of more general low-rank perturbations of Wigner matrices is an ongoing area of research.
Summary updated