no. 16 · Tuesday 17 November 2026
Random matrix discrepancy -- CLuP algorithm and parametric RDT approach
Abstract
We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime. The problem amounts to finding $κ=\min_{\x\in\mB^n}\|\sum_{i=1}^{n}\bar{A}_i\x_i\|_2$, where $\bar{A}_i\in\mR^{d\times d}$ is a collection of $n$ iid GOE matrices, $\mB^n$ are vertices of the unit cube in $\mR^n$, and $α=\lim_{n\rightarrow \infty}\frac{n}{d^2}$ 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,\infty)$ range [1,2,14,31,51,92,111].
- fields
- Information Theory, Probability