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

DOI10.1007/S00440-017-0766-0MaRDI QIDQ2363657zbMATH OpenOpenAlexFDO

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

Publication date 25 July 2017

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

central limit theoremextreme value theoryStein's methodGaussian random matricesenergy landscape

Mathematics Subject Classification ID

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

Abstract: The problem of finding large average submatrices of a real-valued matrix arises in the exploratory analysis of data from a variety of disciplines, ranging from genomics to social sciences. In this paper we provide a detailed asymptotic analysis of large average submatrices of an $nimesn$ Gaussian random matrix. The first part of the paper addresses global maxima. For fixed $k$ we identify the average and the joint distribution of the $kimesk$ submatrix having largest average value. As a dual result, we establish that the size of the largest square sub-matrix with average bigger than a fixed positive constant is, with high probability, equal to one of two consecutive integers that depend on the threshold and the matrix dimension $n$. The second part of the paper addresses local maxima. Specifically we consider submatrices with dominant row and column sums that arise as the local optima of iterative search procedures for large average submatrices. For fixed $k$, we identify the limiting average value and joint distribution of a $kimesk$ submatrix conditioned to be a local maxima. In order to understand the density of such local optima and explain the quick convergence of such iterative procedures, we analyze the number $L_n(k)$ of local maxima, beginning with exact asymptotic expressions for the mean and fluctuation behavior of $L_n(k)$. For fixed $k$, the mean of $L_n(k)$ is $Theta(n^k/(logn{)}^{(k-1)/2})$ while the standard deviation is $Theta(n^{2k^2/(k+1)}/(logn{)}^{k^2/(k+1)})$. Our principal result is a Gaussian central limit theorem for $L_n(k)$ that is based on a new variant of Stein's method.

Recommendations

• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• Finding a large submatrix of a Gaussian random matrix
• Distribution-free, size adaptive submatrix detection with acceleration
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Sampling from large matrices

Cites work

• scientific article; zbMATH DE number 4155658 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1303602 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• scientific article; zbMATH DE number 2172364 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A normal comparison inequality and its applications
• An Introduction to Stein's Method
• Bounds on the Bivariate Normal Distribution Function
• Cliques in random graphs
• Combinatorial landscapes
• Convergence in law of the minimum of a branching random walk
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Detection of an anomalous cluster in a network
• Dynamic programming optimization over random data: the scaling exponent for near-optimal solutions
• Estimating some features of \(NK\) fitness landscapes.
• Extremes and related properties of random sequences and processes
• Finding hidden cliques in linear time with high probability
• Finding large average submatrices in high dimensional data
• Fundamentals of Stein's method
• Information, Physics, and Computation
• Large Cliques Elude the Metropolis Process
• Limit Theorems for the Maximum Term in Stationary Sequences
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• More rigorous results on the Kauffman-Levin model of evolution.
• On combinatorial testing problems
• On the Distribution of the Maximum of Random Variables
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Random graphs.
• Randomized Algorithms for Matrices and Data
• Recovering block-structured activations using compressive measurements
• Rigorous results for the NK model.
• Searching for a trail of evidence in a maze
• The two possible values of the chromatic number of a random graph

Cited in

(8)

• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Finding a large submatrix of a Gaussian random matrix
• Computational barriers in minimax submatrix detection
• On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
• On the energy landscape of the mixed even \(p\)-spin model
• Statistical mechanics of the maximum-average submatrix problem
• Distribution-free, size adaptive submatrix detection with acceleration
• The overlap gap property in principal submatrix recovery

Describes a project that uses

Uses Software

• LAS

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

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