- 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.edu – https://sites.google.com/site/debankurm/
- Organizer
- He Guo
For an n×n matrix An, the r→p operator norm is defined as ‖An‖r→p=sup‖x‖r≤1‖Anx‖p for r,p≥1. The r→p 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 r→p 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<p≤r<∞, we establish the asymptotic normality of the appropriately centered and scaled ‖An‖r→p, 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.).