Title: Linear regression without correspondence,
Abstract: 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.