English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the problem of finding a $k\times k$ submatrix of an $n\times n$matrix with i.i.d. standard Gaussian entries, which has a large average entry.It was shown earlier by Bhamidi et al. that the largest average value of such amatrix is $2\sqrt{\log n/k}$ with high probability. In the same paper anevidence was provided that a natural greedy algorithm called Largest AverageSubmatrix ($\LAS$) should produce a matrix with average entry approximately$\sqrt{2}$ smaller.  In this paper we show that the matrix produced by the $\LAS$ algorithm isindeed $\sqrt{2\log n/k}$ w.h.p. Then by drawing an analogy with the problem offinding cliques in random graphs, we propose a simple greedy algorithm whichproduces a $k\times k$ matrix with asymptotically the same average value. Sincethe greedy algorithm is the best known algorithm for finding cliques in randomgraphs, it is tempting to believe that beating the factor $\sqrt{2}$performance gap suffered by both algorithms might be very challenging.Surprisingly, we show the existence of a very simple algorithm which produces amatrix with average value $(4/3)\sqrt{2\log n/k}$.  To get an insight into the algorithmic hardness of this problem, andmotivated by methods originating in the theory of spin glasses, we conduct theso-called expected overlap analysis of matrices with average valueasymptotically $\alpha\sqrt{2\log n/k}$. The overlap corresponds to the numberof common rows and common columns for pairs of matrices achieving this value.We discover numerically an intriguing phase transition at $\alpha^*\approx1.3608..$: when $\alpha<\alpha^*$ the space of overlaps is a continuous subsetof $[0,1]^2$, whereas $\alpha=\alpha^*$ marks the onset of discontinuity, andthe model exhibits the Overlap Gap Property when $\alpha>\alpha^*$. Weconjecture that $\alpha>\alpha^*$ marks the onset of the algorithmic hardness.

Finding a Large Submatrix of a Gaussian Random Matrix