Timezone: »

Linear regression without correspondence
Daniel Hsu · Kevin Shi · Xiaorui Sun

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #205 #None

This article considers algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, a fully polynomial-time approximation scheme is given 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 i.i.d. draws from a standard multivariate normal distribution, an efficient algorithm based on lattice basis reduction is shown to exactly recover the unknown linear function in arbitrary dimension. Finally, lower bounds on the signal-to-noise ratio are established for approximate recovery of the unknown linear function by any estimator.

Author Information

Daniel Hsu (Columbia University)
Kevin Shi (Columbia University)
Xiaorui Sun (Columbia University)

More from the Same Authors