RDT based upper bounds on the largest average submatrix values
Abstract
We study statistical variants of the classical largest average submatrix problem. For small submatrices (where the dimension is less than linearly proportional to the original matrix), the problem is typically well understood and believed to exhibit the statistical-computational gap (SCG). However, analytical treatment of both the information-theoretic and algorithmic aspects of the linear regime remains challenging, and no mathematically rigorous results have yet arrived anywhere close to proving or disproving SCG existence in this setting. Focusing on the linear regime, we make strong progress in several key directions: 1) We develop a generic Random Duality Theory (RDT) framework to characterize largest average submatrix values. 2) Using the plain RDT variant, we obtain closed-form upper bounds as explicit functions of dimensionality proportionality parameters. 3) We demonstrate that a lifted RDT variant strictly improves upon the plain RDT within a certain linear range of submatrix dimensions. 4) For small submatrices where the dimensional proportionality constants approach zero, we prove that our results match both the replica results from [34] (obtained via one-step replica symmetry breaking) and the sublinear results from [18,45].
Related
- New upper bounds for average kissing numbers
- Upper bounds for arithmetic functions over polynomial values via Chebotarev--Sato--Tate distributions
- On the monotonicity of average singular values of complex Gaussian random matrices
- Dimension Monotonicity in Laguerre Ensembles II: Average Singular Values and the Rectangularity Transition in the Orthogonal Case
- Improved average and almost-all bounds for G(n)
BibTeX
@misc{stojnic2026based,
title = {{RDT based upper bounds on the largest average submatrix values}},
author = {Mihailo Stojnic},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18312},
eprint = {2609.18312},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18312},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - RDT based upper bounds on the largest average submatrix values
AU - Mihailo Stojnic
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18312
UR - https://arxiv.org/abs/2609.18312
AB - We study statistical variants of the classical largest average submatrix problem. For small submatrices (where the dimension is less than linearly proportional to the original matrix), the problem is typically well understood and believed to exhibit the statistical-computational gap (SCG). However, analytical treatment of both the information-theoretic and algorithmic aspects of the linear regime remains challenging, and no mathematically rigorous results have yet arrived anywhere close to proving or disproving SCG existence in this setting. Focusing on the linear regime, we make strong progress in several key directions: 1) We develop a generic Random Duality Theory (RDT) framework to characterize largest average submatrix values. 2) Using the plain RDT variant, we obtain closed-form upper bounds as explicit functions of dimensionality proportionality parameters. 3) We demonstrate that a lifted RDT variant strictly improves upon the plain RDT within a certain linear range of submatrix dimensions. 4) For small submatrices where the dimensional proportionality constants approach zero, we prove that our results match both the replica results from [34] (obtained via one-step replica symmetry breaking) and the sublinear results from [18,45].
ER -