UC Berkeley

This thesis investigates several problems unified by the central role of eigenvalues. Leveraging probabilistic techniques, we establish the following results:1. We analyze a general class of matrix factorization algorithms, capable of computing standard factorizations such as QR, SVD, eigen decomposition, and Cholesky decomposition. Under a uniformly random pivoting strategy, any algorithm of this class is shown to exhibit the same linear rate of convergence, irrespective of the specific factorization computed.2. A general framework for computing spectral sums is introduced, leveraging rational approximations of functions and stochastic trace estimation. We apply this framework to two applications: spectral density estimation and Schatten-1 norm approximation. We give an algorithm for spectral density estimation with local guarantees and an algorithm for Schatten-1 norm approximation improving upon the best known runtime.3. We study the infimum of the spectrum, or ground state energy, of a discrete Schrödinger operator on theta\Z^d parameterized by a non-negative potential V:\R^d \rightarrow \R and a frequency parameter theta in (0,1). We relate this ground state energy to that of a corresponding continuous semiclassical Schrödinger operator on \R^d with parameter theta, arising from the same choice of potential. We prove two-sided, non-asymptotic bounds relating these quantities.4. Lastly, we prove both lower and upper bounds on the Ollivier-Ricci curvature of the basis exchange walk on a matroid. We give several examples of non-negatively curved basis exchange walks and negatively curved basis exchange walks.Though these problems are distinct in nature, together they demonstrate the versatility of probabilistic methods in spectral problems.