Asymptotic normality of the $r\to p$ norm for random matrices with non-negative entries

Series
ACO Student Seminar
Time
Friday, November 1, 2019 - 1:05pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Debankur Mukherjee – ISyE, Georgia Tech – debankur.mukherjee@isye.gatech.eduhttps://sites.google.com/site/debankurm/
Organizer
He Guo

For an n×n matrix An, the rp operator norm is defined as Anrp=supxr1Anxp for r,p1. The rp operator norm puts a huge number of important quantities of interest in diverse disciplines under a single unified framework. The application of this norm spans a broad spectrum of areas including data-dimensionality reduction in machine learning, finding oblivious routing schemes in transportation network, and matrix condition number estimation.

 

In this talk, we will consider the rp norm of a class of symmetric random matrices with nonnegative entries, which includes the adjacency matrices of the Erd\H{o}s-R\'enyi random graphs and matrices with sub-Gaussian entries. For 1<pr<, we establish the asymptotic normality of the appropriately centered and scaled Anrp, as n. The special case r=p=2, which corresponds to the largest singular value of matrices, was proved in a seminal paper by F\"uredi and Koml\'os (1981). Of independent interest, we further obtain a sharp -approximation for the maximizer vector. The results also hold for sparse matrices and further the -approximation for the maximizer vector also holds for a broad class of deterministic sequence of matrices with certain asymptotic `expansion' properties.

 

This is based on a joint work with Souvik Dhara (MIT) and Kavita Ramanan (Brown U.).