Tony Cai：Statistical and Computational Limits for Submatrix Localization and Sparse Matrix Detection

Abstract：In the conventional statistical framework, the goal is developing optimal inference procedures, where optimality is understood with respect to the sample size and parameter space. When the dimensionality of the data becomes large as in many contemporary applications, the computational concerns associated with the statistical procedures come to the forefront. A fundamental question is: Is there a price to pay for statistical performance if one only considers computable (polynomial-time) procedures? After all, statistical methods are useful in practice only if they can be computed within a reasonable amount of time. 

In this talk, we discuss the interplay between statistical accuracy and computational efficiency in two specific problems: submatrix localization and sparse matrix detection based on a noisy observation of a large matrix. The results show some interesting phenomena that are quite different from other high-dimensional problems studied in the literature.   

Tony Cai教授，美国宾夕法尼亚大学沃顿商学院Dorothy Silberberg统计学讲席教授、副院长，兼任该校应用数学及计算科学教授，曾任《Annals of Statistics》主编(2010-2012)。主要研究领域包括高维统计推断，大范围假设检验，非参数函数估计，函数数据分析，小波方法和应用，统计决策论等，已在统计学四大国际顶级期刊Annals of Statistics, JASA, JRSSB, Biometrika上发表文章80余篇；2008年，荣获COPSS总统奖（国际统计学领域最高奖项）。