Large Average Submatrices of a Gaussian Random Matrix: Landscapes and Local Optima

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. This talk will present several new theoretical results concerning large average submatrices of an n x n Gaussian random matrix that are motivated in part by previous work on biomedical applications. We will begin by considering the average and distribution of the k x k submatrix having largest average value (the global maximum), and 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 results characterizing the value and joint distribution of a typical local maximum, and identifying the limiting behavior of the number of local maxima. In the last part of the talk I will present some recent results on the overlap and behavior of k x k submatrices ordered by their average values. Joint work with Shankar Bhamidi (UNC) and Partha S. Dey (UIUC)