Title: Denoising Linear Models with Permuted Data,
Abstract: The multivariate linear regression model with shuffled data and additive
Gaussian noise arises in various correspondence estimation and matching
problems. Focusing on the denoising aspect of this problem, we provide a
characterization the minimax error rate that is sharp up to logarithmic
factors. We also analyze the performance of two versions of a computationally
efficient estimator, and establish their consistency for a large range of input
parameters. Finally, we provide an exact algorithm for the noiseless problem
and demonstrate its performance on an image point-cloud matching task. Our
analysis also extends to datasets with outliers.