Improved Sum-of-Squares Lower Bounds for the Hidden Submatrix Problem

Given a large data matrix A, we consider the  problem of determining whether its entries are iid with some known marginal distribution P_0, or instead A contains a principal submatrix  whose entries have marginal distribution P_1, while the other entries have distribution P_0. A special case of this problem corresponds to the famous hidden clique problem. 

This is a prototypical example of a class of problems that for which the optimal statistical performances are well understood, but no polynomial algorithm is known to get even close to this ideal behavior. I will discuss what is known about a semidefinite programming hierarchy (the sum-of-squares hierarchy) that is the most powerful algorithmic idea known for a broad class of problems.

The analysis consists in bounding the eigenvalues of certain random matrices of non-standard type, for which we will exploit the power method. [Based on joint work with Yash Deshpande]