Theory Seminar

Friday, January 20, 2017 -
3:00pm to 4:30pm

Location:

ASA Conference Room 6115 Gates Hillman Center

Speaker:

ANUP RAO, Associate Professor https://homes.cs.washington.edu/~anuprao/

Event Website:

http://theory.cs.cmu.edu/seminars/

For More Information, Contact:

nlc@cs.cmu.edu

In this talk, we consider the problem of estimating the mean and covariance of a distribution from iid samples in R^n, in the presence of an eta fraction of malicious noise; this is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. We will give polynomial-time algorithms to compute estimates for the mean, covariance and operator norm of the covariance matrix, and show that the dimensional dependence of the error is optimal up to a O(\sqrt{\log n}) factor. This gives polynomial-time solutions to some of the questions studied in robust statistics. As one of the applications, this immediately enables one to do agnostic SVD.This is a joint work with Kevin Lai and Santosh Vempala.

Keywords:

Seminar Series