The ${\mathrm{\ell }}_r$-Levy-Grothendieck problem and $r\to p$ norms of Levy matrices

Given an $n\times n$ matrix $A_n$ and $1\le r,p\le \mathrm{\infty }$, consider the following quadratic optimization problem referred to as the ${\mathrm{\ell }}_r$-Grothendieck problem: \begin{align}M_r(A_n)\coloneqq\max_{\boldsymbol{x}\in$\mathbb{R}$^n:|\boldsymbol{x}|r\leq1}\boldsymbol{x}^{\top} A_n \boldsymbol{x},\end{align} as well as the $r\to p$ operator norm of the matrix $A_n$, defined as \begin{align}|A_n|{r \rightarrow p}\coloneqq \sup _{\boldsymbol{x}\in$\mathbb{R}$^n:|\boldsymbol{x}|_r \leq 1}|A_n \boldsymbol{x}|_p,\end{align} where $\mathrm{\parallel }\mathit{x}{\mathrm{\parallel }}_r$ denotes the ${\mathrm{\ell }}_r$-norm of the vector $\mathit{x}$. This work analyzes high-dimensional asymptotics of these quantities when $A_n$ are symmetric random matrices with independent and identically distributed heavy-tailed upper-triangular entries with index $\alpha$. When $1\le r\le 2$ (respectively, $1\le r\le p$) and $\alpha \in (0,2)$, suitably scaled versions of $M_r(A_n)$ and $\mathrm{\parallel }{A}_n{\mathrm{\parallel }}_{r\to p}$ are shown to converge to a Fréchet distribution as $n\to \mathrm{\infty }$. In contrast, when $2<r<\mathrm{\infty }$ (respectively, $1\le p<r$), it is shown that there exists ${\alpha }_{\ast }\in (1,2)$ such that for every $\alpha \in (0,{\alpha }_{\ast })$, suitably scaled versions of $M_r(A_n)$ and $\mathrm{\parallel }{A}_n{\mathrm{\parallel }}_{r\to p}$ converge to the power of a stable distribution. Furthermore, it is shown that there exists ${\bar{\alpha }}_{\ast }>{\alpha }_{\ast }$ such that when $\alpha \in ({\alpha }_{\ast },{\bar{\alpha }}_{\ast })$, 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 $\alpha \in (0,1)$. The analysis uses a combination of tools from the theory of heavy-tailed distributions, the nonlinear power method and concentration inequalities.