Random matrix discrepancy -- CLuP algorithm and parametric RDT approach

arXiv:2611.18650 · cond-mat.dis-nn, cs.IT, cs.LG, math.IT, math.PR · Submitted 2026-10-15 · Read on arXiv

cond-mat.dis-nn, cs.IT, cs.LG, math.IT, math.PR

Submitted: 2026-10-15

Updated: 2026-10-15

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime.

Abstract

We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime. The problem amounts to finding κ= in n| sum from i=1 to n A bar i i| 2, where A bar i in d times d is a collection of n iid GOE matrices, n are vertices of the unit cube in n, and α= n to infinity n over d squared is a proportionality constant. Strong progress is made in several directions: (i) We develop a Random duality theory (RDT) framework and utilize its a lifted variant to establish lower bounds on κ, which precisely match the bounds obtained via the first moment in [81]. (ii) To address analytical challenges, we propose a negative Hopfield model as a proxy for implementation of a fully lifted RDT. On the 2nd lifting level, this model fits remarkably well between the information-theoretic lower bounds from [81] and the algorithmic upper bounds from [38]. (iii) On the 3rd and 4th lifting levels, parametric RDT concepts predict a sizeable computational gap for lower κ values in the proxy model. Extending proxy information-theoretic fitting to algorithmic suggests a similar computational gap for matrix discrepancy in low κ regime, aligning with [73]. (iv) We design a Controlled Loosening Up (CLuP) algorithm for matrix discrepancy. Its performance strongly matches our analytical results -- closely approaching information-theoretic predictions in lower α ranges (indicating a small or nonexistent computational gap) and following the proxy model's algorithmic predictions in higher α ranges (indicating a sizeable computational gap). Both the information-theoretic and algorithmic predictions match the corresponding phenomenologies of the symmetric binary perceptron (SBP) vector analogue in the entire α in(0, infinity) range [1,2,14,31,51,92,111].

Related papers