On r-to-p norms of random matrices with nonnegative entries: Asymptotic normality and \ell_\infty-bounds for the maximizer

arXiv2005.14056MaRDI QIDQ6503979FDOQ6503979

Authors: Souvik Dhara, Debankur Mukherjee, Kavita Ramanan 

Abstract: For an $nimesn$ matrix $A_n$, the $rop$ operator norm is defined as ${\displaystyle }$|A_n|_{r o p}:= sup_{�oldsymbol{x} in mathbb{R}^n:|�oldsymbol{x}|_rleq 1 } |A_n�oldsymbol{x}|_pquad ext{for}quad r,pgeq 1.${\displaystyle }$ 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 finding oblivious routing schemes in transportation networks. This article considers $rop$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of ErdH{o}s-R'enyi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1<pleqr<infty$, the asymptotic normality, as $noinfty$, of the appropriately centered and scaled norm $|A_n{|}_{rop}$ is established. When $pgeq2$, this is shown to imply, as a corollary, asymptotic normality of the solution to the $el{l}_p$ quadratic maximization problem, also known as the $el{l}_p$ Grothendieck problem. Furthermore, a sharp $el{l}_{i}nfty$-approximation bound for the unique maximizing vector in the definition of $|A_n{|}_{rop}$ is obtained. This result, which may be of independent interest, 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"{u}redi and Koml'{o}s (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices, which corresponds to the special case $r=p=2$ considered here. In the general case with $1<pleqr<infty$, spectral methods are no longer applicable, and so a new approach is developed, which involves a refined convergence analysis of a nonlinear power method and a perturbation bound on the maximizing vector.

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

This page was built for publication: On $r$-to-$p$ norms of random matrices with nonnegative entries: Asymptotic normality and $\ell_\infty$-bounds for the maximizer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6503979)