Jun, 2020

一环统治全局：具有离群点的可验证强鲁棒性几何感知

PDF
TL;DR本文提出了第一种通用且实用的框架，用于设计可证明的算法以应对大量离群值的情况下进行鲁棒几何感知，该算法使用截断最小二乘（TLS）代价函数，TLS 估计可以重新构制为多项式环上的优化，支持证明获得 TLS 问题的全局最小值，同时也可以使用斯内尔定理进行基础缩减，使用 SOS 松弛的双优化认证器，大大减小了 SDP 优化问题的复杂度，解决了当前 SDP 求解器无法解决的大规模问题。
发现论文，激发创造
  • 确证最优离群点鲁棒几何感知：半定松弛和可扩展全局优化

    该研究提出了第一个通用且可扩展的框架，用于设计可靠的几何感知算法，以在存在异常值的情况下证明其准确性，并在六个几何感知问题上进行了评估。

    Sep, 2021

  • 完美形状：从 2D 标志点中可证明的最优 3D 形状重建

    该研究通过采用三维可变形形状模型，将三维形状重建问题转化为相机姿态和线性形状参数的联合优化，使用 Lasserre 的 SOS 松弛层次来解决问题，并通过添加一个异常值剔除层和使用新的 TLS robust 代价函数来解决 TLS 问题，研发出一个鲁棒的三维形状重建算法 Shape#，可以容忍 70% 的异常值，达到了最先进的性能。

    Nov, 2019

  • 极端异常值率下的稳健配准多项式时间解决方案

    在大量异常值存在的情况下，我们提出了一种用于 3D 点集配准的健壮方法，其中第一个贡献是使用截断最小二乘（TLS）成本重新制定了配准问题，使得估计对大量虚假对应不敏感；第二个贡献是解耦旋转、平移和缩放估计的通用框架，允许按级联顺序解决三个转换。

    Mar, 2019

  • 稳健空间感知的非凸性：从非极小解算器到全局异常值拒绝

    本研究提出了一种可应用于任何非最小化求解器的鲁棒全局估计通用方法，该方法利用了鲁棒估计与异常值处理之间的 Black-Rangarajan 对偶并结合逐步非凸性与 SDP 解法求解，解决了常规稳健代价函数导致的非凸性问题；本方法应用于点云和网格登记，位姿图优化和基于图像的形状算法中，具有 70-80％异常值鲁棒性，并且比专门的局部求解器更准确和更快。

    Sep, 2019

  • TEASER：快速且可认证的点云配准

    提出了一个名为 TEASER 的算法，它使用 TLS 成本和图论框架来解决 3D 点集之间的快速且可靠的配准问题，能够在存在大量离群值的情况下有效地工作。该算法还提供了理论误差界限，并且在标准和 3DMatch 基准测试中都表现出跨越式的性能优势。

    Jan, 2020

  • 基于四元数的可验证最优解决方案：Wahba 问题的离群值

    本文提出了 QUASAR 算法，通过 Truncated Least Squares (TLS) 成本和使用 unit quaternions 重新表述问题，并将问题作为 Quadratically-Constrained Quadratic Program (QCQP) 来陈述，最后通过 Semidefinite Programming (SDP) 来放松，解决了 Wahba 问题，并验证了其在混合噪声数据集上的有效性。

    May, 2019

  • 关于理解半定松弛在强健旋转搜索中的应用

    该研究利用截断最小二乘法和半定松弛等方法旨在提高旋转搜索算法的抗干扰性，此外，该研究探讨了在噪声干扰和离群值存在的情况下，如何将求解半定松弛问题的结果作为 TLS 的替代方案。

    Jul, 2022

  • 对异常数据鲁棒的回归的高效算法

    本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

    Mar, 2018

  • 一种针对特殊欧几里德群同步的可证明正确性算法

    本文介绍一种解决几何估计中同步问题的算法，通过基于半定松弛的最大似然估计得出全局最优解，该算法可以在非对抗噪声情况下高效恢复可认证的全局最优解，并在大规模实例上使用低维黎曼曲面与特殊优化方案实现了优化问题的求解。

    Nov, 2016

  • 异常值鲁棒估计：难度、最小调整算法和应用

    本文提出了两种统一的异常值稳健估计公式，并调查了最基本的极限、实用算法和应用。首先，我们证明了在最坏情况下，异常值稳健估计是不可近似的，即使使用慢于多项式时间的算法也无法找到异常值集合。 其次，我们扩展了两种通用算法，这些算法不需要先验知识，并且可以动态决定如何从激光提取稳健的信息，同时提供了对机器人感知问题的评估。

    Jul, 2020