Black-Rangarajan duality

La tecnica dei minimi quadrati iterativi diventa una tecnica ottima se per i pesi vengono selezionati opportunamente, cercando di unire l'aspetto di stima robusta con l'aspetto di rigetto degli Outlier.

La dualità descritta da Black-Rangarajan (BR96) collega questi due aspetti mostrando che la stima robusta può essere vista come un processo di rimozione degli Outlier. Questo dualismo permette l'uso della Non-Convessità Graduata (Graduated Non-Convexity, GNC), una tecnica che trasforma gradualmente un problema non convesso in uno convesso, rendendo più facile trovare una soluzione globale senza bisogno di un'ipotesi iniziale.

In pratica, questo dualismo unito alla GNC sono utilizzati per sviluppare algoritmi che sono robusti a una percentuale elevata di outlier, superando i metodi tradizionali come RANSAC in termini di accuratezza e velocità.

La dualità di Black-Rangarajan fornisce una teoria per costruire la relazione tra M-estimatori e processi lineari. Le tipiche funzioni di Loss robuste includono Welsch (Leclerc), Cauchy (Lorentziana), Charbonnier (pseudo-Huber, $\ell_1$-$\ell_2$), Huber, Geman-McClure, quadratica troncata smooth, quadratica troncata, funzioni biweight di Tukey, ecc. La dualità di Black-Rangarajan di queste funzioni può essere trovata in (ZB17) di cui riporto un estratto qua in tabella:

Nome	$\rho(x)$	$\omega(x)$
Quadratica	$\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}$
Quadratica troncata	$\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.$

dove c'è la loss function $\rho(x)$ e la sua corrispondente funzione di aggiornamento dei pesi $\omega(x)$ e sia $\tau \longDefiningEquals \max \{x : \omega(x) = 1\}$ il raggio degli inlier incondizionati.