Nonlinear Matrix Concentration and Its Applications

The main purpose of this dissertation is to introduce a new method for obtaining norm bounds for random matrices, where each entry is a low-degree polynomial in an underlying set of independent real-valued random variables. Such matrices arise in a variety of settings in the analysis of spectral and optimization algorithms. Using ideas of decoupling and linearization, we show a simple way of expressing norm bounds for such matrices, in terms of their higher-order derivatives. Some of the highlighted applications include graph matrices, tensor networks and smoothed analysis. In addition, we present a concise analysis of the ellipsoid fitting problem using the concentration bound of random matrices with covariance structure.