A Few Results in Random Matrix Theory and Random Optimization

Abstract

The thesis addresses two separate topics related by the common use of random matrices and consists of three main chapters. In the first chapter, we study the minimization problem of the least square type in random setting on an N−sphere. We start with considering the simplest instance of the cost function H(x) = ½||Ax − b||² with A (with N columns and M rows) and b (of size M) being normally distributed matrix and vector, respectively. To get insights into the corresponding cost function landscape we enumerate its stationary points using the Lagrange multiplier approach. This is done by employing the Kac-Rice method for counting stationary points of H(x). Depending on the variance of b as compared to the variance of A the total number of those points ranges from 2 to 2N. We provide the explicit formula for the expected values for the number of points in the full range of parameters and perform the asymptotic analysis for N >> 1 at fixed M/N > 1. The minimal cost solution is related to the minimal possible Lagrange multiplier and we characterize the latter, including its large-deviation function. On this basis we provide the expected value of the minimal loss/cost. To characterize the large deviations of the latter we introduce an alternative approach based on the ideas of statistical mechanics. By defining the partition function Z =∫dx ^{e−βHV (x)}, with β > 0 standing for the inverse temperature, we take advantage of the power albeit heuristic replica trick to recover the large-deviation function for the minimal cost.

The statistical mechanics approach is then used in the next chapter to investigate a more general optimisation problem replacing the ||Ax − b|| in the cost function with the sum of squares of mean zero gaussian-distributed fields V_k(x), k = 1, . . . , M over the N-sphere, with covariance invariant with respect to any rotation of the sphere. We concentrate on the case when V_k(x) are quadratic in x and try to find the associated minimal cost. This can be looked at as finding the best approximation to solving the system of M random quadratic equations V_k(x) = 0, where k = 1, . . . , M in N variables for large M, N with the fixed ratio α = M/N. In particular, we aim at finding the minimal α such that the cost is non-zero, signalling of incompatibility of the equations. We can find such α in the range characterized via the stability of the replica symmetric solution. We also determine the condition of its applicability by attempting to analyze a solution with broken replica symmetry within the Parisi scheme borrowed from the theory of spin glasses.

In the last part of the thesis we study the rank one non-Hermitian deformations of the tridiagonal matrices from β-Hermite ensembles. We are able to shed light on the problem when the perturbation away from Hermiticity is small and can be treated by the perturbation theory to the first nontrivial order. We consider the eigenvalue curvatures which serve as a characterization of the lowest order shift in real parts of the eigenvalues (caused by the said perturbation in the limit N >> 1). Similarly, we examine the eigenvector condition number – these measure the deviations of the associated eigenvectors from orthogonality. We show that the probability densities of those curvatures and condition numbers can be expressed in terms of certain cor-relation functions involving ratios of powers of the characteristics polynomials for β-Hermite ensembles. The latter are well-known for classical β = 1 and 2 and we attempt to conjecture their functional form for any β > 0. The ensuing distributions of curvatures and condition numbers are in a reasonably good agreement with direct numerical simulations.

Date of Award	1 Sept 2022
Original language	English
Awarding Institution	King's College London
Supervisor	Yan Fyodorov (Supervisor)