Linear regression without correspondence
Daniel Hsu, Columbia University
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.