FINDING A LARGE SUBMATRIX OF A GAUSSIAN RANDOM MATRIX

• 成果类型: Article
• 署名作者: Gamarnik, David; Li, Quan
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/17-AOS1628
• 发表日期: 2018
• 页码: 2511-2561
• 关键词: large-average; graph

摘要

We consider the problem of finding a k xk submatrix of an nxn matrix with i.i.d. standard Gaussian entries, which has a large average entry. It was shown in [Bhamidi, Dey and Nobel (2012)] using nonconstructive methods that the largest average value of a k x k submatrix is 2(1 + o(1)) root log n/k, with high probability (w.h.p.), when k = O(log n/log log n). In the same paper, evidence was provided that a natural greedy algorithm called the Largest Average Submatrix (LAS) for a constant k should produce a matrix with average entry at most (1+ o(1)) root 2 logn/k, namely approximately root 2 smaller than the global optimum, though no formal proof of this fact was provided. In this paper, we show that the average entry of the matrix produced by the LAS algorithm is indeed (1+ o(1)) root 2 logn/k w.h.p. when k is constant and n grows. Then, by drawing an analogy with the problem of finding cliques in random graphs, we propose a simple greedy algorithm which produces a kxk matrix with asymptotically the same average value (1 + o(1)) root 2 logn/k w.h.p., for k = o(log n). Since the greedy algorithm is the best known algorithm for finding cliques in random graphs, it is tempting to believe that beating the factor root 2 performance gap suffered by both algorithms might be very challenging. Surprisingly, we construct a very simple algorithm which produces a k x k matrix with average value (1 + ok(1) + o(1))(4/3) root 2 logn/k for k = o((log n)(1.5)), that is, with the asymptotic factor 4/3 when k grows. To get an insight into the algorithmic hardness of this problem, and motivated by methods originating in the theory of spin glasses, we conduct the so-called expected overlap analysis of matrices with average value asymptotically (1+ o(1)) alpha root 2 logn/k for a fixed value alpha is an element of [1, root 2]. The overlap corresponds to the number of common rows and the number of common columns for pairs of matrices achieving this value (see the paper for details). We discover numerically an intriguing phase transition at alpha* (sic) 5 root 2/(3 root 3) approximate to 1.3608...is an element of[4/3, root 2]: when alpha < alpha* the space of overlaps is a continuous subset of [0, 1] 2, whereas alpha = alpha* marks the onset of discontinuity, and as a result the model exhibits the Overlap Gap Property (OGP) when alpha > alpha*, appropriately defined. We conjecture that the OGP observed for alpha > alpha* also marks the onset of the algorithmic hardness-no polynomial time algorithm exists for finding matrices with average value at least (1+ o(1)) alpha root 2 logn/k, when alpha > alpha* and k is a mildly growing function of n.