The problem of finding large average submatrices of a real-valued matrix arises in the exploratory analysis of data from a variety of disciplines, ranging from genomics to social sciences. This talk details several new results concerning the asymptotic behavior of large average submatrices of an nxn Gaussian random matrix. We begin by considering with the average and joint distribution of the (globally optimal) kxk submatrix having largest average value. We then turn our attention to submatrices with dominant row and column sums, which arise as the local optima of a useful iterative search procedure for large average submatrices. Paralleling the result for global optima, we will consider the average and joint distribution of a typical (locally optimal) kxk submatrix with dominant row and column sums. The last part of the talk will be devoted to the analysis of the *number* of locally optimal kxk submatrices, L_n(k), beginning with the asymptotic behavior of its mean and variance for fixed k and increasing n. The principal result of the talk is a Gaussian central limit theorem for L_n(k) that is based on a new variant of Stein's method for normal approximation.

Joint work with Shankar Bhamidi and Partha S. Dey