Optimality of Spectral Methods for Ranking, Community Detections and Beyond

Abstract: Spectral methods have been widely used for a large class of challenging problems, ranging from top-K ranking via pairwise comparisons, community detection, factor analysis, among others.
Analyses of these spectral methods require super-norm perturbation analysis of top eigenvectors. This allows us to UNIFORMLY approximate elements in eigenvectors by linear functions of the observed random matrix that can be analyzed further. We first establish such an infinity-norm pertubation bound for top eigenvectors and apply the idea to several challenging problems such as top-K ranking, community detections, Z_2-syncronization and matrix completion. We show that the spectral methods are indeed optimal for these problems. We illustrate these methods via simulations.
(Based on joint work with Emmanuel Abbe, Kaizheng Wang, Yiqiao Zhong and that of Yixin Chen, Cong Ma and Kaizheng Wang)

Biography: Jianqing Fan is Frederick L. Moore Professor at Princeton University.  After receiving his Ph.D. from the University of California at Berkeley, he has been appointed as assistant, associate, and full professor at the University of North Carolina at Chapel Hill (1989-2003), professor at the University of California at Los Angeles (1997-2000), and professor at the Princeton University (2003–).  He was the past president of the Institute of Mathematical Statistics and International Chinese Statistical Association. He is co-editing  Journal of Econometrics and was the co-editor of The Annals of Statistics,  Probability Theory and Related Fields and Econometrics Journal.    His published work on statistics, economics, finance, and computational biology has been recognized by The 2000 COPSS Presidents’ Award, The 2007 Morningside Gold Medal of Applied Mathematics, Guggenheim Fellow, P.L. Hsu Prize, Royal Statistical Society Guy medal in silver, and election to Academician of Academia Sinica and follow of American Associations for Advancement of Science.