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

Στα μαθηματικά, ένας Πίνακας ευκλείδειας απόστασης είναι ένας πίνακας n×n που αναπαριστά την απόσταση ενός συνόλου n σημείων στον ευκλείδειο χώρο. Για τα σημεία $x_{1},x_{2},\ldots ,x_{n}$ στον k-διάστατο χώρο ℝ^k, τα στοιχεία του πίνακα ευκλείδειων αποστάσεων A τους δίνονται από τα τετράγωνα των αποστάσεων μεταξύ τους. Δηλαδή

${\begin{aligned}A&=(a_{ij});\\a_{ij}&=d_{ij}^{2}\;=\;\lVert x_{i}-x_{j}\rVert ^{2}\end{aligned}}$

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

$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 έχει τις ακόλουθες ιδιότητες.

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

Στη διάσταση k, ένας πίνακας ευκλείδειας απόστασης έχει βαθμό μικρότερο ή ίσο με k+2. Αν τα σημεία $x_{1},x_{2},\ldots ,x_{n}$ βρίσκονται σε γενική θέση, ο βαθμός είναι ακριβώς min(n, k + 2).

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

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

Ο πίνακας Γκραμ μιας ακολουθίας σημείων $x_{1},x_{2},\ldots ,x_{n}$ στον k-διάστατο χώρο ℝ^k είναι ο n×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$ ο k×n πίνακας που περιέχει $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}$ μεταξύ ζευγών σημείων n+1 $x_{0},x_{1},\ldots ,x_{n}$ καθορίζουν τα γινόμενα τελείας μεταξύ των διανυσμάτων n $x_{i}-x_{0}$ (1≤i≤n):

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

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

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

Για έναν n×n πίνακα A, μια ακολουθία σημείων $x_{1},x_{2},\ldots ,x_{n}$ στον ℝ^k-διάστατο ευκλείδειο χώρο ℝ^k ονομάζεται υλοποίηση του A στον ℝ^k αν A είναι ο πίνακας ευκλείδειας απόστασής τους. Μπορούμε να υποθέσουμε χωρίς απώλεια γενικότητας ότι $x_{1}=\mathbf {0}$ (επειδή η μετατόπιση κατά $-x_{1}$ διατηρεί τις αποστάσεις).

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

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

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

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

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

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

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

'Επακόλουθο

Ένας συμμετρικός κοίλος n×n πίνακας A με πραγματικές καταχωρήσεις δέχεται μια υλοποίηση εάν και μόνο εάν οA είναι αρνητικά ημιορισμένος στο υπερεπίπεδο $H=\{v\in \mathbf {R} ^{n}\colon e^{\textsf {T}}v=0\}$, that is

$v^{\textsf {T}}Av\leq 0$ για κάθε $v\in \mathbf {R} ^{n}$ έτσι ώστε $\textstyle \sum _{i=1}^{n}v_{i}=0$.

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

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

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

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

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

Θεώρημα

Έστω $x_{1},x_{2},\ldots ,x_{n}$ και $y_{1},y_{2},\ldots ,y_{n}$ δύο ακολουθίες σημείων στον k-διάστατο Ευκλείδειο χώρο ℝ^k.

Οι αποστάσεις $\|x_{i}-x_{j}\$ and $\|y_{i}-y_{j}\$ είναι ίσες (για όλα τα 1≤i,j≤n) αν και μόνο αν υπάρχει ένας άκαμπτος μετασχηματισμός του ℝ^k που απεικονίζει το $x_{i}$ στο $y_{i}$ (για όλα τα 1≤i≤n).

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

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

• Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf. 
• Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9. 
• Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244. 
• Bareiss, E. H. (1969), «Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices», Numerische Mathematik 13 (5): 404–424, doi:10.1007/BF02163269 
• Goldreich, O.; Tal, A. (2018), «Matrix rigidity of random Toeplitz matrices», Computational Complexity 27 (2): 305–350, doi:10.1007/s00037-016-0144-9 
• 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

Παραπομπές

• Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin (2015). «Euclidean Distance Matrices: Essential theory, algorithms, and applications». IEEE Signal Processing Magazine 32 (6): 12–30. doi:10.1109/MSP.2015.2398954. ISSN 1558-0792. 
• James E. Gentle (2007). Matrix Algebra: Theory, Computations, and Applications in Statistics. Springer-Verlag. σελ. 299. ISBN 978-0-387-70872-0. 
• So, Anthony Man-Cho (2007). A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions (PDF) (PhD) (στα Αγγλικά). 
• Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Mucherino, Antonio (2014). «Euclidean Distance Geometry and Applications» (στα αγγλικά). SIAM Review 56 (1): 3–69. doi:10.1137/120875909. ISSN 0036-1445. 
• Alfakih, Abdo Y. (2018). Euclidean Distance Matrices and Their Applications in Rigidity Theory (στα Αγγλικά). Cham: Springer International Publishing. doi:10.1007/978-3-319-97846-8. ISBN 978-3-319-97845-1.