Search

\indent Over the last two decades, randomization has emerged as a leading tool for pursuing efficiency in numerical linear algebra. Its benefits can be explained in part by smoothed analysis, where an algorithm that fails spectacularly in certain cases may be unlikely to do so on random -- or randomly perturbed -- inputs. This observation implies a simple framework for developing accurate and efficient randomized algorithms:\ apply a random perturbation and run an existing method, whose worst-case error (or run-time) can be avoided with high probability. \\\indent Recent work of Banks, Garza-Vargas, Kulkarni, and Srivastava applied this framework to the standard eigenvalue problem, developing a randomized algorithm that (with high probability) diagonalizes a matrix in nearly matrix multiplication time [Foundations of Computational Math 2022]. Central to their work is the phenomenon of \textit{pseudospectral shattering}, in which a small Gaussian perturbation regularizes the pseudospectrum of a matrix, with high probability breaking it into disjoint components and allowing classical, divide-and-conquer eigensolvers to run successfully. Prior to their work, no way of accessing the benefits of divide-and-conquer’s natural parallelization was known in general. \\ \indent In this thesis, we extend the work of Banks et al.\ to the generalized eigenvalue problem -- e.g., $Av = \lambda Bv$ for matrices $A,B \in {\mathbb C}^{n \times n}$. Our main contributions can be summarized as follows. \begin{enumerate}[itemsep=0em] \item First, we show that pseudospectral shattering generalizes directly:\ randomly perturbing $A$ and $B$ has a similar regularizing effect on the pseudospectra of the corresponding matrix pencil $(A,B)$ with high probability. \item Building on pseudospectral shattering, we construct and analyze a fast, randomized, divide-and-conquer algorithm for diagonalizing $(A,B)$, which begins by randomly perturbing the inputs. \item Finally, we demonstrate that both

This thesis contributes to the emerging field of nonlinear random matrix theory and deep learning theory. The main contributions are summarized as follows:In the linear-width regime, where the network widths scale proportionally with the sample size, we include proof of the global laws of the neural tangent kernel (NTK) and conjugate kernel (CK) matrices across layers. For datasets with low-dimensional signal structures, we characterize the outlier eigenvalues and eigenvector alignments of the CK matrices, extending recent results on spiked covariance models.In the ultra-wide regime, where the first layer's width is much larger than the sample size, we show that spectra of both CK and NTK matrices converge to a deformed semicircle law.Going beyond random initialization, we investigate the spectral properties of trained weight, CK, and NTK matrices through empirical and theoretical analyses. Empirically, it demonstrates the invariance of bulk spectra under small learning rates, the emergence of outliers with large learning rates, and the heavy-tailed distributions after adaptive gradient training, correlating them with feature learning.Theoretically, we prove the invariance of bulk spectra under small constant learning rates and characterize the feature learning phenomenon, where gradient descent optimizes the first-layer weights, leading to a rank-one spiked structure in the weight and CK matrices, with spike eigenvectors aligning with test labels.

This thesis concerns the spectral and combinatorial properties of sparse random graphs and hypergraphs. We present three models, including inhomogeneous random graphs, random bipartite biregular graphs, and the hypergraph stochastic block model, emphasizing the limiting spectral distributions, eigenvalue fluctuations, and top eigenvalues and eigenvectors, respectively. We first present a graphon approach to finding the limiting spectral distribution of Wigner-type matrices, building a connection between random matrices and graph limits. For random bipartite biregular graphs, we analyze their cycle structure and compute the global eigenvalue fluctuations. Finally, we study a spectral algorithm for community detection in sparse hypergraph stochastic block models using a new matrix that counts self-avoiding walks on hypergraphs.

This thesis concerns the spectral and combinatorial properties of sparse random graphs and hypergraphs. We present three models, including inhomogeneous random graphs, random bipartite biregular graphs, and the hypergraph stochastic block model, emphasizing the limiting spectral distributions, eigenvalue fluctuations, and top eigenvalues and eigenvectors, respectively. We first present a graphon approach to finding the limiting spectral distribution of Wigner-type matrices, building a connection between random matrices and graph limits. For random bipartite biregular graphs, we analyze their cycle structure and compute the global eigenvalue fluctuations. Finally, we study a spectral algorithm for community detection in sparse hypergraph stochastic block models using a new matrix that counts self-avoiding walks on hypergraphs.