Finding a large submatrix of a Gaussian random matrix

DOI10.1214/17-AOS1628zbMath1401.68120arXiv1602.08529OpenAlexW2963892825MaRDI QIDQ1991667

Quan Li, David Gamarnik

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

zbMATH Keywords

computational complexityrandom graphsrandom matrixmaximum cliqueoverlap gap propertysubmatrix detection

Mathematics Subject Classification ID

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

Related Items (6)

Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Optimizing mean field spin glasses with external field ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ The overlap gap property in principal submatrix recovery

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal detection of sparse principal components in high dimension
• Finding one community in a sparse graph
• Finding large average submatrices in high dimensional data
• Extremes and related properties of random sequences and processes
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• On independent sets in random graphs
• Limits of local algorithms over sparse random graphs
• On the solution‐space geometry of random constraint satisfaction problems

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