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

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

:\begin{align}
A & = (a_{ij}); \\
a_{ij} & = d_{ij}^2 \;=\; \lVert x_i - x_j\rVert^2
\end{align}


όπου \|\cdot\| συμβολίζει την ευκλείδεια νόρμα στο .

:A = \begin{bmatrix}
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 \\
\vdots&\vdots & \vdots & \ddots&\vdots&  \\
d_{n1}^2 & d_{n2}^2 & d_{n3}^2 & \dots & 0 \\
\end{bmatrix} 

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

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

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

## Ιδιότητες

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

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

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

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

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

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

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

Ειδικότερα
: g_{ii} = \|x_i\|^2 είναι το τετράγωνο της απόστασης of x_i από το **0**.

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

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

: G = X^\textsf{T} X, διότι  g_{ij} = x_i^\textsf{T} x_j (βλέποντας  x_i ως διάνυσμα στήλης).
Οι πίνακες που μπορούν να αναλυθούν ως X^\textsf{T}X, δηλαδή πίνακες Γκραμ κάποιας ακολουθίας διανυσμάτων (στήλες του X), είναι ευρέως γνωστοί- συγκεκριμένα πρόκειται  για θετικούς ημιορισμένους πίνακες.

Για να συσχετίσουμε τον πίνακα ευκλείδειας απόστασης με τον πίνακα Γκραμ, παρατηρούμε ότι 
: d_{ij}^2 = \|x_i - x_j\|^2 = (x_i - x_j)^\textsf{T} (x_i - x_j) = x_i^\textsf{T} x_i - 2x_i^\textsf{T} x_j + x_j^\textsf{T} x_j = g_{ii} -2g_{ij} + g_{jj}

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

Αντίστροφα, οι αποστάσεις d_{ij} μεταξύ ζευγών σημείων  x_0,x_1,\ldots,x_n καθορίζουν τα γινόμενα τελείας μεταξύ των διανυσμάτων  x_i-x_0 ():
: g_{ij} = (x_i-x_0) \cdot (x_j-x_0) = \frac{1}{2}\left(\|x_i-x_0\|^2 + \|x_j-x_0\|^2 - \|x_i - x_j\|^2 \right) = \frac{1}{2}(d_{0i}^2 + d_{0j}^2 - d_{ij}^2)

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

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

Για έναν  πίνακα , μια ακολουθία σημείων x_1,x_2,\ldots,x_n στον -διάστατο ευκλείδειο χώρο  ονομάζεται υλοποίηση του  στον  αν  είναι ο πίνακας ευκλείδειας απόστασής τους. Μπορούμε να υποθέσουμε χωρίς απώλεια γενικότητας ότι x_1 = \mathbf{0} (επειδή η μετατόπιση κατά -x_1 διατηρεί τις αποστάσεις).

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

Ένας συμμετρικός κοίλος  πίνακας  με πραγματικές εισόδους δέχεται μια υλοποίηση στο  αν και μόνο αν ο  πίνακας G = (g_{ij})_{2 \leq i,j \leq n} ορίζεται από
: g_{ij} = \frac{1}{2}(a_{1i}^2 + a_{1j}^2 - a_{ij}^2)

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

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

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

**'Επακόλουθο** 
Ένας συμμετρικός κοίλος  πίνακας   με πραγματικές καταχωρήσεις δέχεται μια υλοποίηση εάν και μόνο εάν ο
είναι αρνητικά ημιορισμένος στο υπερεπίπεδο H=\{v \in \mathbf{R}^n \colon e^\textsf{T}v = 0\}, that is
: v^\textsf{T} A v \leq 0 για κάθε v \in \mathbf{R}^n έτσι ώστε \textstyle\sum_{i=1}^n v_i = 0. 

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

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

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

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

**Θεώρημα**
Έστω x_1,x_2,\ldots,x_n και y_1,y_2,\ldots,y_n δύο ακολουθίες σημείων στον -διάστατο Ευκλείδειο χώρο .
Οι αποστάσεις \|x_i-x_j\  and \|y_i-y_j\  είναι ίσες (για όλα τα ) αν και μόνο αν υπάρχει ένας άκαμπτος μετασχηματισμός του  που απεικονίζει το x_i στο y_i (για όλα τα ).

Οι άκαμπτοι μετασχηματισμοί διατηρούν τις αποστάσεις, οπότε η μία κατεύθυνση είναι σαφής. Ας υποθέσουμε ότι οι αποστάσεις \|x_i-x_j\| και \|y_i-y_j\| είναι ίσες.
Χωρίς απώλεια γενικότητας μπορούμε να υποθέσουμε ότι x_1=y_1=\textbf{0} μετατοπίζοντας τα σημεία κατά -x_1 και -y_1, αντίστοιχα.
Τότε ο  πίνακας Γκραμ των υπόλοιπων διανυσμάτων x_i=x_i-x_1 ταυτίζεται με τον πίνακα Γκραμ των διανυσμάτων y_i ().
Δηλαδή, X^\textsf{T} X = Y^\textsf{T} Y, όπου  και  είναι οι  πίνακες που περιέχουν τα αντίστοιχα διανύσματα ως στήλες. Αυτό σημαίνει ότι υπάρχει ένας ορθογώνιος  πίνακας  έτσι ώστε , βλέπε Ορισμένος συμμετρικός πίνακας#Αδυναμία μέχρι μοναδιαίους μετασχηματισμούς.
Ο  περιγράφει έναν ορθογώνιο μετασχηματισμό του  (μια σύνθεση περιστροφών και ανακλάσεων, χωρίς μετατοπίσεις) που απεικονίζει το x_i to y_i (και το**0** στο **0**).
Ο τελικός άκαμπτος μετασχηματισμός περιγράφεται από τη σχέση T(x) = Q(x-x_1)+y_1.

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

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

* 
* 
* 
*
*
* 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

## Παραπομπές

* 
* 
* 
* 
* 

 

Κατηγορία:Αριθμητική γραμμική άλγεβρα
Κατηγορία:Γραμμική άλγεβρα
Κατηγορία:Θεωρήματα της γραμμικής άλγεβρας
Κατηγορία:Πίνακες (μαθηματικά)
Κατηγορία:Θεωρία πινάκων
Κατηγορία:Μετρική γεωμετρία