The $\ell_r$-Levy-Grothendieck problem and $r\rightarrow p$ norms of Levy matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913333673721856 |
|---|---|
| author | Ramanan, Kavita Xie, Xiaoyu |
| author_facet | Ramanan, Kavita Xie, Xiaoyu |
| contents | Given an $n\times n$ matrix $A_n$ and $1\leq r, p \leq\infty$, consider the following quadratic optimization problem referred to as the $\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\rightarrow 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 $\|\boldsymbol{x}\|_r$ denotes the $\ell_r$-norm of the vector $\boldsymbol{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 $α$. When $1\leq r\leq 2$ (respectively, $1\leq r\leq p$) and $α\in(0,2)$, suitably scaled versions of $M_r(A_n)$ and $\|A_n\|_{r\rightarrow p}$ are shown to converge to a Fréchet distribution as $n\rightarrow\infty$. In contrast, when $2< r<\infty$ (respectively, $1\leq p< r$), it is shown that there exists $α_*\in(1,2)$ such that for every $α\in(0,α_*)$, suitably scaled versions of $M_r(A_n)$ and $\|A_n\|_{r\rightarrow p}$ converge to the power of a stable distribution. Furthermore, it is shown that there exists $\barα_*>α_*$ such that when $α\in(α_*,\barα_*)$, 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 $α\in (0,1)$. The analysis uses a combination of tools from the theory of heavy-tailed distributions, the nonlinear power method and concentration inequalities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18299 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The $\ell_r$-Levy-Grothendieck problem and $r\rightarrow p$ norms of Levy matrices Ramanan, Kavita Xie, Xiaoyu Probability Primary: 60B20, 60E07, Secondary: 60F05, 15A60, 46B09 Given an $n\times n$ matrix $A_n$ and $1\leq r, p \leq\infty$, consider the following quadratic optimization problem referred to as the $\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\rightarrow 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 $\|\boldsymbol{x}\|_r$ denotes the $\ell_r$-norm of the vector $\boldsymbol{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 $α$. When $1\leq r\leq 2$ (respectively, $1\leq r\leq p$) and $α\in(0,2)$, suitably scaled versions of $M_r(A_n)$ and $\|A_n\|_{r\rightarrow p}$ are shown to converge to a Fréchet distribution as $n\rightarrow\infty$. In contrast, when $2< r<\infty$ (respectively, $1\leq p< r$), it is shown that there exists $α_*\in(1,2)$ such that for every $α\in(0,α_*)$, suitably scaled versions of $M_r(A_n)$ and $\|A_n\|_{r\rightarrow p}$ converge to the power of a stable distribution. Furthermore, it is shown that there exists $\barα_*>α_*$ such that when $α\in(α_*,\barα_*)$, 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 $α\in (0,1)$. The analysis uses a combination of tools from the theory of heavy-tailed distributions, the nonlinear power method and concentration inequalities. |
| title | The $\ell_r$-Levy-Grothendieck problem and $r\rightarrow p$ norms of Levy matrices |
| topic | Probability Primary: 60B20, 60E07, Secondary: 60F05, 15A60, 46B09 |
| url | https://arxiv.org/abs/2404.18299 |