Hidden structures in large matrices

Hidden structures in large matrices

-
Sourav Chatterjee , Courant Institute of Mathematical Sciences, NYU
Fine Hall 314

Consider the problem of estimating the entries of a large matrix, when most of the entries are either hidden from us or blurred by noise. Of course, one needs to assume that the matrix has some structure for this estimation to be possible. This problem has received widespread attention in statistics, computer science and information theory in recent times, especially after the pioneering works of Emmanuel Candes and collaborators. I will introduce a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that automatically detects the inherent structure of the matrix whenever any structure is present, and uses this knowledge to estimate the unknown entries. Surprisingly, this simple estimator is "minimax optimal" up to a constant factor. The method gives easy solutions to a wide range of difficult questions about large data matrices.