Finding a large submatrix of a Gaussian random matrix
We consider the problem of finding a k × k submatrix of an n × n 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 × k submatrix is 2(1 + o(1))√log n/k, wi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Mathematical Statistics
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120593 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 |
| _version_ | 1826196430280196096 |
|---|---|
| author | Gamarnik, David Li, Quan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gamarnik, David Li, Quan |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | We consider the problem of finding a k × k submatrix of an n × n 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 × k submatrix is 2(1 + o(1))√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))√2 log n/k, namely approximately √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))√2 log n/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 k × k matrix with asymptotically the same average value (1 + o(1))√2 log n/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 √2 performance gap suffered by both algorithms might be very challenging. Surprisingly, we construct a very simple algorithm which produces a k × k matrix with average value (1 + ok(1) + o(1))(4/3)√2 log n/k for k = o((log n)[superscript 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))α√2 log n/k for a fixed value α ∈ [1, √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 α∗ 52/(33) ≈ 1.3608 . . . ∈ [4/3, √2]: when α < α∗ the space of overlaps is a continuous subset of [0, 1]2, whereas α = α∗ marks the onset of discontinuity, and as a result the model exhibits the Overlap Gap Property (OGP) when α > α∗, appropriately defined. We conjecture that the OGP observed for α > α∗ also marks the onset of the algorithmic hardness—no polynomial time algorithm exists for finding matrices with average value at least (1 + o(1))α√2 log n/k, when α > α∗ and k is a mildly growing function of n. |
| first_indexed | 2024-09-23T10:26:44Z |
| format | Article |
| id | mit-1721.1/120593 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:26:44Z |
| publishDate | 2019 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1205932022-09-30T21:12:09Z Finding a large submatrix of a Gaussian random matrix Gamarnik, David Li, Quan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sloan School of Management Gamarnik, David Li, Quan We consider the problem of finding a k × k submatrix of an n × n 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 × k submatrix is 2(1 + o(1))√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))√2 log n/k, namely approximately √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))√2 log n/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 k × k matrix with asymptotically the same average value (1 + o(1))√2 log n/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 √2 performance gap suffered by both algorithms might be very challenging. Surprisingly, we construct a very simple algorithm which produces a k × k matrix with average value (1 + ok(1) + o(1))(4/3)√2 log n/k for k = o((log n)[superscript 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))α√2 log n/k for a fixed value α ∈ [1, √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 α∗ 52/(33) ≈ 1.3608 . . . ∈ [4/3, √2]: when α < α∗ the space of overlaps is a continuous subset of [0, 1]2, whereas α = α∗ marks the onset of discontinuity, and as a result the model exhibits the Overlap Gap Property (OGP) when α > α∗, appropriately defined. We conjecture that the OGP observed for α > α∗ also marks the onset of the algorithmic hardness—no polynomial time algorithm exists for finding matrices with average value at least (1 + o(1))α√2 log n/k, when α > α∗ and k is a mildly growing function of n. 2019-03-01T17:28:56Z 2019-03-01T17:28:56Z 2018-09 2017-06 2019-02-13T17:55:38Z Article http://purl.org/eprint/type/JournalArticle 0090-5364 http://hdl.handle.net/1721.1/120593 Gamarnik, David and Quan Li. “Finding a Large Submatrix of a Gaussian Random Matrix.” The Annals of Statistics 46, 6A (December 2018): 2511–2561 © 2018 Institute of Mathematical Statistics https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 http://dx.doi.org/10.1214/17-AOS1628 Annals of Statistics Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Gamarnik, David Li, Quan Finding a large submatrix of a Gaussian random matrix |
| title | Finding a large submatrix of a Gaussian random matrix |
| title_full | Finding a large submatrix of a Gaussian random matrix |
| title_fullStr | Finding a large submatrix of a Gaussian random matrix |
| title_full_unstemmed | Finding a large submatrix of a Gaussian random matrix |
| title_short | Finding a large submatrix of a Gaussian random matrix |
| title_sort | finding a large submatrix of a gaussian random matrix |
| url | http://hdl.handle.net/1721.1/120593 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 |
| work_keys_str_mv | AT gamarnikdavid findingalargesubmatrixofagaussianrandommatrix AT liquan findingalargesubmatrixofagaussianrandommatrix |