美文网首页
Graduated Non-convexity

Graduated Non-convexity

作者: 轻骑兵1390 | 来源:发表于2020-07-20 16:49 被阅读0次

This page notes some supply materials about Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection. The paper gives a new approach for least squares optimization with outliers. The main contributions are two points:

  1. The Black-Rangarajan duality gives a function to estimate the weight of each cost function.
  2. The graduated non-convexity makes non-convexity cost function convex by a specially value and let the cost function to the original version during optimization.

1. The Deduction of Geman Mclure(GM) Function

The orignal version of GM is
\rho(r) = \frac{c^2r^2}{c^2+r^2}
The paper defines its surrogate function with a control parameter \mu:
\rho_\mu(r) = \frac{\mu c^2r^2}{\mu c^2+r^2}
where \mu\rightarrow \infty, \rho_\mu(r) become quadratic and \rho_\mu(r) recovers \rho(r) when \mu = 1.

The outlier process of \rho_\mu(r) with penalty term is computed as:
\Phi_{\rho_\mu}(w) = \mu c^2 (\sqrt{w} - 1)^2
\Phi_{\rho_\mu}(w) is derived by scheme in Fig.10 of Black-Rangarajan Duality.
We give the deduction from \rho_\mu(r) to \Phi_{\rho_\mu}(w).

1.1 Deviation

Step 1. \phi(w) = \rho(\sqrt{w})
\phi(w) = \rho_\mu(\sqrt{w}) = \frac{\mu c^2w}{\mu c^2+w}
where w > 0.

Step 2. Compute \phi^\prime(w) and \phi^{\prime\prime}(w) with respect to w

\begin{aligned} \phi^\prime(w) &= \frac{\mu c^2(\mu c^2+w) - \mu c^2w}{(\mu c^2+w)^2} \\ &= \frac{(\mu c^2)^2}{(\mu c^2+w)^2} = \left(\frac{\mu c^2}{\mu c^2+w}\right)^2 \\ \end{aligned}
And
\begin{aligned} \phi^{\prime\prime}(w) &= -\frac{2(\mu c^2)^2}{(\mu c^2 + w)^3} \end{aligned}

Step3. \lim_{w\rightarrow 0}\phi^\prime(w) = 1, \lim_{w\rightarrow \infty}\phi^\prime(w) = 0 and \phi^{\prime\prime}(w) < 0, then the process can continue.
For GM, \lim_{w\rightarrow 0}\phi^\prime(w) = 1 and \lim_{w\rightarrow \infty}\phi^\prime(w) = 0 is ok.
Because \sqrt{w} is existed, thus w > 0. Then (\mu c^2 + w) > 0 and \phi^{\prime\prime}(w) < 0.

Step4. z = \phi^\prime(w)
Step5. Solve w = (\phi^\prime)^{-1}(z)
z = \phi^\prime(w) = \left(\frac{\mu c^2}{\mu c^2+w}\right)^2
Then
w = \frac{\mu c^2}{\sqrt{z}} - \mu c^2 = (\phi^\prime)^{-1}(z)
where (\phi^\prime)^{-1} is inverse operation of \phi^\prime.

Step6. The target function:
\Phi(z)=\phi(w)-z w=\phi\left(\left(\phi^{\prime}\right)^{-1}(z)\right)-z\left(\phi^{\prime}\right)^{-1}(z)
We process our functions as:
\begin{aligned} \Phi(z)&=\phi(w)-zw = \frac{\mu c^2w}{\mu c^2+w} - \left(\frac{\mu c^2}{\mu c^2+w}\right)^2 \cdot w \\ &= \frac{\mu c^2w(\mu c^2 + w)- (\mu c^2)^2w}{(\mu c^2 + w)^2}\\ &= \frac{\mu c^2 w^2}{(\mu c^2 + w)^2} \end{aligned}
The value is z, thus we simplify \Phi(z) with w = \frac{\mu c^2}{\sqrt{z}} - \mu c^2
\begin{aligned} \Phi(z) &= \frac{\mu c^2 w^2}{(\mu c^2 + w)^2} =\frac{\mu c^2 (\mu c^2/\sqrt{z} - \mu c^2)^2}{(\mu c^2 + \mu c^2/\sqrt{z} - \mu c^2)^2} \\ &= \frac{(\mu c^2)^3(1/\sqrt{z} - 1)^2}{(\mu c^2)^2(1/\sqrt{z})^2} \\ &= \mu c^2 \cdot (1 - \sqrt{z})^2 \\ &= \mu c^2 \cdot (\sqrt{z} - 1)^2 \end{aligned}

The function is equivalent to (11) in Graduated Non-Convexity.

相关文章

网友评论

      本文标题：Graduated Non-convexity

      本文链接：https://www.haomeiwen.com/subject/cnhykktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Graduated Non-convexity|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！