Linear Regression without Correspondences via Concave Minimization

Abstract

Linear regression without correspondences concerns the recovery of a signal in the linear regression setting, where the correspondences between the observations and the linear functionals are unknown. The associated maximum likelihood function is NP-hard to compute when the signal has dimension larger than one. To optimize this objective function we reformulate it as a concave minimization problem, which we solve via branch-and-bound. This is supported by a computable search space to branch, an effective lower bounding scheme via convex envelope minimization and a refined upper bound, all naturally arising from the concave minimization reformulation. The resulting algorithm outperforms state-of-the-art methods for fully shuffled data and remains tractable for up to $8$-dimensional signals, an untouched regime in prior work.

References in corpus (9)

• Linear regression without correspondence
• Linear Regression with Shuffled Labels
• Signal Recovery from Unlabeled Samples
• Permutations Unlabeled beyond Sampling Unknown
• Stochastic EM for Shuffled Linear Regression
• Homomorphic Sensing
• A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data
• Homomorphic Sensing of Subspace Arrangements
• A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data

Cited by in corpus (7)

• r-local sensing: Improved algorithm and applications
• Homomorphic Sensing of Subspace Arrangements
• Estimation in exponential family Regression based on linked data contaminated by mismatch error
• The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors
• Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces
• Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group
• A Hypergradient Approach to Robust Regression without Correspondence