Search papers, labs, and topics across Lattice.
This paper introduces GTM, a novel branch-and-bound (BnB) framework for globally minimizing Truncated Losses (TL) in geometric estimation problems, addressing the limitations of consensus maximization (CM) regarding threshold sensitivity and computational cost. GTM employs a hybrid solving design, performing BnB search over a reduced subspace and bounding the remaining variable using Lipschitz-continuous functions solvable by DIRECT. Experiments on linear regression and various geometric estimation tasks demonstrate GTM's superior threshold resilience, outlier robustness, and efficiency compared to existing BnB-based CM and TL methods.
Achieve state-of-the-art outlier robustness and threshold resilience in geometric estimation with a surprisingly efficient branch-and-bound approach.
To achieve outlier-robust geometric estimation, robust objective functions are generally employed to mitigate the influence of outliers. The widely used consensus maximization(CM) is highly robust when paired with global branch-and-bound(BnB) search. However, CM relies solely on inlier counts and is sensitive to the inlier threshold. Besides, the discrete nature of CM leads to loose bounds, necessitating extensive BnB iterations and computation cost. Truncated losses(TL), another continuous alternative, leverage residual information more effectively and could potentially overcome these issues. But to our knowledge, no prior work has systematically explored globally minimizing TL with BnB and its potential for enhanced threshold resilience or search efficiency. In this work, we propose GTM, the first unified BnB-based framework for globally-optimal TL loss minimization across diverse geometric problems. GTM involves a hybrid solving design: given an n-dimensional problem, it performs BnB search over an (n-1)-dimensional subspace while the remaining 1D variable is solved by bounding the objective function. Our hybrid design not only reduces the search space, but also enables us to derive Lipschitz-continuous bounding functions that are general, tight, and can be efficiently solved by a classic global Lipschitz solver named DIRECT, which brings further acceleration. We conduct a systematic evaluation on various BnB-based methods for CM and TL on the robust linear regression problem, showing that GTM enjoys remarkable threshold resilience and the highest efficiency compared to baseline methods. Furthermore, we apply GTM on different geometric estimation problems with diverse residual forms. Extensive experiments demonstrate that GTM achieves state-of-the-art outlier-robustness and threshold-resilience while maintaining high efficiency across these estimation tasks.
