Ohio State nav bar

Joint Statistics/CSE Seminar: Daniel Hsu

Statistics Seminar Series
November 9, 2017
All Day
209 W Eighteenth Ave (EA), Room 170

Title

Linear regression without correspondence

Speaker

Daniel Hsu, Columbia University

Abstract

I will talk about algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown.  First, I'll give a fully polynomial-time approximation scheme for the natural least squares optimization problem in any constant dimension.  Next, in an average-case and noise-free setting where the responses exactly correspond to a linear function of iid draws from a standard multivariate normal distribution, I'll describe an efficient algorithm based on lattice basis reduction that exactly recovers the unknown linear function in arbitrary dimension.  Last, I'll establish lower bounds on the signal-to-noise ratio for approximate recovery of the unknown linear function.

This is joint work with Kevin Shi (Columbia) and Xiaorui Sun (Microsoft Research).

Note: Seminars are free and open to the public. Reception to follow.