Robust Fitting with Truncated Least Squares: A Bilevel Optimization Approach

We tackle the problem of large-scale robust fitting using the truncated least squares (TLS) loss. Existing approaches commonly optimize this loss by employing a smooth surrogate, which allows the problem to be solved using well-known methods such as Iteratively Re-weighted Least Squares (IRLS). In this work, we present a new approach to optimize the TLS objective, where we propose to reformulate the original problem as a bi-level program. Then, by applying the Optimal Value Reformulation (OVR) technique to this new formulation, we derive a penalty approach to solve for the best fitting models, where the penalty parameters can be adaptively computed. Our final algorithm can be considered as a special instance of IRLS. As a result, we can incorporate our new algorithm into existing IRLS solvers, where we only need to modify the weight evaluation procedure. Our experimental results show promising results on several instances of large-scale bundle adjustment and non-linear refinement for essential matrix fitting.