REFORMULATING MAXIMUM CONSENSUS AS A SET- HITTING PROBLEM FOR ROBUST ESTIMATION AND OUTLIER REMOVAL UNDER HIGH NOISE

Maximum consensus (MAXCON) is a standard criterion for outlier removal and robust model estimation. Computing the exact optimal consensus set is a hard optimization problem as the standard big-M mixed-integer linear-programming (MILP) formulation scales poorly with the number of data-points, model dimension, and, most importantly, the percentage of outliers. To address this, we provide an exact reformulation of MAXCON as a set-hitting problem, and develop point- and subset-based criteria that remove guaranteed outliers, thereby reducing the size of the reformulated problem. In most cases the reduced problem either admits a tight LP relaxation or its greedy solution is provably optimal, so the exact optimum is certified without solving any MILP – removing the dependence on a licensed solver. In the remaining cases, the original MILP is solved over the much smaller pruned data-set, preserving tractability. On synthetic and real-world datasets with a large number of data-points and $50$–$80$% outliers, the proposed approach recovers the exact consensus set while running on average $10$–$100\times$ faster than the MILP baseline, which often fails to solve the problem exactly even after exhausting a 48-hour runtime budget.