Sampson Error

Figura 4.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 ottenuto mediante l'approssimazione 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 modello geometrico. Si supponga che esista un punto ideale $\hat{\mathbf p}$ appartenente alla varietà tale che

$$\mathbf p=\hat{\mathbf p}+\boldsymbol\eta$$ (4.66)

dove $\boldsymbol\eta$ rappresenta il rumore di osservazione.

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 dal punto di vista della massima verosimiglianza, nel caso di rumore gaussiano isotropo, è la distanza geometrica tra il punto osservato $\mathbf p$ e il punto ideale $\hat{\mathbf p}$ appartenente al modello, ovvero la norma del vettore di rumore $\boldsymbol\eta$.

Esaminiamo pertanto il problema di calcolare una distanza approssimata tra il punto $\mathbf{p} \in \mathbb{R}^m$ e una varietà geometrica definita implicitamente dall'equazione $f(\mathbf{x})=\mathbf{0}$, con

$$f:\mathbb{R}^m \to \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$$ (4.67)

sotto il vincolo $f(\mathbf{x})=0$ (o equivalentemente $\min \Vert\boldsymbol\delta_{\mathbf x}\Vert^2$ sotto il vincolo $f(\mathbf p+\boldsymbol\delta_{\mathbf x})=\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: la funzione implicita $f$ deve poter essere approssimata linearmente nell'intorno del punto $\mathbf {p}$. La varietà definita dal vincolo $f(\mathbf{x})=0$ può essere approssimata con Taylor

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

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 sottospazio affine in $\mathbf {x}$ e, nel caso particolare $n=1$, di un iperpiano. La distanza tra il punto $\mathbf {p}$ e tale approssimazione lineare della varietà è la distanza di Sampson o approximate maximum likelihood (AML). L'errore di Sampson rappresenta la distanza geometrica tra il punto e la versione linearizzata della funzione.

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})$$ (4.69)

Essendo un problema di minimizzazione vincolata, la soluzione può essere ricavata attraverso i moltiplicatori di Lagrange. Applicando la linearizzazione del vincolo e assumendo che $\mathbf{J}_f$ abbia rango di riga pieno, si ottiene

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

che rappresenta la minima correzione necessaria, nel senso della norma euclidea, per soddisfare il vincolo linearizzato. Il risultato è interessante se confrontato con il metodo di Gauss-Newton, equazione (4.58).

Il vettore $\boldsymbol\delta_{\mathbf x}$ rappresenta la minima correzione necessaria per soddisfare il vincolo linearizzato. La sua norma costituisce una stima della distanza del punto $\mathbf p$ dalla varietà: può essere usata per esempio all'interno di algoritmi come RANSAC per discernere gli outlier o come funzione costo alternativa alla norma euclidea. Il vettore $\boldsymbol\delta_{\mathbf x}$ è la correzione associata alla distanza di Sampson. La quantità

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

è detta errore (o distanza) di Sampson e 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}$$ (4.72)

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

La formulazione precedente può essere estesa al caso di rumore anisotropo introducendo una metrica di Mahalanobis:

$$\min_{\boldsymbol\delta_{\mathbf x}} \; \boldsymbol\delta_{... ...x}^{\top} \boldsymbol\Sigma^{-1} \boldsymbol\delta_{\mathbf x}$$ (4.73)

sotto il vincolo

$$f(\mathbf p+\boldsymbol\delta_{\mathbf x})=0.$$

L'equazione sopra si generalizza pertanto in

$$%\Vert \boldsymbol\delta_x \Vert^2 = \boldsymbol\delta_x^{\... ...oldsymbol\Sigma \mathbf{J}_f^{\top} \right)^{-1} f(\mathbf{p})$$ (4.74)