The ᵣ-Levy-Grothendieck problem and r→ p norms of Levy matrices

Given an n× n matrix Aₙ and 1≤ r, p ≤∞, consider the following quadratic optimization problem referred to as the ᵣ-Grothendieck problem: {align}M_r(A_n)maxx^n:\|x\|_r≤1x^{} A_n x,{align} as well as the r→ p operator norm of the matrix Aₙ, defined as {align}\|A_n\|r → p x^n:\|x\|_r ≤ 1\|A_n x\|_p,{align} where \|x\|ᵣ denotes the ᵣ-norm of the vector x. This work analyzes high-dimensional asymptotics of these quantities when Aₙ are symmetric random matrices with independent and identically distributed heavy-tailed upper-triangular entries with index α. When 1≤ r≤ 2 (respectively, 1≤ r≤ p) and α∈(0,2), suitably scaled versions of Mᵣ(Aₙ) and \|Aₙ\|r→ p are shown to converge to a Fr\'echet distribution as n→∞. In contrast, when 2< r<∞ (respectively, 1≤ p< r), it is shown that there exists α_*∈(1,2) such that for every α∈(0,α_*), suitably scaled versions of Mᵣ(Aₙ) and \|Aₙ\|r→ p converge to the power of a stable distribution. Furthermore, it is shown that there exists α_*>α_* such that when α∈(α_*,α_*), the latter convergence result holds only when the matrix entries are centered; when the entries have non-zero mean, a different limit arises after additional centering and scaling. As a corollary, these results yield a characterization of the limiting ground state of the Levy spin glass when α ∈ (0,1). The analysis uses a combination of tools from the theory of heavy-tailed distributions, the nonlinear power method and concentration inequalities.