The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Optimal detection of a sparse principal component

Philippe Rigollet, Asst. Professor, Princeton University

Date and Time: Oct 31, 2012 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Sparse Principal Component Analysis (SPCA) is a remarkably useful tool for practitioners who had been relying on ad-hoc thresholding methods. Our analysis aims at providing a a framework to test whether the data at hand indeed contains a sparse principal component. More precisely we propose an optimal test procedure to detect the presence of a sparse principal component in a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels and performs very well on simulated datasets. Moreover, we exhibit some evidence from average case complexity that this slight deterioration may be unavoidable.

Philippe Rigollet received his Ph.D. in mathematics from University Paris 6 where he studied in the Laboratoire de Probabilites under the supervision of Alexandre Tsybakov. He then moved to Georgia Tech as a Post-Doc working with Vladimir Koltchinskii in the School of Mathematics. In 2008, he joined the faculty in the department of Operations Research and Financial Engineering at Princeton University as an assistant professor. He received a Berkeley-France fund in 2006 and an NSF CAREER award in 2011.
Philippe has developed new tools for the theory of aggregation, which allows a better understanding of finite sample properties of stochastic optimization and sparse prediction procedures for example. This research is at the intersection of Statistics, Machine Learning and Optimization. More recently, Philippe has been interested in understanding the statistical limitations of learning under computational constraints.