论文标题
在$ r $ -to-to-p $ p $带有非负条目的随机矩阵规范：渐近态性和$ \ ell_ \ infty $ bounds for the Maximizer
On $r$-to-$p$ norms of random matrices with nonnegative entries: Asymptotic normality and $\ell_\infty$-bounds for the maximizer
论文作者
论文摘要
对于$ n \ times n $ matrix $ a_n $，$ r \ to p $运算符规范定义为$$ \ | a_n \ | _ {r \ to p}：= \ sup _ {\ sup _ {\ sup _ {\ mathbf {x} \ in \ in \ mathbb {r}^n： \ | a_n \ Mathbf {X} \ | _p \ Quad \ text {for} \ Quad} \ quad r，p \ geq1。$$对于$ r $和$ p $的不同选择，此规范对应于在多种应用程序中产生的密钥数量，包括在多个应用程序中出现的多个应用程序编号估算，包括矩阵数量估算，构建构建和构建schem in oblivious schem schem oblevious schem schem schem schem in oplavious schem schem schem schem schem in oblevious schem schem schem schem。本文认为$ r \ to p $具有非负条目的对称随机矩阵的规范，包括Erdős-rényi随机图的邻接矩阵，具有正高斯次级入口的矩阵以及某些稀疏的矩阵。对于$ 1 <p \ leq r <\ infty $，确定了适当的中心和缩放norm $ \ | a_n \ | _ {r \ to p} $的适当中心和缩放norm $ \ | a_n \ | a_n \ | a_n \ |当$ p \ geq 2 $时，这表明解决方案对$ \ ell_p $二次最大化问题的渐变性，也称为$ \ ell_p $ grothendieck问题。此外，在定义$ \ | a_n \ | _ {r \ to p} $的定义中，最大化矢量的尖锐$ \ ell_ \ iffty $ - approximation将获得最大化的矢量，并且可以将其视为最大值的Maximimizer在Maximimizer下与Maximimizer在Maximimizer中的随机态度均与Mattrix的最大态度相关的结果。实际上，该结果表明具有具有某些渐近扩展特性的矩阵的一类确定性序列。获得的结果可以看作是Füredi和Komlós（1981）对一类对称随机矩阵的最大奇异值的渐近正态性的开创性结果的概括。在$ 1 <p \ leq r <\ infty $的一般情况下，光谱方法不再适用，因此开发了一种新方法，涉及对非线性功率方法的精制收敛分析和最大化载体的扰动，这可能是独立的。
For an $n\times n$ matrix $A_n$, the $r\to p$ operator norm is defined as $$\|A_n\|_{r\to p}:= \sup_{\mathbf{x}\in\mathbb{R}^n:\|\mathbf{x} \|_r\leq 1 } \|A_n\mathbf{x} \|_p\quad\text{for}\quad r,p\geq 1.$$ For different choices of $r$ and $p$, this norm corresponds to key quantities that arise in diverse applications including matrix condition number estimation, clustering of data, and construction of oblivious routing schemes in transportation networks. This article considers $r\to p$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of Erdős-Rényi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1<p\leq r<\infty$, the asymptotic normality, as $n\to\infty$, of the appropriately centered and scaled norm $\|A_n\|_{r\to p}$ is established. When $p \geq 2$, this is shown to imply asymptotic normality of the solution to the $\ell_p$ quadratic maximization problem, also known as the $\ell_p$ Grothendieck problem. Furthermore, a sharp $\ell_\infty$-approximation bound for the unique maximizing vector in the definition of $\|A_n\|_{r\to p}$ is obtained, and may be viewed as an $\ell_\infty$-stability result of the maximizer under random perturbations of the matrix with mean entries. This result is in fact shown to hold for a broad class of deterministic sequences of matrices having certain asymptotic expansion properties. The results obtained can be viewed as a generalization of the seminal results of Füredi and Komlós (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices. In the general case with $1<p\leq r< \infty$, spectral methods are no longer applicable, and so a new approach is developed involving a refined convergence analysis of a nonlinear power method and a perturbation bound on the maximizing vector, which may be of independent interest.
