.png){kind=icon}
.png){kind=icon}
Return
Average-Case Matrix Discrepancy: Satisfiability Bounds
.png){kind=icon}
OA
AI
DOI：10.1002/rsa.70033.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a sequence of dx d symmetric matrices {W-i}(n)(i=1), and a margin Delta > 0, we investigate whether it is possible to find signs (epsilon(1),... ,epsilon(n)) E {+/- 1}(n) such that the operator norm of the signed sum satisfies ||I Sigma(n)(i=1)epsilon(i) W-i ||(op) <= Delta. Kunisky and Zhang (2023) recently introduced a random version of this problem, where the matrices {W-i}(n)(i=1) are drawn from the Gaussian orthogonal ensemble. This model can be seen as a random variant of the celebrated Matrix Spencer conjecture and as a matrix-valued analog of the symmetric binary perceptron (SBP) in statistical physics. In this work, we establish a satisfiability transition in this problem as n,d ->infinity with n/d2 ->tau >0. Our main results are twofold. First, we prove that the expected number of solutions with margin Delta = kappa root n has a sharp threshold at a critical tau(1)(kappa): for tautau(1)(kappa) the average number of solutions becomes exponentially large. Second, combining a second-moment method with recent results from Altschuler (2023) on margin concentration in perceptron-type problems, we identify a second threshold tau(2)(kappa), such that for tau>tau(2)(kappa) the problem admits solutions with high probability. In particular, we establish that a system of n=Theta(d(2)) Gaussian random matrices can be balanced so that the spectrum of the resulting matrix macroscopically shrinks compared to the typical semicircle law. Finally, under a technical assumption, we show that there exist values of (tau,kappa) for which the number of solutions has large variance, implying the failure of the second-moment method and uncovering a richer picture than in the vector-analog SBP problem. Our proofs rely on concentration inequalities and large deviation properties for the law of correlated Gaussian matrices under spectral norm constraints.
Keywords:
LARGE DEVIATIONS
INTEGRALS
SPACE
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.