Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms

2025/07/25 by Shankar Bhamidi, David Gamarnik, Bhamidi, Shankar +3 · 1 citation
Computer Science · Mathematics · #62G32 60G70 #68Q17 #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2507.19259

openalex publication_date 2025/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \citesmadeira-survey,shabalin2009finding and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor 4\over 3√(2) for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \citehuang2025tight. We further extend our results to (\mathbb Rⁿ)^{⊗ p} tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be 2√(p)/(1+p).

Citations

• Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Optimal Hardness of Online Algorithms for Large Independent Sets
• The Algorithmic Phase Transition of Random Graph Alignment Problem
• Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• Latent Association Mining in Binary Data
• Finding a Large Submatrix of a Gaussian Random Matrix
• A testing-based approach to the discovery of differentially correlated variable sets
• Energy Landscape for large average submatrix detection problems in\n Gaussian random matrices

Cited by

• Sharp Online Hardness for Large Balanced Independent Sets

Related

• Finding a Large Submatrix of a Gaussian Random Matrix
• Energy Landscape for large average submatrix detection problems in\n Gaussian random matrices
• Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy
• Submatrices with non-uniformly selected random supports and insights\n into sparse approximation
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties