Introduction
Standard linear regression models rely on the fundamental assumption that data pairs $(x_i, y_i)$ are perfectly aligned. However, in practical applications such as record linkage across disparate databases or data integration from anonymized sources, this correspondence is frequently compromised. This "Broken Sample Problem" or "Unlabeled Sensing" occurs when the relationship between predictors and responses is obscured by an unknown permutation.
While previous literature has largely addressed scalar response scenarios with strict one-to-one shuffles, this work introduces a robust framework for multivariate linear regression. This approach generalizes the mismatch model to accommodate missing matches and one-to-many correspondences, leveraging the presence of multiple response variables to facilitate data recovery.
Methodology
The proposed solution follows a computationally efficient two-stage pipeline designed for the "sparse mismatch" regime, where the majority of data pairs remain correctly aligned.
Stage 1: Robust Parameter Estimation
The first stage focuses on estimating the regression coefficients $B^*$ without immediate concern for individual matches. By treating mismatched observations as row-wise outliers, the authors employ a convex optimization formulation with block-sparsity penalties. This allows the model to effectively "ignore" contaminated rows and learn the underlying linear relationship from the correctly matched majority.
Stage 2: Correspondence Restoration
With a reliable estimate of $B^*$, the problem of finding the correct alignment is simplified. The second stage utilizes the residuals from the estimated model to perform correspondence restoration. This is achieved through variants of matching algorithms, such as the Hungarian or Auction algorithms, to identify the most probable permutation that aligns responses with their corresponding predictors.
Experimental Results and Key Insights
The framework was validated using synthetic high-dimensional data and several real-world benchmarks, including robot kinematics (SARCOS), flight ticket pricing, and air quality monitoring. A notable case study involved U.S. City Temperatures, where monthly average temperatures for 46 cities were used to test the model's ability to handle partial shuffling of seasonal data.
The "Power of $m$"
A central finding of this research is the significant advantage provided by multivariate responses. In scalar regression ($m=1$), recovering matches requires a Signal-to-Noise Ratio (SNR) that scales with the sample size $n$. Conversely, in the multivariate case, if the number of responses $m$ is sufficiently large (specifically $\Omega(\log n)$), the required SNR becomes a constant. This suggests that having more "features" in the response space acts as a force multiplier for data alignment.
Comparative Performance
In empirical tests, the two-stage method consistently outperformed traditional approaches like Expectation-Maximization (EM). While EM often converges to local minima or fails when data deviates from Gaussian assumptions, the proposed method remains robust. Furthermore, the first stage scales linearly with the number of samples, offering superior scalability for large-scale data integration tasks.
Conclusion
This work demonstrates that reframing permutation recovery as a robust regression problem with sparse outliers makes the "Broken Sample Problem" tractable. The primary limitation remains the sparsity requirement; the method is most effective when mismatches constitute less than 40% of the dataset. Future research will explore "dense" mismatch scenarios and the extension of this framework to non-linear models and mixed-type response variables.
Summary updated