Energy landscape for large average submatrix detection problems in Gaussian random matrices

DOI10.1007/s00440-017-0766-0zbMath1371.60010arXiv1211.2284OpenAlexW1870355844MaRDI QIDQ2363657

Partha S. Dey, Shankar Bhamidi, Andrew B. Nobel

Publication date: 25 July 2017

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.2284

zbMATH Keywords

Stein's methodcentral limit theoremenergy landscapeGaussian random matricesextreme value theory

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Extreme value theory; extremal stochastic processes (60G70) Combinatorial probability (60C05)

Related Items (5)

On the energy landscape of the mixed even \(p\)-spin model ⋮ Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time ⋮ Finding a large submatrix of a Gaussian random matrix ⋮ The overlap gap property in principal submatrix recovery ⋮ Computational barriers in minimax submatrix detection

Uses Software

• LAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergence in law of the minimum of a branching random walk
• Fundamentals of Stein's method
• On combinatorial testing problems
• Searching for a trail of evidence in a maze
• Finding large average submatrices in high dimensional data
• Extremes and related properties of random sequences and processes
• Rigorous results for the NK model.
• A normal comparison inequality and its applications
• Estimating some features of \(NK\) fitness landscapes.
• More rigorous results on the Kauffman-Levin model of evolution.
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Local algorithms for independent sets are half-optimal
• Recovering block-structured activations using compressive measurements
• Detection of an anomalous cluster in a network
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Combinatorial Landscapes
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Randomized Algorithms for Matrices and Data
• Bounds on the Bivariate Normal Distribution Function
• Information, Physics, and Computation
• Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions
• Large Cliques Elude the Metropolis Process
• Cliques in random graphs
• An Introduction to Stein's Method
• Finding Hidden Cliques in Linear Time with High Probability
• On the Distribution of the Maximum of Random Variables
• Limit Theorems for the Maximum Term in Stationary Sequences
• Limits of local algorithms over sparse random graphs
• The two possible values of the chromatic number of a random graph

This page was built for publication: Energy landscape for large average submatrix detection problems in Gaussian random matrices