Finding a large submatrix of a Gaussian random matrix

DOI10.1214/17-AOS1628MaRDI QIDQ1991667zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Quan Li

Publication date 30 October 2018

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08529, https://projecteuclid.org/euclid.aos/1536307224

zbMATH Keywords

computational complexitymaximum cliqueoverlap gap propertyrandom graphsrandom matrixsubmatrix detection

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We consider the problem of finding a $kimesk$ submatrix of an $nimesn$ 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 a matrix is $2sqrtlogn/k$ with high probability. In the same paper an evidence was provided that a natural greedy algorithm called Largest Average Submatrix ($LAS$) should produce a matrix with average entry approximately $sqrt2$ smaller. In this paper we show that the matrix produced by the $LAS$ algorithm is indeed $sqrt2logn/k$ w.h.p. Then by drawing an analogy with the problem of finding cliques in random graphs, we propose a simple greedy algorithm which produces a $kimesk$ matrix with asymptotically the same average value. Since the greedy algorithm is the best known algorithm for finding cliques in random graphs, it is tempting to believe that beating the factor $sqrt2$ performance gap suffered by both algorithms might be very challenging. Surprisingly, we show the existence of a very simple algorithm which produces a matrix with average value $(4/3)sqrt2logn/k$. 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 $alphasqrt2logn/k$. The overlap corresponds to the number of common rows and common columns for pairs of matrices achieving this value. We discover numerically an intriguing phase transition at $alph{a}^{\ast }approx\mathrm{1.3608..}$: when $alpha<alph{a}^{\ast }$ the space of overlaps is a continuous subset of $[0,1{]}^2$, whereas $alpha=alph{a}^{\ast }$ marks the onset of discontinuity, and the model exhibits the Overlap Gap Property when $alpha>alph{a}^{\ast }$. We conjecture that $alpha>alph{a}^{\ast }$ marks the onset of the algorithmic hardness.

Recommendations

• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• The overlap gap property in principal submatrix recovery
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Finding dense subgraphs in \(G(n,1/2)\)
• Sampling from large matrices

Cites work

• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Extremes and related properties of random sequences and processes
• Finding large average submatrices in high dimensional data
• Finding one community in a sparse graph
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Limits of local algorithms over sparse random graphs
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• On the solution-space geometry of random constraint satisfaction problems
• Optimal detection of sparse principal components in high dimension

Cited in

(16)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• The overlap gap property in principal submatrix recovery
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• scientific article; zbMATH DE number 721906 (Why is no real title available?)
• Algorithmic obstructions in the random number partitioning problem
• Optimizing mean field spin glasses with external field
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Statistical mechanics of the maximum-average submatrix problem
• Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
• Principal minors of Gaussian orthogonal ensemble
• Limits of sequential local algorithms on the random k-XORSAT problem
• The algorithmic phase transition of random graph alignment problem
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties

Describes a project that uses

Uses Software

• LAS

This page was built for publication: Finding a large submatrix of a Gaussian random matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1991667)