Πίνακας Ευκλείδειας απόστασης

Στα μαθηματικά, ένας Πίνακας ευκλείδειας απόστασης είναι ένας πίνακας Πρότυπο:Math που αναπαριστά την απόσταση ενός συνόλου n σημείων στον ευκλείδειο χώρο. Για τα σημεία $x_1,x_2,\dots ,x_n$ στον Πρότυπο:Mvar-διάστατο χώρο Πρότυπο:Math, τα στοιχεία του πίνακα ευκλείδειων αποστάσεων Πρότυπο:Mvar τους δίνονται από τα τετράγωνα των αποστάσεων μεταξύ τους. Δηλαδή

$\begin{array}{cc}A& =(a_{ij});\\ a_{ij}& =d_{ij}^2=\Vert x_i-x_j{\Vert }^2\end{array}$

όπου $\Vert \cdot \Vert$ συμβολίζει την ευκλείδεια νόρμα στο Πρότυπο:Math.

$A=\left[\begin{array}{ccccc}0& d_{12}^2& d_{13}^2& \dots & d_{1n}^2\\ d_{21}^2& 0& d_{23}^2& \dots & d_{2n}^2\\ d_{31}^2& d_{32}^2& 0& \dots & d_{3n}^2\\ ⋮& ⋮& ⋮& \ddots & ⋮& \\ d_{n1}^2& d_{n2}^2& d_{n3}^2& \dots & 0\end{array}\right]$

Στο πλαίσιο των πινάκων (όχι απαραίτητα ευκλείδειων) αποστάσεων, οι καταχωρήσεις ορίζονται συνήθως απευθείας ως αποστάσεις και όχι ως τα τετράγωνά τους. Ωστόσο, στην ευκλείδεια περίπτωση, τα τετράγωνα των αποστάσεων χρησιμοποιούνται για την αποφυγή υπολογισμού τετραγωνικών ριζών και για την απλοποίηση σχετικών θεωρημάτων και αλγορίθμων.

Οι πίνακες ευκλείδειας απόστασης είναι στενά συνδεδεμένοι με τους πίνακες Γκραμ (πίνακες τετραγωνικών γινομένων, που περιγράφουν τις νόρμες των διανυσμάτων και τις γωνίες μεταξύ τους). Οι τελευταίοι αναλύονται εύκολα με μεθόδους της γραμμικής άλγεβρας. Αυτό επιτρέπει τον χαρακτηρισμό των πινάκων ευκλείδειας απόστασης και την ανάκτηση των σημείων $x_1,x_2,\dots ,x_n$ που τον υλοποιούν. Μια υλοποίηση, αν υπάρχει, είναι μοναδική μέχρι άκαμπτους μετασχηματισμούς, δηλαδή μετασχηματισμούς του Ευκλείδειου χώρου που διατηρούν την απόσταση (περιστροφές, ανακλάσεις, μεταφορές).

Στις πρακτικές εφαρμογές, οι αποστάσεις είναι θορυβώδεις μετρήσεις ή προέρχονται από αυθαίρετες εκτιμήσεις ανομοιότητας (όχι απαραίτητα μετρικές). Ο στόχος μπορεί να είναι η οπτικοποίηση τέτοιων δεδομένων με σημεία στον ευκλείδειο χώρο, των οποίων ο πίνακας αποστάσεων προσεγγίζει όσο το δυνατόν καλύτερα έναν δεδομένο πίνακα ανομοιότητας - αυτό είναι γνωστό ως πολυδιάστατη κλιμάκωση. Εναλλακτικά, δεδομένου ότι δύο σύνολα δεδομένων έχουν ήδη αναπαρασταθεί με σημεία στον ευκλείδειο χώρο, μπορεί να τεθεί το ερώτημα πόσο παρόμοια είναι στο σχήμα τους, δηλαδή πόσο στενά μπορούν να συσχετιστούν με έναν μετασχηματισμό που διατηρεί την απόσταση - αυτό είναι η ανάλυση Προκρούστη. Ορισμένες από τις αποστάσεις μπορεί επίσης να λείπουν ή να έρχονται χωρίς ετικέτα (ως μη ταξινομημένο σύνολο ή πολυσύνολο αντί για πίνακα), οδηγώντας σε πιο σύνθετες αλγοριθμικές εργασίες, όπως το πρόβλημα της υλοποίησης γραφημάτων ή το πρόβλημα της στροφής (για σημεία σε μια γραμμή).

Ιδιότητες

Από το γεγονός ότι η Ευκλείδεια απόσταση είναι μια μετρική, ο πίνακας Πρότυπο:Mvar έχει τις ακόλουθες ιδιότητες.

• Όλα τα στοιχεία στη διαγώνιο του Πρότυπο:Mvar είναι μηδενικά (δηλαδή είναι ένας κοίλος πίνακας)- συνεπώς το ίχνος του Πρότυπο:Mvar είναι μηδέν.
• Πρότυπο:Mvar είναι συμμετρικός (δηλαδή $a_{ij}=a_{ji}$).
• $\sqrt{a_{ij}}\le \sqrt{a_{ik}}+\sqrt{a_{kj}}$ (από την τριγωνική ανισότητα)
• $a_{ij}\ge 0$

Στη διάσταση Πρότυπο:Mvar, ένας πίνακας ευκλείδειας απόστασης έχει βαθμό μικρότερο ή ίσο με Πρότυπο:Math. Αν τα σημεία $x_1,x_2,\dots ,x_n$ βρίσκονται σε γενική θέση, ο βαθμός είναι ακριβώς Πρότυπο:Math

Οι αποστάσεις μπορούν να συρρικνωθούν με οποιαδήποτε δύναμη για να προκύψει ένας άλλος πίνακας ευκλείδειας απόστασης. Δηλαδή, αν $A=(a_{ij})$ είναι ένας πίνακας ευκλείδειας απόστασης, τότε $({a_{ij}}^s)$ είναι ένας πίνακας ευκλείδειας απόστασης για κάθε Πρότυπο:Math.

Σχέση με τον πίνακα Γκραμ

Ο πίνακας Γκραμ μιας ακολουθίας σημείων $x_1,x_2,\dots ,x_n$ στον Πρότυπο:Mvar-διάστατο χώρο Πρότυπο:Math είναι ο Πρότυπο:Math πίνακας $G=(g_{ij})$ των τετραγωνικών γινομένων τους (εδώ ένα σημείο $x_i$ θεωρείται ως ένα διάνυσμα από το 0 στο σημείο αυτό):

$g_{ij}=x_i\cdot x_j=\Vert x_i\Vert \Vert x_j\Vert \cos \theta$, όπου $\theta$ είναι η γωνία μεταξύ του διανύσματος $x_i$ και $x_j$.

Ειδικότερα

$g_{ii}=\Vert x_i{\Vert }^2$ είναι το τετράγωνο της απόστασης of $x_i$ από το 0.

Έτσι, ο πίνακας Γκραμ περιγράφει τις νόρμες και τις γωνίες των διανυσμάτων (από 0 έως) $x_1,x_2,\dots ,x_n$.

Έστω $X$ ο Πρότυπο:Math πίνακας που περιέχει $x_1,x_2,\dots ,x_n$ ως στήλες. Τότε

$G=X^{\mathsf{\text{T}}}X$, διότι $g_{ij}=x_i^{\mathsf{\text{T}}}{x}_j$ (βλέποντας $x_i$ ως διάνυσμα στήλης).

Οι πίνακες που μπορούν να αναλυθούν ως $X^{\mathsf{\text{T}}}X$, δηλαδή πίνακες Γκραμ κάποιας ακολουθίας διανυσμάτων (στήλες του $X$), είναι ευρέως γνωστοί- συγκεκριμένα πρόκειται για θετικούς ημιορισμένους πίνακες.

Για να συσχετίσουμε τον πίνακα ευκλείδειας απόστασης με τον πίνακα Γκραμ, παρατηρούμε ότι

$d_{ij}^2=\Vert x_i-x_j{\Vert }^2=(x_i-x_j{)}^{\mathsf{\text{T}}}(x_i-x_j)=x_i^{\mathsf{\text{T}}}{x}_i-2x_i^{\mathsf{\text{T}}}{x}_j+x_j^{\mathsf{\text{T}}}{x}_j=g_{ii}-2g_{ij}+g_{jj}$

Δηλαδή, οι νόρμες και οι γωνίες καθορίζουν τις αποστάσεις. Ας σημειωθεί ότι ο πίνακας Γκραμ περιέχει πρόσθετες πληροφορίες: αποστάσεις από το 0.

Αντίστροφα, οι αποστάσεις $d_{ij}$ μεταξύ ζευγών σημείων Πρότυπο:Math $x_0,x_1,\dots ,x_n$ καθορίζουν τα γινόμενα τελείας μεταξύ των διανυσμάτων Πρότυπο:Mvar $x_i-x_0$ (Πρότυπο:Math):

$g_{ij}=(x_i-x_0)\cdot (x_j-x_0)=\frac{1}{2}(\Vert x_i-x_0{\Vert }^2+\Vert x_j-x_0{\Vert }^2-\Vert x_i-x_j{\Vert }^2)=\frac{1}{2}(d_{0i}^2+d_{0j}^2-d_{ij}^2)$

(αυτό είναι γνωστό ως ταυτότητα πόλωσης).

Χαρακτηρισμοί

Για έναν Πρότυπο:Math πίνακα Πρότυπο:Mvar, μια ακολουθία σημείων $x_1,x_2,\dots ,x_n$ στον Πρότυπο:Math-διάστατο ευκλείδειο χώρο Πρότυπο:Math ονομάζεται υλοποίηση του Πρότυπο:Mvar στον Πρότυπο:Math αν Πρότυπο:Mvar είναι ο πίνακας ευκλείδειας απόστασής τους. Μπορούμε να υποθέσουμε χωρίς απώλεια γενικότητας ότι $x_1=\mathrm{𝟎}$ (επειδή η μετατόπιση κατά $-x_1$ διατηρεί τις αποστάσεις).

Μαθηματικό θεώρημα

Κριτήριο Σένμπεργκ, ανεξάρτητα από τον Γιανγκ &Χάουζχολντερ

Ένας συμμετρικός κοίλος Πρότυπο:Math πίνακας Πρότυπο:Mvar με πραγματικές εισόδους δέχεται μια υλοποίηση στο Πρότυπο:Math αν και μόνο αν ο Πρότυπο:Math πίνακας $G=(g_{ij}{)}_{2\le i,j\le n}$ ορίζεται από

$g_{ij}=\frac{1}{2}(a_{1i}^2+a_{1j}^2-a_{ij}^2)$

είναι θετικά ημιορισμένος και έχει βαθμό το πολύ Πρότυπο:Mvar.

Αυτό προκύπτει από την προηγούμενη συζήτηση επειδή ο Πρότυπο:Mvar είναι θετικά ημιορισμένος με βαθμό το πολύ Πρότυπο:Mvar αν και μόνο αν μπορεί να αναλυθεί ως $G=X^{\mathsf{\text{T}}}X$ όπου Πρότυπο:Mvar είναι ένας πίνακας Πρότυπο:Math matrix.. Επιπλέον, οι στήλες του Πρότυπο:Mvar δίνουν μια υλοποίηση στο Πρότυπο:Math. Επομένως, οποιαδήποτε μέθοδος αποσύνθεσης του Πρότυπο:Mvar επιτρέπει την εύρεση μιας υλοποίησης. Οι δύο κύριες προσεγγίσεις είναι παραλλαγές της αποσύνθεσης Τσολέσκι ή η χρήση φασματικών αναλύσεων για την εύρεση της κύριας τετραγωνικής ρίζας του Πρότυπο:Mvar, βλέπε Ορισμένος πίνακας#Ανάλυση.

Η πρόταση του θεωρήματος διακρίνει το πρώτο σημείο $x_1$. Μια πιο συμμετρική παραλλαγή του ίδιου θεωρήματος είναι η ακόλουθη:

'Επακόλουθο

Ένας συμμετρικός κοίλος Πρότυπο:Math πίνακας Πρότυπο:Mvar με πραγματικές καταχωρήσεις δέχεται μια υλοποίηση εάν και μόνο εάν οΠρότυπο:Mvar είναι αρνητικά ημιορισμένος στο υπερεπίπεδο $H=\{v\in {𝐑}^n:e^{\mathsf{\text{T}}}v=0\}$, that is

$v^{\mathsf{\text{T}}}Av\le 0$ για κάθε $v\in {𝐑}^n$ έτσι ώστε ${\sum }_{i=1}^n{v}_i=0$.

Άλλοι χαρακτηρισμοί αφορούν τις ορίζουσες Κέιλι - Μένγκερ. Συγκεκριμένα, αυτές επιτρέπουν να δείξουμε ότι ένας συμμετρικός κοίλος πίνακας Πρότυπο:Math είναι υλοποιήσιμος στο Πρότυπο:Math αν και μόνο αν κάθε Πρότυπο:Math κύριος υποπίνακας είναι. Με άλλα λόγια, ένα ημιμετρικό σε πεπερασμένα πολλά σημεία είναι ενσωματώσιμο ισομετρικά στο Πρότυπο:Math αν και μόνο αν κάθε Πρότυπο:Math σημεία είναι.

Στην πράξη, οι συνθήκες οριστικότητας ή κατάταξης μπορεί να αποτύχουν λόγω αριθμητικών σφαλμάτων, θορύβου στις μετρήσεις ή λόγω του ότι τα δεδομένα δεν προέρχονται από πραγματικές ευκλείδειες αποστάσεις. Τα σημεία που υλοποιούν βέλτιστα παρόμοιες αποστάσεις μπορούν στη συνέχεια να βρεθούν με ημιοριστική προσέγγιση (και προσέγγιση χαμηλής τάξης, εάν είναι επιθυμητό) χρησιμοποιώντας εργαλεία γραμμικής άλγεβρας, όπως η ανάλυση σε ιδιάζουσες τιμές ή ο ημιοριστικός προγραμματισμός. Αυτό είναι γνωστό ως πολυδιάστατη κλιμάκωση. Παραλλαγές αυτών των μεθόδων μπορούν επίσης να αντιμετωπίσουν ελλιπή δεδομένα αποστάσεων.

Τα μη επισημειωμένα δεδομένα, δηλαδή ένα σύνολο ή ένα πολυσύνολο αποστάσεων που δεν αντιστοιχούν σε συγκεκριμένα ζεύγη, είναι πολύ πιο δύσκολο να αντιμετωπιστούν. Τέτοια δεδομένα προκύπτουν, παραδείγματος χάριν, στην αλληλούχιση DNA (συγκεκριμένα, ανάκτηση γονιδιώματος από μερική πέψη) ή στην ανάκτηση φάσεων. Δύο σύνολα σημείων ονομάζονται ομομετρικά εάν έχουν το ίδιο πολυσύνολο αποστάσεων (αλλά δεν συνδέονται απαραίτητα με άκαμπτο μετασχηματισμό). Η απόφαση για το αν ένα δεδομένο πολυσύνολο Πρότυπο:Math αποστάσεων μπορεί να πραγματοποιηθεί σε μια δεδομένη διάσταση Πρότυπο:Mvar είναι έντονα NP-δύσκολη. Σε μία διάσταση αυτό είναι γνωστό ως το πρόβλημα της στροφής- είναι ένα ανοικτό ερώτημα αν μπορεί να επιλυθεί σε πολυωνυμικό χρόνο. Όταν το πολυσύνολο των αποστάσεων δίνεται με ράβδους σφάλματος, ακόμη και η περίπτωση της μίας διάστασης είναι NP-δύσκολη. Παρ' όλα αυτά, υπάρχουν πρακτικοί αλγόριθμοι για πολλές περιπτώσεις, π.χ. για τυχαία σημεία.

Μοναδικότητα των αναπαραστάσεων

Δεδομένου ενός πίνακα ευκλείδειας απόστασης, η ακολουθία των σημείων που τον υλοποιούν είναι μοναδική μέχρι άκαμπτων μετασχηματισμών - πρόκειται για ισομετρίες του ευκλείδειου χώρου: περιστροφές, ανακλάσεις, μεταφορές και οι συνθέσεις τους.

Θεώρημα

Έστω $x_1,x_2,\dots ,x_n$ και $y_1,y_2,\dots ,y_n$ δύο ακολουθίες σημείων στον Πρότυπο:Mvar-διάστατο Ευκλείδειο χώρο Πρότυπο:Math.

Οι αποστάσεις

$\Vert x_i-x_j$

and

$\Vert y_i-y_j$

είναι ίσες (για όλα τα Πρότυπο:Math) αν και μόνο αν υπάρχει ένας άκαμπτος μετασχηματισμός του Πρότυπο:Math που απεικονίζει το

$x_i$

στο

$y_i$

(για όλα τα Πρότυπο:Math).

Πρότυπο:Collapse top Οι άκαμπτοι μετασχηματισμοί διατηρούν τις αποστάσεις, οπότε η μία κατεύθυνση είναι σαφής. Ας υποθέσουμε ότι οι αποστάσεις $\Vert x_i-x_j\Vert$ και $\Vert y_i-y_j\Vert$ είναι ίσες. Χωρίς απώλεια γενικότητας μπορούμε να υποθέσουμε ότι $x_1=y_1=\mathbf{\text{0}}$ μετατοπίζοντας τα σημεία κατά $-x_1$ και $-y_1$, αντίστοιχα. Τότε ο Πρότυπο:Math πίνακας Γκραμ των υπόλοιπων διανυσμάτων $x_i=x_i-x_1$ ταυτίζεται με τον πίνακα Γκραμ των διανυσμάτων $y_i$ (Πρότυπο:Math). Δηλαδή, $X^{\mathsf{\text{T}}}X=Y^{\mathsf{\text{T}}}Y$, όπου Πρότυπο:Mvar και Πρότυπο:Mvar είναι οι Πρότυπο:Math πίνακες που περιέχουν τα αντίστοιχα διανύσματα ως στήλες. Αυτό σημαίνει ότι υπάρχει ένας ορθογώνιος Πρότυπο:Math πίνακας Πρότυπο:Mvar έτσι ώστε Πρότυπο:Math, βλέπε Ορισμένος συμμετρικός πίνακας#Αδυναμία μέχρι μοναδιαίους μετασχηματισμούς. Ο Πρότυπο:Mvar περιγράφει έναν ορθογώνιο μετασχηματισμό του Πρότυπο:Math (μια σύνθεση περιστροφών και ανακλάσεων, χωρίς μετατοπίσεις) που απεικονίζει το $x_i$ to $y_i$ (και το0 στο 0). Ο τελικός άκαμπτος μετασχηματισμός περιγράφεται από τη σχέση $T(x)=Q(x-x_1)+y_1$. Πρότυπο:Collapse bottom

Σε εφαρμογές, όταν οι αποστάσεις δεν ταιριάζουν ακριβώς, η ανάλυση Προκρούστη αποσκοπεί στο να συσχετίσει δύο σύνολα σημείων όσο το δυνατόν πιο κοντά μέσω άκαμπτων μετασχηματισμών, συνήθως με τη χρήση της αποσύνθεσης μοναδιαίων τιμών. Η συνήθης ευκλείδεια περίπτωση είναι γνωστή ως το ορθογώνιο πρόβλημα Προκρούστη ή το πρόβλημα του Γουάμπα (όταν οι παρατηρήσεις σταθμίζονται για να ληφθούν υπόψη ποικίλες αβεβαιότητες). Παραδείγματα εφαρμογών περιλαμβάνουν τον προσδιορισμό του προσανατολισμού δορυφόρων, τη σύγκριση της δομής μορίων (στη χημειοπληροφορική), τη δομή πρωτεϊνών (δομική ευθυγράμμιση στη βιοπληροφορική) ή τη δομή οστών (στατιστική ανάλυση σχήματος στη βιολογία).

Δημοσιεύσεις

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Citation
• Diodorus Siculus, Bibliotheca Historica. Vol. 1–2. Immanel Bekker. Ludwig Dindorf. Friedrich Vogel. in aedibus B. G. Teubneri. Leipzig. 1888–1890. Greek text available at the Perseus Digital Library.
• Gaius Julius Hyginus, Fabulae from The Myths of Hyginus translated and edited by Mary Grant. University of Kansas Publications in Humanistic Studies. Online version at the Topos Text Project.
• Lucius Mestrius Plutarchus, Lives with an English Translation by Bernadotte Perrin. Cambridge, MA. Harvard University Press. London. William Heinemann Ltd. 1914. 1. Online version at the Perseus Digital Library. Greek text available from the same website.
• Pausanias, Description of Greece with an English Translation by W. H. S. Jones, Litt.D., and H. A. Ormerod, M.A., in 4 Volumes. Cambridge, MA, Harvard University Press; London, William Heinemann Ltd. 1918. Online version at the Perseus Digital Library

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Πίνακας Γκραμ
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Διανυσματικός χώρος
• Παραμετρικές εξισώσεις
• Πολλαπλασιασμός πινάκων
• Ρητή συνάρτηση
• Ανάλυση πίνακα σε ιδιάζουσες τιμές
• Αντιστρέψιμος πίνακας
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Euclidean Distance Matrices and Their Applications in Rigidity Theory.
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Random Tensors..
• Euclidean Distance Geometry: An Introduction .....
• Handbook on Semidefinite, Conic and Polynomial Optimization
• Lectures on the Combinatorics of Free Probability, Τόμος 13

Παραπομπές

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite thesis
• Πρότυπο:Cite journal
• Πρότυπο:Cite book