Black-Rangarajan Duality

Iterative least squares becomes an optimal technique when the weights are selected appropriately, combining robust estimation with outlier rejection.

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

In practice, this duality together with GNC is used to develop algorithms that are robust to a high proportion of outliers, outperforming traditional methods such as RANSAC in terms of accuracy and speed.

Black–Rangarajan duality provides a theory for constructing the relationship between M-estimators and line 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 others. The Black–Rangarajan duality of these functions can be found in (ZB17); an excerpt is reproduced here in the table:

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 the loss function is $\rho(x)$, its corresponding weight-update function is $\omega(x)$, and $\tau \longDefiningEquals \max \{x : \omega(x) = 1\}$ is the radius of the unconditional inliers.