提出首个全局最优的截断损失优化框架,提升几何估计抗异常值能力与阈值鲁棒性。
Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation
- 采用混合分支定界法,在高维问题中降维求解并构建紧致边界函数
- 相比共识最大化,对阈值变化更不敏感,且计算效率显著提升
- 适用于多种几何估计任务,适合需要高精度与稳定性的工业场景
为实现鲁棒的几何估计,通常采用鲁棒目标函数以缓解异常值影响。广泛使用的共识最大化(CM)在结合全局分支定界(BnB)搜索时具有很高鲁棒性,但仅依赖内点数量,对内点阈值敏感,且因其离散性导致边界松散,需大量BnB迭代和计算开销。截断损失(TL)作为连续替代方案,能更有效利用残差信息,可能克服上述问题。然而,据我们所知,尚无研究系统探索基于BnB的全局最小化TL及其在增强阈值鲁棒性或搜索效率方面的潜力。本文提出GTM,首个统一的基于BnB的全局最优TL损失最小化框架,适用于多种几何问题。GTM采用混合求解设计:针对n维问题,在(n-1)维子空间进行BnB搜索,剩余1维变量通过边界函数求解。该设计不仅缩小搜索空间,还使我们能推导出通用、紧致的Lipschitz连续边界函数,可由经典全局求解器DIRECT高效求解,进一步加速。我们在鲁棒线性回归问题上系统评估了多种基于BnB的CM与TL方法,结果表明GTM在阈值鲁棒性和效率方面均优于基线方法。此外,我们将GTM应用于具有不同残差形式的多种几何估计问题,实验显示其在各类任务中均达到当前最优的抗异常值性能与阈值鲁棒性,同时保持高效。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。