Robust Composite Recovery for Two-Component Mixed Linear Regression

Mixed linear regression (MLR) models heterogeneous populations through multiple linear relationships with unobserved component memberships, with broad applications across market segmentation, trajectory clustering, and signal unmixing. A fundamental challenge in robust MLR is to reliably recover the underlying regression coefficients in the presence of both structured inlier noise and a small fraction of arbitrarily large response outliers, while providing rigorous finite-sample guarantees. We study the canonical two-component MLR setting with Gaussian covariates and component proportions bounded away from zero. We propose SARP-P (Segment-initialized Adaptive Robust Prox-linear estimation with Polishing), a complete estimator that unifies segment initialization, normalized composite iteration, and residual-calibrated response polishing in a single pipeline. With a sample size nearly linear in the covariate dimension, we establish a full finite-sample recovery guarantee: Provably correct initialization, a quadratic error recursion converging to an explicit noise floor, and valid recovery of the final polished estimate. Our bounds tolerate a bounded fraction of arbitrary response outliers independent of their amplitudes, and hold uniformly across all data-dependent adaptive weights and trimming steps. All stages of the estimator reuse the same observations, and all guarantees hold under a single high-probability event. A computable data-driven acceptance rule transfers recovery guarantees to the final polished estimate without requiring a known noise scale. Synthetic experiments demonstrate that response polishing improves estimation accuracy, with particularly strong gains under scale-mixture noise with response outliers.