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 se un punto $\mathbf {p}$ possa appartenere o meno al modello. Allo stesso modo può tornare utile conoscere una stima $\hat{\mathbf{p}}$ dell'osservazione senza la componente del rumore.

Sia $\mathbf {p}$ pertanto una osservazione affetta da rumore e sia $f(\mathbf{x})=\mathbf{0}$ una varietà multidimensionale rappresentante un particolare modello.

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: qualsiasi multiplo diverso da zero della funzione rappresenterà lo stessa varietà ma la distanza cambierà di conseguenza. La metrica corretta sotto il punto di vista dello stimatore alla massima verosimiglianza in caso di rumore additivo gaussiano bianco è la distanza geometrica tra il punto $\mathbf {p}$ e il punto $\hat{\mathbf{p}}$ appartenente al modello.

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$.

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 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 tra il punto e l'approssimazione al primo grado della varietà.

Nel caso notevole $n=1$, ampiamente diffuso, 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.5.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).