For an $ntimes n$ matrix $A_n$, the $rto p$ operator norm is defined as $$|A_n|_{rto p}:= sup_{boldsymbol{x} in mathbb{R}^n:|boldsymbol{x}|_rleq 1 } |A_nboldsymbol{x}|_pquadtext{for}quad r,pgeq 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 finding oblivious routing schemes in transportation networks. This article considers $rto p$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of ErdH{o}s-Renyi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1< pleq r< infty$, the asymptotic normality, as $ntoinfty$, of the appropriately centered and scaled norm $|A_n|_{rto p}$ is established. When $p geq 2$, this is shown to imply, as a corollary, 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|_{rto p}$ 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< pleq r < 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.
Download