Metraipolis › archive › dc_ecc7d8a28c4f

RDT based upper bounds on the largest average submatrix values — arXiv:2609.18312

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18312
License (as archived)
CC0-1.0
Archived
2026-10-15T15:42:49.131Z
SHA-256 of the archived text
82c052c7deab5447698ab795745d0d4a36fa62265a0c8425bbaebadb4585f7d4
Stable URL of this page
https://metraipolis.com/documento/dc_ecc7d8a28c4f

How to cite

RDT based upper bounds on the largest average submatrix values — arXiv:2609.18312 — arXiv (en), https://arxiv.org/abs/2609.18312 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ecc7d8a28c4f (Metraipolis archive dc_ecc7d8a28c4f, sha256 82c052c7deab5447698ab795745d0d4a36fa62265a0c8425bbaebadb4585f7d4)
BibTeX
@misc{dcecc7d8a28c4f,
  title = {RDT based upper bounds on the largest average submatrix values — arXiv:2609.18312},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18312},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ecc7d8a28c4f; sha256 82c052c7deab5447698ab795745d0d4a36fa62265a0c8425bbaebadb4585f7d4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18312. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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].

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.ST).
Categorie arXiv: Probability (math.PR) ; Statistical Mechanics (cond-mat.stat-mech); Information Theory (cs.IT); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2609.18312 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T15:08:37.150Z dalla pagina https://arxiv.org/catchup/math.ST/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).