Georgia Institute of Technology College of Sciences

The problem of finding large average submatrices of a real-valued matrix arises in the exploratory analysis of data from disciplines as diverse as genomics and social sciences. Motivated in part by previous work on this applied problem, this talk will present several new theoretical results concerning large average submatrices of an n x n Gaussian random matrix. We will begin by considering the average and joint distribution of the k x k submatrix having largest average value (the global maximum). We then turn our attention to submatrices with dominant row and column sums, which arise as the local maxima of a practical iterative search procedure for large average submatrices I will present a result characterizing the value and joint distribution of a local maximum, and show that a typical local maxima has an average value within a constant factor of the global maximum. In the last part of the talk I will describe several results concerning the *number* L_n(k) of k x k local maxima, including the asymptotic behavior of its mean and variance for fixed k and increasing n, and a central limit theorem for L_n(k) that is based on Stein's method for normal approximation. Joint work with Shankar Bhamidi (UNC) and Partha S. Dey (UIUC)