Random duality theory advances largest average submatrix analysis in linear settings
RDT based upper bounds on the largest average submatrix values
Information Theory
Summary
Finding the largest average in a submatrix of data is a useful but tricky math problem, especially when the submatrix size scales linearly with the whole matrix. The authors introduce a new mathematical framework called Random Duality Theory to better understand this problem in the linear regime. They provide explicit formulas that give upper limits on these largest averages and show improvements over earlier methods in certain cases. For very small submatrices, their results agree with previous advanced theoretical predictions, helping to bridge gaps between different approaches.
What this means in practice
- •For data scientists: Determine theoretical limits on data subset averages to guide algorithm design for large matrix analysis.
- •For machine learning engineers: Use refined upper bounds on submatrix averages to evaluate feasibility and efficiency of feature extraction methods.
A theory result. No direct application yet.
Authors
Mihailo Stojnic
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].