EVENT DETAILS AND ABSTRACT

Title: The r-to-p norm of non-negative random matrices
Speaker: Souvik Dhara
Speaker Info: MIT
Brief Description:
Special Note:
Abstract:

For an n\times n matrix A_n, the r\to p operator norm is defined as \|A_n\|_{r\to p}:= \sup_{x \in \mathbb{R}^n:\|x\|_r\leq 1 } \|A_n\|_p\quad\mbox{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 finding oblivious routing schemes in transportation networks. This talk considers r\to p norms of symmetric random matrices with nonnegative entries, including adjacency matrices of Erd\H{o}s-R\'enyi 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. Furthermore, a sharp \ell_\infty-approximation for the unique maximizing vector in the definition of \|A_n\|_{r\to p} is obtained, which may be of independent interest. In fact, the vector approximation result is shown to hold for a broad class of deterministic sequence 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< p\leq r < \infty, the spectral methods are no longer applicable, which requires a new approach, involving a refined convergence analysis of a nonlinear power method and establishing a perturbation bound on the maximizing vector.

This is based on a joint work with Debankur Mukherjee (Georgia Tech) and Kavita Ramanan (Brown University).