Retta di distanza ottimale da punti

Messaggioda 3m0o » 06/06/2019, 22:46

Siano \( a_1, \ldots , a_m \in \mathbb{R}^n \), per \( z \in \mathbb{R}^n \) e \( v \in S^{n-1} \) consideriamo la retta
\( L_{z,v} \) definita come
\[ L_{z,v} = \{ z + \lambda v : \lambda \in \mathbb{R} \} \]

Sia \( d(a_i,L_{z,v}) \) la distanza tra \( a_i \) e \( L_{z,v} \), per \( i =1,\ldots ,m \)
i) Supponi che \( \sum\limits_{i} a_i = 0 \) dimostra che \( \sum\limits_{i} d(a_i,L_{z,v})^2 \geq \sum\limits_{i} d(a_i,L_{0,v})^2 \) per tutti \( z \in \mathbb{R}^n \).

ii) Concludere che dati dei punti \( a_1, \ldots, a_m \) possiamo trovare un \( z \in \in \mathbb{R}^n \) e \( v \in S^{n-1} \) tale che
\[ \sum\limits_{i} d(a_i,L_{z',v'})^2 \geq \sum\limits_{i} d(a_i,L_{z,v})^2 \]
per tutti gli \( z' \in \mathbb{R}^n \) e \( v' \in S^{n-1} \) in particolare dare una formula per \( z \) e descrivere la matrice \( A \) tale che un autovettore normalizzato di \( A^T A \) associato all'autovalore più grande è una soluzione per \( v \)

Per il punto i) non capisco solo un passaggio
\[ \sum\limits_{i} d(a_i,L_{z,v})^2 -\sum\limits_{i} d(a_i,L_{0,v})^2 = \sum\limits_{i} (-2 \left \langle a_i , z \right \rangle + \begin{Vmatrix} z \end{Vmatrix}^2 + 2 \left \langle a_i , v \right \rangle \left \langle z , v \right \rangle - \left \langle z , v \right \rangle^2 ) \]
\[ \sum\limits_{i} d(a_i,L_{z,v})^2 -\sum\limits_{i} d(a_i,L_{0,v})^2 = m(\begin{Vmatrix} z \end{Vmatrix}^2 - \left \langle z , v \right \rangle^2 ) \geq 0 \]
Non capisco come mai il risultato sia \( m(\begin{Vmatrix} z \end{Vmatrix}^2 - \left \langle z , v \right \rangle^2 ) \)

Per il punto ii) non capisco due cose, prima di tutto fa notare come il risultato sia invariante per traslazione per \( -t \in \mathbb{R}^n \), sostituendo \( a_i' = a_i - t \) e \( z' = z- t \) si ottiene che
\[ \sum\limits_{i} d(a_i,L_{z,v})^2 = \sum\limits_{i} \begin{Vmatrix} a_i -z \end{Vmatrix}^2 - \left \langle a_i- z , v \right \rangle^2 = \sum\limits_{i} \begin{Vmatrix} a_i' -z' \end{Vmatrix}^2 - \left \langle a_i'- z' , v \right \rangle^2 = \sum\limits_{i} d(a_i',L_{z',v})^2 \]

E deduce direttamente che \( z = \frac{1}{m} \sum\limits_i a_i \) ma io non capisco come abbia fatto a trovare questo valore di \( z \). Inoltre non capisco il motivo per cui fa notare che il risultato è invariante per rotazione.
Per la matrice dice semplicemente che visto che lo spazio ottimale deve avere lo zero shifta i vettori \( a_1 \) all origine e crea questa matrice, ma non capisco il motivo per cui soddisfa le richieste...
\( A = \begin{pmatrix}
(a_1 - z)^T\\
\vdots\\
(a_m-z)^T
\end{pmatrix} \)

Tra l'altro non mi sembrando "shiftati" all origine.
3m0o
Junior Member
Junior Member
 
Messaggio: 327 di 447
Iscritto il: 02/01/2018, 16:00

Re: Retta di distanza ottimale da punti

Messaggioda 3m0o » 09/06/2019, 22:25

Proprio nessuno riesce a darmi una mano a capire? :(
3m0o
Junior Member
Junior Member
 
Messaggio: 333 di 447
Iscritto il: 02/01/2018, 16:00

Re: Retta di distanza ottimale da punti

Messaggioda Bokonon » 09/06/2019, 23:47

E' la regressione multivariata.
L'avevo letto ieri ma mi è venuto male all'idea di scrivere formule. Inoltre non mi tornava la definizione che hai dato, ovvero ci sono m vettori di $R^n$ e subito dopo scrivi che la loro somma è zero. Probabilmente invece si intendeva la somma delle componenti di ogni singolo vettore è zero per ogni i.
Così torna tutto, perchè la "regressione alla media" fa proprio questo. Si prendono m vettori e si cerca la retta che minimizza la somma delle distanze al quadrato di questi vettori dalla retta. Se si depurano le medie, ovvero si prende la media delle componenti di ogni vettore e la si sottrae da tutte le componenti, allora la nuova somma è zero...e la retta di regressione passerà per l'origine (ecco perchè è vero il primo punto, infatti se la si trasla la somma delle devianze di dispersione fra i vettori e la retta traslata sarà necessariamente maggiore della prima).
Poi generalizzano il discorso e vedo che sostanzialmente scrivono la formula della decomposizione della varianza...ovvero la devianza totale è pari alla somma della devianza dovuta al modello + quella residua.
Infine fanno notare che in generale la retta di regressione intercetta l'asse della variabile indipendente all'altezza del vettore delle medie z.
Avatar utente
Bokonon
Senior Member
Senior Member
 
Messaggio: 1383 di 1544
Iscritto il: 25/05/2018, 21:22

Re: Retta di distanza ottimale da punti

Messaggioda 3m0o » 11/06/2019, 04:13

Gentilissimo,
Anche se ci ho capito poco, la regressione multivariata e le varie devianze che nomini non ho idea di cosa siano a quanto pare sono questa roba qui :lol: , le soluzioni e l'enunciato dicono somma degli \( a_i \) uguale a 0 non è un errore mio e onestamente non credo sia un errore, infatti dopo fa un esempio per mostrare come la retta ottimale non sia unica (e non l'ho messo nel problema perché di per se avevo capito ed è un punto a parte).
Alla domanda dati \( a_1, \ldots, a_m \in \mathbb{R}^n \) dove \( m > n >1 \) la retta \( L_{z,v} \) che minimizza \( \sum_{i=1}^{m} d(a_i, L_{z,v} )^2 \) è unica?
La risposta è no, infatti se prendiamo \( e_1, e_2, -e_1, -e_2 \in \mathbb{R}^2 \), questi quattro punti sommati danno zero, ma due linee \( L_{0,v} \) e \( L_{0,v^{\perp}} \) ortogonali una all altra risultano sempre nella stessa somma di quadrati delle distanze. Quindi una soluzione ottimale che passa da 0, qualunque essa sia, non può essere unica. (Tradotto malamente da...These points sum up to zero, but two lines \( L_{0,v} \) and \( L_{0,v^{\perp}} \) orthogonal to each other always result in the same sum of square distances. Hence, an optimal solution through 0, whatever it is, cannot be unique.)

Edit:
Cioé a me sembra che \( z \) sia il baricentro dei punti, che probabilmente si comporta in modo analogo a quello che dici te. Ma il motivo per cui è il baricentro e come trova questa cosa rimane per me un mistero
3m0o
Junior Member
Junior Member
 
Messaggio: 338 di 447
Iscritto il: 02/01/2018, 16:00

Re: Retta di distanza ottimale da punti

Messaggioda Bokonon » 11/06/2019, 18:27

Faccio un po' di chiarezza a partire dalla matrice A.
3m0o ha scritto:\( A = \begin{pmatrix}
(a_1 - z)^T\\
\vdots\\
(a_m-z)^T
\end{pmatrix} \)

Mettiamo $z={0}$. $A_0$ è una matrice mxn la cui somma delle righe è zero.
Usiamo l'esempio che hai fornito:
$ A_0=( ( 1 , 0 ),( 0 , 1 ),( -1 , 0 ),( 0 , -1 ) ) $
Quindi $m=4$ $n=2$. A me sta benissimo così perchè in effetti le matrici con cui si lavora sono tutte di questo tipo con $m>" >n$ dove le colonne rappresentano le variabili e le righe il campione rilevato e $A^TA$ è una matrice simmetrica invertibile.
Quindi con somma delle componenti intendo proprio gli elementi di ogni colonna...quindi gli $a_i$ sono le righe (ovvero le osservazioni campionarie) e tutto torna. Vedi io di solito chiamo gli $a_i$ le colonne/variabili, da qua la mia confusione.

Non ti annoio con la statistica (per ora :-D ) ma userò l'algebra lineare e farò un ragionamento (classico).
Supponiamo di avere un sistema $A_0x=w$ che non ha soluzione perchè w non si trova nello span dell'immagine di A.
Ma vogliamo comunque risolverlo, come? Troviamo un vettore v che stia nell'immagine per rimpazzare w.
Ma non un v qualsiasi: vogliamo che v sia la proiezione ortogonale di w sull'immagine.
Questo è il metodo dei minimi quadrati o regressione alla media. Nella sostanza troviamo la retta che passa per l'origine per cui la somma delle distanze (in modulo) di tutti $a_i$ è minima. Infatti li proiettiamo ortogonalmente, quindi la distanza è la più piccola possibile e visto che le differenze sono vettori ortogonali, usando pitagora, anche la somma dei quadrati delle distanze sarà la minore possibile.

Ora non so per quale motivo, il libro stia facendo un ragionamento al contrario, in cui non hai un vincolo w e lavori già nello spazio dell'immagine.
In pratica parte ponendo z=0 e ti dice che hai già v passante per l'origine.
Torniamo all'esempio. $A_0$ ha già le colonne depurate dalla loro media, come lo so? Perchè come hai detto deve essere il baricentro! E' la proprietà fondamentale della media aritmetica.
Infatti $ sum_(i=1)^(m) (a_i-z)=0 rArr sum_(i=1)^(m) a_i-mz=0 rArr z=1/msum_(i=1)^(m) a_i=M(z) $
z è il vettore delle medie delle righe di $A^T$
E ora guardiamo cosa accade se facciamo:
$ A_0^TA_0=( ( 1 , 0 , -1 , 0 ),( 0 , 1 , 0 , 1 ) ) ( ( 1 , 0 ),( 0 , 1 ),( -1 , 0 ),( 0 , -1 ) ) =( ( 2 , 0 ),( 0 , 2 ) ) $
Lungo la diagonale ci sono le norme al quadrato dei vettori colonna, in gergo statistico le devianze delle due variabili/colonne. Fuori dalla diagonale ci sono i prodotti scalari fra variabili/colonne, in gergo le codevianze (e sono tutte zero perchè le variabili/colonne sono ortogonali).
Gli autovettori sono la base canonica e sono associati ad un unico autovalore 2.
Se facessimo $ A_0^TA_0v=2v$ per qualsiasi v...per ovvie ragioni visto che si trova già nell'unico autospazio possibile.
Questo spiega perchè in generale non si possa affermare che v sia unico.

Mi fermo qua per ora. Ma dovresti "vedere" da dove salta fuori il vettore delle medie z e dovresti intuire che se sposti il baricentro, allora fissato un v le distanze saranno sempre superiori.
Avatar utente
Bokonon
Senior Member
Senior Member
 
Messaggio: 1395 di 1544
Iscritto il: 25/05/2018, 21:22

Re: Retta di distanza ottimale da punti

Messaggioda 3m0o » 11/06/2019, 19:24

Allora, mi è già un po' più chiaro, però noi abbiamo un approccio diverso (non statistico, anche perché statistica la farò al secondo anno).
Dato un sistema lineare (1) \( Ax=b \) che non ha soluzione, per trovare il \( x \) ottimale ci è stato spiegato di utilizzare appunto il metodo dei minimi quadrati e dunque \( x \) ottimale di (1) se e solo se è soluzione di questo sistema \( A^T A x = A^T b \).
Oppure se e solo se \( x = A^{+} b \) dove con \( A^{+} \) indico la pseudo-inversa di \( A \), effettivamente perché diagonalizzando \( A^T A \) (ed è sempre possibile in quanto simmetrica ), ottengo come autovalori il quadrato dei valori singolari che poi utilizzo nella decomposizione SVD dove \( A^+ = Q^* D^+ P^* \) dove \( Q,P \) unitarie (otrogonali) e \( D^+ \) la pseudo inversa di \( D \) sulle cui diagonali ci sono i valori singolari.
Questo per trovare un punto ottimale di distanza.

Mentre dati \( m \) punti gli \( a_i \), per trovare uno spazio \(H\) ottimale (ovvero la cui somma delle distanze ai miei punti al quadrato sia minimizzata) una cui base ortonormale è data da \( \{ u_1, \ldots, u_k \} \) di dimensione al più \( k \), ( \( \dim L_{z,v} = 1 \) ),
mi dice che lo spazio H che minimizza \( \sum_i d(H,a_i)^2 \) è lo spazio che massimizza (non mi è molto chiaro)
\[ \sum_i \sum\limits_{j=1}^{k} <a_i, u_i >^2 = \sum\limits_{j=1}^{k} u_j^T A^T A u_j \]
E dunque con \( k=1 \) la soluzione ottimale è \( x = \max_{u \in S^{n-1}} u^TA^T Au \);
dove \( A = (a_1 \ldots a_m)^T \)
E sappiamo che questo massimo è raggiunto con \( u_1 \) associato al autovalore \( \lambda_1 \) di \( A^T A \) ordinati in questo modo \( \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda _r \geq 0\)
Bene!

Cerco di applicare ciò al mio problema,
devo cercare uno spazio di dimensione \( 1 \) \( L_{z,v} \) che mi minimizza le distanze dai punti \( a_i \). Fissiamo un \( z \) arbitrario.
Sia \( H_v = \operatorname{span} \{v\} \), abbiamo che \( L_{z,v} = \{ z + H_{v} \} \).
Quindi se \( d(a_i, L_{z,v})=d(a_i-z, H_v) \). Pertanto posso applicare il teorema sopra e trovare che \( H_v \) ottimale è dato da... \( v= \max_{u \in S^{n-1}} u^T \tilde{A}^T \tilde{A} u \);
dove \( \tilde{A} = ( a_1 - z \ldots a_m - z)^T \).


Bene ora abbiamo trovato uno spazio ottimale associato ad ogni \( z \), ora il problema si conduce a trovare il \( z \) tale che lo spazio associato \( H_{v} \) minimizzi più di tutti gli altri \(H_{v'} \) associati ad un \(z' \) la distanza con i miei \( a_1, \ldots, a_m \) punti.
E qui non capisco il motivo per cui egli dice e anche tu mi dici che è semplicemente il \( z \) definito come il baricentro dei punti \( a_i \)... mi sfugge.
3m0o
Junior Member
Junior Member
 
Messaggio: 341 di 447
Iscritto il: 02/01/2018, 16:00

Re: Retta di distanza ottimale da punti

Messaggioda Bokonon » 11/06/2019, 21:13

Proviamo a ripercorrere il ragionamento del libro.
Il libro usa $a_i$ in due casistiche diverse.
Nella prima pone a priori che $sum a_i=0$ e ti chiede appunto di dimostrare che la somma delle distanze degli $a_i$ da una retta che non passa per l'origine (traslata) è sempre $>=$ alla somma delle distanza dalla medesima retta che passa per l'origine.
Nella seconda casistica non impone più il vincolo $sum a_i=0$ (diventano generici).
Stavolta ci sarà una retta ottimale generica che non passa per l'origine del tipo $z+lambdav$ quindi per dimostrane l'ottimalità troviamo uno z in modo da trasformare gli $a_i$ in modo da ottenere la retta $lambdav$. Ovvero trova una trasformazione $y_i=a_i-z$ tale che $sum y_i=0$
Una volta fatto, sai già che $lambdav$ è la retta ottimale per gli $y_i$ (lo hai dimostrato al punto 1 dove li chiamavi $a_i$) ed hai anche trovato il vettore z e quindi la retta $z+lambdav$ ottimale per gli $a_i$
Ora quale traslazione sposta tutti gli $a_i$ in modo che abbiano un baricentro nell'origine?
E questo lo abbiamo visto...sono le medie aritmetiche. E più semplice se consideri i due vettori colonna di A.
La prima colonna contiene tutte le componenti $x$ degli $a_i$, la seconda seconda le componenti $y$ etc etc.
Ora, se prendi tutte le componenti dei vettori $a_i$ che stanno sull'asse x e sottrai la loro media allora hai spostato il baricentro sullo zero lungio l'asse X. Fallo anche per le componenti y, z, w etc etc e alla fine tutte le componenti saranno centrate nell'origine. No?
Una volts spostato il baricentro globale si torna al caso 1 e si dice" Ok, sappiamo già che v è la retta ottimale per gli $y_i$ quindi quella per gli $a_i$ sarà v traslata dal vettore delle medie delle componenti degli $a_i$, ovvero z".

Questo era l'ordine logico! Fai il caso uno e poi riportati in quella casisistica trovando la traslazione lungo tutti gli assi che mi riporti il baricentro a zero.
Avatar utente
Bokonon
Senior Member
Senior Member
 
Messaggio: 1400 di 1544
Iscritto il: 25/05/2018, 21:22

Re: Retta di distanza ottimale da punti

Messaggioda 3m0o » 14/06/2019, 01:49

Chiarissimo!
3m0o
Junior Member
Junior Member
 
Messaggio: 343 di 447
Iscritto il: 02/01/2018, 16:00

Re: Retta di distanza ottimale da punti

Messaggioda Bokonon » 14/06/2019, 20:42

Un ultima cosa, sullo spazio ottimale H.
E' il teorema di Eckart-Young (usando la metrica spettrale).
https://en.wikipedia.org/wiki/Low-rank_approximation

E' il discorso sulle componenti principali che feci qualche tempo e su come si possa derivare una matrice ridotta che spieghi la maggior parte della variabilità delle colonne della A originaria.
Onestamente non avevo mai visto la prova matematica di tutto ciò prima di un mesetto fa, ovvero quando ho visto che il MIT ha rilasciato le "nuove" lezioni di Strang.
https://www.youtube.com/playlist?list=P ... kS2PivhN3k
Praticamente si occupa di questo problema nelle lezioni fra 6 e 11
Avatar utente
Bokonon
Senior Member
Senior Member
 
Messaggio: 1405 di 1544
Iscritto il: 25/05/2018, 21:22


Torna a Geometria e algebra lineare

Chi c’è in linea

Visitano il forum: Nessuno e 9 ospiti