Linear regression without correspondence
arXiv:1705.07048
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.
Cited by in corpus (14)
- Signal Recovery from Unlabeled Samples
- Linear Regression without Correspondences via Concave Minimization
- Stochastic EM for Shuffled Linear Regression
- Homomorphic Sensing
- R-local unlabeled sensing: A novel graph matching approach for multiview unlabeled sensing under local permutations
- A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data
- Uncoupled Regression from Pairwise Comparison Data
- Estimation in exponential family Regression based on linked data contaminated by mismatch error
- Extreme Multi-label Classification from Aggregated Labels
- Robust approximate linear regression without correspondence
- Low-rank Matrix Recovery With Unknown Correspondence
- Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group
- A Hypergradient Approach to Robust Regression without Correspondence
- Multiview Sensing With Unknown Permutations: An Optimal Transport Approach