Black-Rangarajan duality

The iterative least squares technique becomes optimal when the weights are appropriately selected, aiming to combine the aspects of robust estimation with the rejection of outliers.

The duality described by Black-Rangarajan (BR96) connects these two aspects by showing that robust estimation can be viewed as a process of outlier removal. This dualism enables the use of Graduated Non-Convexity (GNC), a technique that gradually transforms a non-convex problem into a convex one, making it easier to find a global solution without the need for an initial hypothesis.

In practice, this dualism combined with GNC is used to develop algorithms that are robust to a high percentage of outliers, surpassing traditional methods such as RANSAC in terms of accuracy and speed.

The Black-Rangarajan duality provides a framework for establishing the relationship between M-estimators and linear processes. Typical robust loss functions include Welsch (Leclerc), Cauchy (Lorentzian), Charbonnier (pseudo-Huber, $\ell_1$-$\ell_2$), Huber, Geman-McClure, smooth truncated quadratic, truncated quadratic, Tukey's biweight functions, and so on. The Black-Rangarajan duality of these functions can be found in (ZB17), from which I present an excerpt in the table below:

Name	$\rho(x)$	$\omega(x)$
Quadratic	$\frac{x^2}{2}$	1
Cauchy	$\frac{\tau^2}{2} \log \left( 1 + x^2 / \tau^2 \right)$	$\frac{\tau^2}{\tau^2 + x^2}$
Huber	$\left\{\begin{array}{ll} x^2 / 2 & \vert x\vert \le \tau \\ \tau \vert x\vert - \tau^2 / 2 & \vert x\vert \ge \tau \\ \end{array} \right.$	$\left\{\begin{array}{ll} 1 & \vert x\vert \le \tau \\ \tau / \vert x\vert & \vert x\vert \ge \tau \\ \end{array} \right.$
Welsch	$\frac{\tau^2}{2} \left( 1 - e^{-x^2 / \tau^2} \right)$	$e^{-x^2 / \tau^2}$
Truncated Quadratic	$\min \left\{ \tau,x \right\}^2 / 2$	$\left\{ \begin{array}{ll} 1 & \vert x\vert \leq \tau \\ 0 & \vert x\vert > \tau \\ \end{array} \right.$

where there is the loss function $\rho(x)$ and its corresponding weight update function $\omega(x)$, and let $\tau \longDefiningEquals \max \{x : \omega(x) = 1\}$ be the radius of the unconditional inliers.