Sampson Error

Figura 3.1: Tra una varietà $\mathcal {V}$ e un punto $\mathbf {p}$ si possono individuare il punto a distanza geometrica minima $\hat{\mathbf{p}}$ e il punto determinato dalla distanza di Sampson $\mathbf {x}$.

In molti problemi di regressione di dati è necessario essere in possesso di una qualche metrica per capire quanto un $\mathbf {p}$ è distante dal modello vero e proprio e per fare questo sarebbe utile avere una stima $\hat{\mathbf{p}}$ dell'osservazione senza la componente del rumore, ovvero un dato che appartiene al modello esattamente. Entrambe queste quantità normalmente non sono direttamente ottenibili se non introducendo variabili sussidiarie incognite. È tuttavia possibile ottenere una stima di questi valori, linearizzando la funzione del modello nell'intorno dell'osservazione.

Sia $\mathbf {p}$ una osservazione affetta da rumore e sia $f(\mathbf{x})=\mathbf{0}$ una varietà multidimensionale manifold rappresentante un particolare modello a cui l'osservazione deve appartenere, ovvero $\mathbf{p} = \hat{\mathbf{p}} + \epsilon$.

Il residuo $f(\mathbf{p})$ è una misura algebrica della vicinanza tra il punto e il modello e non fornisce nessuna informazione utile in termini assoluti: se la funzione viene sostituita da un suo multiplo (diverso da zero) rappresenterà ovviamente lo stesso luogo dei punti ma il risultato della funzione cambierà di conseguenza. La metrica corretta sotto il punto di vista dello stimatore alla massima verosimiglianza in caso di rumore additivo gaussiano bianco sulle osservazioni è la distanza geometrica tra il punto $\mathbf {p}$ e il punto $\hat{\mathbf{p}}$ appartenente al modello ovvero stimare $\epsilon$.

Esaminiamo pertanto il problema di calcolare una distanza approssimata tra il punto $\mathbf{p} \in \mathbb{R}^m$ rispetto a una varietà geometrica $f(\mathbf{x})=\mathbf{0}$ dove $f: \mathbb{R}^{m} \mapsto \mathbb{R}^{n}$ funzione derivabile in un intorno di $\mathbf {p}$.

Il punto $\hat{\mathbf{p}}$ che giace sulla varietà più vicino al punto $\mathbf {p}$ è per definizione quel punto che minimizza l'errore geometrico

$$\hat{\mathbf{p}} = \argmin_\mathbf{x} \Vert \mathbf{p} - \mathbf{x} \Vert$$ (3.52)

sotto il vincolo $f(\mathbf{x})=0$ (o $\min \vert\vert \epsilon \vert\vert^2$ sotto il vincolo $f(\mathbf{p} + \epsilon)=\mathbf{0}$).

La differenza tra minimizzare una quantità algebrica in maniera lineare e una quantità geometrica in maniera non-lineare ha spinto la ricerca di un eventuale compromesso. Il metodo di Sampson, sviluppato inizialmente per varietà come le coniche, richiede un ipotesi che può essere applicata invece a diversi problemi: le derivate della funzione costo nell'intorno del minimo $\hat{\mathbf{p}}$ devono essere pressoché lineari e dunque approssimabili attraverso l'espansione in serie. La varietà $f(\mathbf{p})=0$ può essere approssimata con Taylor in modo tale che

$$\tilde{f}(\mathbf{x}) \approx f(\mathbf{p}) + \mathbf{J}_f \boldsymbol\delta_{\mathbf{x}} = \mathbf{0}$$ (3.53)

con $\mathbf{J}_f$ matrice $n \times m$ dello Jacobiano della funzione $f$ calcolato in $\mathbf {p}$ e $\boldsymbol\delta_{\mathbf{x}} = \mathbf{x}-\mathbf{p}$.

Questa è l'equazione di un iperpiano in $\mathbf {x}$ e la distanza tra il punto $\mathbf {p}$ con il piano $\tilde{f}(\mathbf{x})=0$ è la distanza di Sampson o l'approximate maximum likelihood (AML). L'errore di Sampson rappresenta la distanza geometrica tra il punto e la versione approssimata della funzione (geometric distance to first order approximation function).

Il problema a questo punto diventa quello di trovare il punto $\mathbf {x}$ più vicino a $\mathbf {p}$, ovvero minimizzare $\Vert\boldsymbol\delta_{\mathbf{x}}\Vert$, soddisfacendo il vincolo lineare

$$\mathbf{J}_f \boldsymbol\delta_{\mathbf{x}} = -f(\mathbf{p})$$ (3.54)

Essendo un caso di minimizzazione con vincoli si risolve attraverso l'uso dei moltiplicatori di Lagrange, da cui si ottiene il risultato notevole

$$\boldsymbol\delta_{\mathbf{x}} = - \mathbf{J}^{\top} \left( \mathbf{J} \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (3.55)

risultato interessante se confrontato con il metodo di Gauss-Newton per esempio, equazione (3.46).

Il valore $\boldsymbol\delta_\mathbf{x}$ rappresenta una stima della distanza del punto $\mathbf {p}$ rispetto alla varietà e può essere usato sia per capire se il punto appartiene o meno alla varietà (per esempio all'interno di algoritmi come RANSAC per discernere gli outlier) che potenzialmente come funzione costo alternativa alla norma euclidea. $\boldsymbol\delta_\mathbf{x}$ è l'errore di Sampson e la sua norma, data da

$$\Vert \boldsymbol\delta_x \Vert^2 = \boldsymbol\delta_x^{\t... ...\left( \mathbf{J} \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (3.56)

indica la distanza (al quadrato) tra il punto e (l'approssimazione al primo grado di) un punto della varietà.

Nel caso notevole $n=1$, la distanza di Sampson si riduce a

$$\Vert \boldsymbol\delta_x \Vert^2 = \dfrac{\left( f(\mathbf{p}) \right)^{2}}{\left\Vert \nabla f(\mathbf{p}) \right\Vert^2}$$ (3.57)

Applicazioni pratiche dell'uso dell'errore di Sampson sono per esempio la distanza tra un punto e la conica (vedi sezione 3.6.7), distanza di una coppia di punti da una omografia o la distanza di una coppia di punti omologhi rispetto alla matrice Fondamentale (sezione 9.4.2).

La distanza di Sampson può venire generizzata nel caso di molteplici vincoli usando la distanza di Mahalanobis, ovvero minimizzando

$$\min_\epsilon \sum \vert\vert \epsilon \vert\vert^2_\Sigma ... ...epsilon \sum \epsilon^{\top} \boldsymbol \Sigma^{-1} \epsilon$$ (3.58)

sotto al vincolo $f(\mathbf{p}+\epsilon)=0$. L'equazione sopra si generalizza pertanto in

$$\Vert \boldsymbol\delta_x \Vert^2 = \boldsymbol\delta_x^{\t... ...boldsymbol \Sigma \mathbf{J}^{\top} \right)^{-1} f(\mathbf{p})$$ (3.59)