Ανάλυση πίνακα σε ιδιάζουσες τιμές

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Οπτικοποίηση μίας ανάλυσης σε ιδιάζουσες τιμές ενός δισδιάστατου, πραγματικού πίνακα στρέβλωσης M. Αρχικά βλέπουμε τον μοναδιαίο δίσκο χρώματος μπλε μαζί με δύο διανύσματα της φυσικής βάσης. Στη συνέχεια , μπορούμε να δούμε την δράση του M , η οποία στρεβλώνει τον κύκλο σε έλλειψη. Η ανάλυση σε ιδιάζουσες τιμές αναλύει τον M σε τρεις απλούς μετασχηματισμούς: μία αρχική περιστροφή V*, μία αλλαγή κλίμακας Σ κατά μήκος των συντεταγμένων αξόνων , και μία τελική περιστροφή U. Τα μήκη σ1 και σ2 των ημιαξόνων της έλλεψης είναι οι ιδιάζουσες τιμές του M, δηλαδή τα Σ1,1 και Σ2,2.

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

Η ανάλυση ενός m×n πίνακα M, με πραγματικά ή μιγαδικά στοιχεία, σε ιδιάζουσες τιμές είναι μια παραγοντοποίηση της μορφής

όπου U είναι ένας m×m πραγματικός ή μιγαδικός ορθομοναδιαίος πίνακας, Σ ένας m×n ορθογώνιος διαγώνιος πίνακας με μη αρνητικές τιμές στην διαγώνιο και V* (ο συζυγής ανάστροφος του V, ή απλά ο ανάστροφος του V αν ο V είναι πραγματικός) ένας n×n πραγματικός ή μιγαδικός ορθομοναδιαίος πίνακας. Τα διαγώνια στοιχεία Σi,i του Σ είναι γνωστά ως ιδιάζουσες τιμές του M. Οι m στήλες του U και οι n στήλες του V ονομάζονται αριστερά-ιδιάζοντα διανύσματα και δεξιά-ιδιάζοντα διανύσματα του Μ, αντίστοιχα.

Η ανάλυση σε ιδιάζουσες τιμές και η ανάλυση σε ιδιοτιμές είναι στενά συνδεδεμένες. Δηλαδή:

  • Τα αριστερά-ιδιάζοντα διανύσματα του M είναι τα ιδιοδιανύσματα του MM*.
  • Τα δεξιά-ιδιάζοντα διανύσματα του M είναι τα ιδιοδιανύσματα του M*M.
  • Οι μη-μηδενικές ιδιάζουσες τιμές του M (που εμφανίζονται στις διαγώνιες θέσεις του Σ) είναι οι τετραγωνικές ρίζες των μη μηδενικών ιδιοτιμών του M*M και του MM*.

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

Διατύπωση του θεωρήματος[Επεξεργασία | επεξεργασία κώδικα]

Υποθέτουμε ότι ο M είναι ενας m×n πίνακας του οποίου τα στοιχεία ανηκουν στο σώμα K, που είναι είτε το σώμα των πραγματικών αριθμών είτε το σώμα των μιγαδικών αριθμών. Τότε υπάρχει μια παραγοντοποίηση της μορφής

όπου ο U είναι ένας m×m ορθομοναδιαίος πινακας (ορθογώνιος πίνακας αν το K είναι το σώμα των πραγματικών) με στοιχεία από το K, ο Σ είναι ένας m×n διαγώνιος πίνακας με μη αρνητικούς πραγματικούς αριθμούς στην διαγώνιο, και ο n×n ορθομοναδιαίος πίνακας V* είναι ο συζηγής ανάστροφος του n×n ορθομοναδιαίου πίνακα V. Μια τέτοια παραγοντοποίηση ονομάζεται ανάλυση του M σε ιδιάζουσες τιμές.

Τα διαγώνια στοιχεία του Σ είναι γνωστά ως οι ιδιάζουσες τιμές του M. Μια συνήθης σύμβαση είναι να κατατάσσουμε τις ιδιάζουσες τιμές σε φθίνουσα σειρά. Σ'αυτήν την περίπτωση, ο διαγώνιος πίνακας Σ καθορίζεται με μοναδικό τροπο απο τον M (όχι όμως και οι πίνακες U και V).

Διαισθητικές ερμηνείες[Επεξεργασία | επεξεργασία κώδικα]

Περιστροφή, αλλαγή κλίμακας[Επεξεργασία | επεξεργασία κώδικα]

Στην ειδική αλλά συνηθισμένη περίπτωση που ο M είναι απλά ένας m×m τετραγωνικός πίνακας με θετική ορίζουσα του οποίου τα στοιχεία είναι πραγματικοί αριθμοί, τότε οι U, V*, και Σ είναι m×m πίνακες πραγματικών αριθμών, επίσης ο Σ μπορεί να θεωρηθεί ως ένας πίνακας αλλαγής κλίμακας, και οι U και V* ως πίνακες περιστροφής.

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

Οι ιδιάζουσες τιμές ως ημιάξονες μιας έλλειψης ή ενός ελλειψοειδούς[Επεξεργασία | επεξεργασία κώδικα]

Όπως φαίνεται στην εικόνα, οι ιδιάζουσες τιμές μπορούν να ερμηνευθούν ως οι ημιάξονες μιας έλλειψης στο επίπεδο. Αυτή η ιδέα μπορεί να γενικοποιηθεί στον n-διάστατο Ευκλείδειο χώρο, με τις ιδιάζουσες τιμές κάθε n×n τετραγωνικού πίνακα να θεωρούνται ως οι ημιάξονες ενός n-διάστατου ελλειψοειδούς. Δείτε παρακάτω για περισσότερες λεπτομέρειες.

Οι στήλες των U και V είναι ορθοκανονικές βάσεις[Επεξεργασία | επεξεργασία κώδικα]

Καθώς οι πίνακες U και V* είναι ορθομοναδιαίοι, οι στήλες του καθενός σχηματιζουν ένα σύνολο ορθοκανονικών διανυσμάτων, που μπορούν να θεωρηθούν ως διανύσματα βάσης. Από τον ορισμό του ορθομοναδιαίου πίνακα, προκύπτει οτι το ίδιο ισχύει και για τους συζηγείς αναστρόφους αυτων, U* και V. Εν συντομία, οι στήλες των U, U*, V, και V* είναι ορθοκανονικές βάσεις.

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Θεωρούμε τον 4×5 πίνακα

Μία ανάλυση αυτού του πίνακα σε ιδιάζουσες τιμές δίνεται από τους πίνακες

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

και

Η παραπάνω ανάλυση σε ιδιάζουσες τιμές δεν είναι μοναδική. Επιλέγοντας τον έτσι ώστε

έχουμε άλλη μία ανάλυση σε ιδιάζουσες τιμές.

Ιδιάζουσες τιμές, ιδιάζοντα διανύσματα και η σχέση τους με την ανάλυση σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Ένας μη αρνητικός πραγματικός αριθμός σ είναι μια ιδιάζουσα τιμή για τον M αν και μόνο αν υπάρχουν μοναδιαία διανύσματα u του Km και v του Kn τέτοια ώστε

Τα διανύσματα u και v ονομάζονται αριστερά-ιδιάζοντα και δεξιά-ιδιάζοντα διανύσματα του σ, αντίστοιχα.

Σε κάθε ανάλυση πίνακα σε ιδιάζουσες τιμές

τα διαγώνια στοιχεία του Σ είναι ίσα με τις ιδιάζουσες τιμές του M. Οι στήλες των U και V είναι, αντίστοιχα, τα αριστερά και δεξιά ιδιάζοντα διανύσματα των αντίστοιχων ιδιάζουσων τιμών. Επομένως, το παραπάνω θεώρημα συνεπάγεται οτι:

  • Ένας m × n πίνακας M έχει το πολύ p = min(m,n) διαφορετικές ιδιάζουσες τιμές.
  • Είναι πάντα δυνατόν να βρούμε μια ορθογώνια βάση U του Km αποτελούμενη απο αριστερά ιδιάζοντα διανύσματα του M.
  • Είναι πάντα δυνατόν να βρούμε μια ορθογώνια βάση V του Kn αποτελούμενη απο δεξιά ιδιάζοντα διανύσματα του M.

Μια ιδιάζουσα τιμή για την οποία μπορούμε να βρούμε δύο αριστερά (ή δεξιά) ιδιάζοντα διανύσματα που είναι γραμμικώς ανεξάρτητα μεταξύ τους ονομάζεται εκφυλισμένη.

Οι μη εκφυλισμένες ιδιάζουσες τιμές έχουν πάντα μοναδικά αριστερά και δεξιά ιδιάζοντα διανύσματα, κατά προσέγγιση ενός πολλαπλασιαστικού παράγοντα φάσης της μορφής eiφ (στην περίπτωση των πραγματικών κατα προσέγγιση προσήμου). Συνεπώς, αν όλες οι ιδιάζουσες τιμες του M είναι μη εκφυλισμένες και μη μηδενικές, τότε η ανάλυση του είναι μοναδική, κατά προσέγγιση πολλαπλασιασμού μιας στήλης του U κατά ενός μοναδιαίου παράγοντα φάσης και ταυτόχρονου πολλαπλασιασμού της αντίστοιχης στήλης του V με τον ίδιο μοναδιαίο παράγοντα φάσης.

Οι εκφυλισμένες ιδιάζουσες τιμές, από τον ορισμό τους, έχουν μη μοναδικά ιδιάζοντα διανύσματα. Επιπλέον, αν u1 και u2 είναι δύο αριστερά ιδιάζοντα διανύσματα που και τα δύο αντιστοιχούν στην ιδιάζουσα τιμή σ, τότε κάθε κανονικοποιημένος γραμμικός συνδυασμός των δύο αυτών διανυσμάτων είναι επίσης ένα αριστερό ιδιάζων διάνυσμα που αντιστοιχεί στην τιμή σ. Το ίδιο ισχύει και για τα δεξιά ιδιάζοντα διανύσματα. Κατά συνέπεια, αν ο M έχει εκφυλισμένες ιδιάζουσες τιμές, τότε η ανάλυση του σε ιδιάζουσες τιμές δεν είναι μοναδική.

Εφαρμογές της Ανάλυσης σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Ψευδοαντίστροφος[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές μπορεί να χρησιμοποιηθεί για τον υπολογισμό του ψευδοαντιστρόφου ενός πίνακα. Πράγματι, ο ψευδοαντίστροφος ενός πίνακα M με ανάλυση σε ιδιάζουσες τιμές είναι ο

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

Επίλυση ομογενών γραμμικών εξισώσεων[Επεξεργασία | επεξεργασία κώδικα]

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

Ελαχιστοποίηση μέσω της μεθόδου ελαχίστων τετραγώνων[Επεξεργασία | επεξεργασία κώδικα]

Το πρόβλημα ελαχιστοποίησης μέσω της μεθόδου ελαχίστων τετραγώνων αναφέρεται στον υπολογισμό του διανύσματος που ελαχιστοποιεί την 2-νόρμα ενός διανύσματος κάτω απο την προυπόθεση . Η λύση τελικά είναι το δεξί ιδιάζων διάνυσμα του που αντιστοιχεί στη μικρότερη ιδιάζουσα τιμή.

Χώρος στηλών, μηδενοχώρος και βαθμίδα[Επεξεργασία | επεξεργασία κώδικα]

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

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

Προσέγγιση μέσω πινάκων χαμηλής τάξης[Επεξεργασία | επεξεργασία κώδικα]

Σε μερικές πρακτικές εφαρμογές υπάρχει η ανάγκη της προσέγγισης ενός πίνακα με έναν αλλον , περιορισμένο, ο οποίος έχει μία συγκεκριμένη βαθμίδα . Στην περίπτωση που η προσσέγιση βασίζεται στην ελαχιστοποίηση της νόρμας του Φρομπένιους της διαφοράς υπό τον περιορισμό , η λύση δίνεται απο την ανάλυση σε ιδιάζουσες τιμές του ,

όπου ο διαφέρει από τον στο ότι περιέχει μόνο τις μεγαλύτερες ιδιάζουσες τιμές (οι υπόλοιπες αντικαθιστώνται με μηδέν). Αυτό είναι γνωστό ως το θεώρημα των Eckart–Young, μιας και αποδείχθηκε από αυτούς το 1936 (παρόλο που αργότερα ανακαλυφθηκε ότι ήταν ήδη γνωστό από προγενέστερους, βλέπε Stewart 1993).

Διαχωρίσιμα μοντέλα[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές μπορεί να θεωρηθεί ως ανάλυση ενός πίνακα σε σταθμισμένο διατεταγμένο άθροισμα διαχωρίσιμων πινάκων. Ένας πίνακας λεγεται διαχωρίσιμος αν μπορεί να γραφτεί ως εξωτερικό γινόμενο δύο διανυσμάτων , ή, . Ειδικότερα, ο πίνακας M μπορεί να αναλυθεί ως εξής:

Όπου και είναι οι i-στές στήλες των αντίστοιχων πινάκων της ανάλυσης σε ιδιάζουσες τιμές, είναι οι διατεταγμένες ιδιάζουσες τιμές, και κάθε είναι διαχωρίσιμος. Η ανάλυση σε ιδιάζουσες τιμές μπορεί να χρησιμοποιηθεί στην ανάλυση ενός φίλτρου επεξεργασίας εικόνας σε οριζόντια και κάθετα φίλτρα. Παρατηρήστε ότι το πλήθος των μη μηδενικών είναι ακριβώς η βαθμίδα του πίνακα.

Εγγύτατος ορθογώνιος πίνακας[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές του μπορεί να χρησιμοποιηθεί για τον προσδιορισμό του εγγύτατου ορθογώνιου πίνακα του . Η απόσταση υπολογίζεται μέσω της Φρομπένιους νόρμας του . Η λύση είναι το γινόμενο .[1] Αποτέλεσμα το όποιο είναι διαισθητικά αναμενόμενο αφού ένας ορθογώνιος πίνακας θα έπρεπε να είχε μία ανάλυση όπου είναι ο μοναδιαίος πίνακας, έτσι ωστε αν τότε το γινόμενο ισοδυναμεί με την αντικατάσταση των ιδιαζόντων τιμών με μονάδες.

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

όπου συμβολίζει την νόρμα του Φρομπένιους.

Το πρόβλημα αυτό είναι ισοδύναμο με την εύρεση του εγγύτατου ορθογώνιου πίνακα του .

Αλγόριθμος του Kabsch[Επεξεργασία | επεξεργασία κώδικα]

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

Επεξεργασία σημάτων[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές και ο ψευδοαντίστροφος έχουν εφαρμοστεί επιτυχημένα στην επεξεργασία σήματος και στα μεγάλα δεδομένα (big data), για παράδειγμα στην επεξεργασία γονιδιωματικού σήματος.[2][3][4][5]

Άλλα παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές εφαρμόζεται ευρέως και στην μελέτη των γραμμικών αντιστρόφων προβλημάτων και είναι χρήσιμη στην ανάλυση μεθόδων κανονικοποίησης όπως αυτή του Tikhonov. Χρησιμοποιείται ευρύτατα στην Στατιστική όπου σχετίζεται με την ανάλυση κυρίων συνιστωσών και την Ανάλυση Αντιστοιχιών. Στη επεξεργασία σημάτων χρησιμοποιείται στον τομέα της αναγνώρισης προτύπων. Μία ακόμη χρήση είναι η Λανθάνουσα σημασιολογική δεικτοδότηση στην επεξεργασία κειμένων φυσικών γλωσσών.

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

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

Η ανάλυση σε ιδιάζουσες τιμές έχει επίσης εφαρμοστεί στην μοντελοποίηση ελλατωμένης τάξης. Σκοπός της μοντελοποίησης ελλατωμένης τάξης είναι η ελλάτωση των βαθμών ελευθερίας περίπλοκων συστημάτων τα οποία πρόκειται να μοντελοποιηθούν. Η ανάλυση σε ιδιάζουσες τιμές χρησιμοποιήθηκε σε συνδυασμό με συναρτήσεις ακτινικής βάσης για τον υπολογισμό μέσω παρεμβολής των λύσεων τριδιάστατων ασταθών προβλημάτων ροής.[6]

Η ανάλυση σε ιδιάζουσες τιμές έχει επίσης εφαρμοστεί στην θεωρία αντίστροφων προβλημάτων. Μία σημαντική εφαρμογή είναι η κατασκευή υπολογιστικών μοντέλων για δεξαμενές πετρελαίου.[7]

Η ανάλυση σε ιδιάζουσες τιμές χρησιμοποιείται σε συστηµάτα προτάσεων για την πρόβλεψη της βαθμολόγισης των προιόντων από τους καταναλωτές.[8]

Σχέση με την παραγοντοποίηση με χρήση ιδιοτιμών[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές είναι μια γενικότερη μέθοδος με την έννοια οτι μπορεί να χρησιμοποιηθεί σε κάθε πίνακα m × n ενώ αντιθέτως η ανάλυση σε ιδιοτιμές μπορεί να εφαρμοστεί μόνο σε συγκεκριμένα είδη τετραγωνικών πινάκων. Παρόλαυτα, οι δύο αναλύσεις σχετίζονται μεταξύ τους.

Δοσμένης μιας ανάλυσης σε ιδιάζουσες τιμές του M, όπως περιγράφηκε πιο πάνω, ισχύουν οι παρακάτω δύο σχέσεις:

Τα δεξιά μέλη των σχέσεων περιγράφουν την ανάλυση σε ιδιοτιμές των αριστερών μελών. Ως συμπέρασμα έχουμε οτι:

  • Οι στήλες του V (δεξιά ιδιάζοντα διανύσματα) είναι ιδιοδιανύσματα του .
  • Οι στήλες του U (αριστερά ιδιάζοντα διανύσματα) είναι ιδιοδιανύσματα του .
  • Τα μη μηδενικά στοιχεία του Σ (μη μηδενικές ιδιάζουσες τιμές) είναι οι τετραγωνικές ρίζες των μη μηδενικών ιδιοτιμών του ή του .

Στην ειδική περίπτωση που ο M είναι κανονικός πίνακας, που από τον ορισμό του σημαίνει ότι ειναι και τετραγωνικός, το φασματικό θεώρημα μας λέει οτι μπορεί να διαγωνιοποιηθεί ορθομοναδιαία χρησιμοποιώντας μια βάση απο ιδιοδιανύσματα, έτσι ώστε να μπορεί να γραφτεί στη μορφή για κάποιο ορθομοναδιαίο πίνακα U και διαγώνιο πίνακα D. Όταν ο M είναι επίσης θετικά ημιορισμένος, η ανάλυση είναι επίσης ανάλυση σε ιδιάζουσες τιμές.

Ωστόσο, η ανάλυση σε ιδιοτιμές και η ανάλυση σε ιδιάζουσες τιμές διαφέρουν για όλους τους άλλους πίνακες M: η ανάλυση σε ιδιοτιμές ειναι όπου ο U δεν είναι απαραίτητα ορθομοναδιαίος και ο D δεν είναι απαραίτητα θετικά ημιορισμένος, ενώ η ανάλυση σε ιδιάζουσες τιμές είναι όπου ο Σ είναι διαγώνιος και θετικά ημιορισμένος, και οι U και V είναι ορθομοναδιαίοι πίνακες που δεν σχετίζονται απαραίτητα μεταξύ τους, πλυν της σχέσης τους μέσω του M.

Ύπαρξη[Επεξεργασία | επεξεργασία κώδικα]

Μια ιδιοτιμή λ ενός πίνακα M χαρακτηρίζεται από την αλγεβρική σχέση M u = λ u. Όταν ο M είναι ερμητιανός, η χρήση του λογισμού των μεταβολών είναι επίσης δυνατή. Ας είναι ο M ένας n × n συμμετρικός πίνακας με πραγματικά στοιχεία. Ορίζουμε την f:RnR ως f(x) = xT M x. Από το θεώρημα ακραίων τιμών, η συνεχής αυτή συνάρτηση λαμβάνει μέγιστη τιμή για κάποιο u όταν περιοριστεί στην κλειστή μοναδιαία σφαίρα {||x|| ≤ 1}. Από το θεώρημα πολλαπλασιαστών του Lagrange, το u απαραίτητα ικανοποιεί το εξής:

όπου το σύμβολο, , είναι ο τελεστής ανάδελτα.

Ένας σύντομος υπολογισμός μας δείχνει οτι το παραπάνω οδηγεί στο M u = λ u (η συμμετρία του M είναι απαραίτητη εδώ). Επομένως το λ είναι η μεγαλύτερη ιδιοτιμή του M. Ο ίδιος υπολογισμός εκτελεσμένος στο ορθογώνιο συμπλήρωμα του u δίνει την επόμενη μεγαλύτερη ιδιοτιμή και πάει λέγοντας. Η μιγαδική περίπτωση (ο Μ και πάλι ερμητιανός) είναι παρόμοια. Σε αυτήν την περίπτωση ορίζουμε f(x) = x* M x να είναι μια πραγματική συνάρτηση 2n πραγματικών μεταβλητών.

Οι ιδιάζουσες τιμές ειναι όμοιες με την έννοια ότι μπορούν να περιγραφούν αλγεβρικά ή μέσω του λογισμού μεταβολών . Αν και, σε αντίθεση με την περίπτωση των ιδιοτιμών, ο Μ δεν είναι απαραίτητο να ειναι ερμητιανός ή συμμετρικός.

Η παράγραφος αυτή δίνει αυτά τα δύο επιχειρήματα για την ύπαρξη της ανάλυσης σε ιδιάζουσες τιμές.

Βασισμένη στο φασματικό θεώρημα[Επεξεργασία | επεξεργασία κώδικα]

Ας είναι M ένας m × n πίνακας με μιγαδικά στοιχεία. Ο M*M είναι θετικά ημιορισμένος και ερμητιανός. Από το φασματικό θεώρημα, θα υπάρχει ένας ορθομοναδιαίος n × n πίνακας V τέτοιος ώστε

όπου ο D είναι διαγώνιος και θετικά ορισμένος. Χωρίζουμε τον V καταλλήλως ώστε να μπορούμε να γράψουμε

Τότε V1*M*MV1 = D και V2*M*MV2 = 0. Το τελευταίο σημαίνει οτι MV2 = 0.

Επίσης, αφού ο V είναι ορθομοναδιαίος, V1*V1 = I, V2*V2 = I και V1V1* + V2V2* = I.

Ορίζουμε τον

Τότε

Βλέπουμε οτι αυτό είναι σχεδόν το επιθυμητό αποτέλεσμα, πλυν του ότι οι U1 και V1 δεν είναι γενικά ορθομοναδιαίοι, αλλα απλώς ισομετρίες. Για να ολοκληρώσουμε το επιχείρημα έχουμε ότι θα πρέπει να "συμπληρώσουμε" αυτούς τους πίνακες για να τους μετατρέψουμε σε ορθομοναδιαίους. Για παράδειγμα, μπορούμε να επιλέξουμε έναν U2 τέτοιο ώστε ο

να είναι ορθομοναδιαίος.

Ορίζουμε τον

όπου οι έξτρα μηδενικές γραμμές προστίθενται ή αφαιρούνται έτσι ώστε το σύνολο των μηδενικών γραμμών να ισούται με το σύνολο των στηλών του U2. Τότε

που είναι και το επιθυμητό αποτέλεσμα:

Παρατηρήστε ότι το επιχείρημα αυτό θα μπορούσε να ξεκινήσει διαγωνιοποιώντας τον MM* αντί για τον M*M (αυτό δείχνει επακριβώς ότι οι MM* και M*M έχουν τις ίδιες μη μηδενικές ιδιοτιμές).

Βασισμένη στο λογισμό των μεταβολών[Επεξεργασία | επεξεργασία κώδικα]

Οι ιδιάζουσες τιμές μπορούν επίσης να χαρακτηριστούν ως τα μέγιστα του uTMv, όταν θεωρηθεί σαν συνάρτηση των u και v, πάνω απο συγκεκριμένους υποχώρους. Τα ιδιάζοντα διανύσματα είναι οι τιμές των u και v όπου παρουσιάζονται τα μέγιστα.

Ας είναι M ένας m × n πίνακας με πραγματικά στοιχεία και και τα σύνολα των 2-νορμ μοναδιαίων διανυσμάτων των Rm και Rn αντίστοιχα. Ορίζουμε τη συνάρτηση

για διανύσματα u και v. Θεωρούμε τη συνάρτηση σ περιορισμένη στο × . Μιας και τα και είναι συμπαγή σύνολα , η τοπολογία γινόμενο τους είναι επίσης συμπαγής. Επιπλέον, μιας και η σ είναι συνεχής, λαμβάνει τουλάχιστον μια μέγιστη τιμή για τουλάχιστον ένα ζεύγος διανυσμάτων u και v. Η μέγιστη αυτή τιμή γράφεται σ1 και τα αντίστοιχα διανύσματα u1 και v1. Μιας και το είναι η μέγιστη τιμή της θα πρέπει να είναι μη αρνητική. Αν ήταν αρνητική, αλλάζοντας το πρόσημο είτε του u1 είτε του v1 θα την έκανε θετική και επομένως μεγαλύτερη.

Υπόθεση: Τα u1, v1 είναι αριστερά και δεξιά ιδιάζοντα διανύσματα του M με αντίστοιχη ιδιάζουσα τιμή την σ1.

Απόδειξη: Όμοια με την περίπτωση των ιδιοτιμών, από την υπόθεση τα δύο διανύσματα ικανοποιούν την εξίσωση πολλαπλασιαστών του Lagrange:

Μετά απο μερικές πράξεις, παίρνουμε

και

Πολλαπλασιάζοντας την πρώτη εξίσωση από αριστερά με και τη δεύτερη εξίσωση και πάλι απο αριστερά με και παίρνοντας ||u|| = ||v|| = 1 έχουμε ότι

Σε συνδυασμό με το ζεύγος των εξισώσεων παραπάνω, παίρνουμε τα εξής

και

Αυτό αποδεικνύει την υπόθεση.

Περισσότερα ιδιάζοντα διανύσματα και ιδιάζουσες τιμές μπορούν να βρεθούν μεγιστοποιώντας το σ(u, v) με κανονικοποιημένα u, v τα οποία είναι ορθογώνια ως προς τα u1 και v1, αντίστοιχα.

Η μετάβαση από τους πραγματικούς στους μιγαδικούς είναι παρόμοια με την περίπτωση των ιδιοτιμών.

Γεωμετρική σημασία[Επεξεργασία | επεξεργασία κώδικα]

Επειδή οι U και V είναι ορθομοναδιαίοι, γνωρίζουμε ότι οι στήλες u1, …, um του U σχηματίζουν μία ορθοκανονική βάση του Km και οι στήλες v1, …, vn του V μία ορθοκανονική βάση για το Kn (θεωρόντας και τον γνωστό βαθμωτό πολλαπλασιασμό στους χώρους αυτούς).

Ο γραμμικός μετασχηματισμός T :KnKm που απεικονίζει το x στο Mx έχει ιδιαίτερα απλή περιγραφή σε σχέση με αυτές τις ορθοκανονικές βάσεις: έχουμε T(vi) = σi ui, για i = 1,...,min(m,n), όπου σi είναι το i-στο στοιχείο της διαγωνίου του Σ, και T(vi) = 0 για i > min(m,n).

Η γεωμετρική σημασία της ανάλυσης ενός πίνακα σε ιδιάζουσες τιμές συνοψίζεται ως εξής: για κάθε γραμμική απεικόνιση T :KnKm μπορούμε να βρούμε ορθοκανονικές βάσεις των Kn και Km έτσι ώστε η T να απεικονίζει το i-στο διάνυσμα βάσης του Kn σε ένα μη αρνητικό πολλαπλάσιο του i-στου διανύσματος βάσης του Km, και να απεικονίσει την υπόλοιπη βάση σε μηδενικά διανύσματα. Σε σχέση με αυτές τις βάσεις, η απεικόνιση T αντιπροσωπεύεται από έναν διαγώνιο πίνακα με μη αρνητικά, πραγματικά στοιχεία.

Μία καλύτερη εποπτική περιγραφή των ιδιάζουσων τιμών και της ανάλυσης πίνακα σε αυτές -τουλάχιστον για πραγματικούς διανυσματικούς χώρους- είναι η εξής: Θεωρούμε μια σφαίρα S με ακτίνα ένα στον Rn. Η γραμμική απεικόνιση T απεικονίζει την σφαίρα σε ένα ελλειψοειδές στον Rm. Οι μη μηδενικές ιδιάζουσες τιμές είναι τα μήκη των ημιαξόνων του ελλειψοειδούς. Ειδικά όταν n=m, και όλες οι ιδιάζουσες τιμές είναι μη μηδενικές, η ανάλυση της γραμμικής απεικόνισης T μπορεί εύκολα να αναλυθεί σαν αλληλουχία τριών συνεχόμενων κινήσεων: Θεωρούμε το ελλειψοειδές T(S) και τους άξονές του, τότε θεωρούμε τις κατευθύνσεις στον Rn που καθορίζονται από την T σε αυτούς τους άξονες. Αυτές οι κατευθύνσεις είναι μεταξύ τους ορθογώνιες. Αρχικά θεωρούμε την ισομετρία v* που απεικονίζει αυτές τις κατευθύνσεις στους άξονες συντεταγμένων του Rn . Εν συνεχεία, ο ενδομορφισμός d διαγωνιοποιημένος κατά μήκος των αξόνων συντεταγμένων, μεγεθυνμένος ή συρρικνωμένος προς κάθε κατεύθυνση, χρησιμοποιώντας τα μήκη των ημιαξόνων της T(S) ως συντελεστές μεγέθυνσης. Η σύνθεση d ο v* στέλνει την μοναδιαία σφαίρα σε ένα ελλειψοειδές ισομετρικό του T(S). Για να ορίσουμε την τρίτη και τελευταία κίνηση u, θεωρούμε την ισομετρία που μεταφέρει το ελλειψοειδές στο T(S). Όπως μπορεί εύκολα να ελεγθεί, η σύνθεση u ο d ο v* ταυτίζεται με το T.

Υπολογίζοντας την ανάλυση σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Αριθμητική προσέγγιση[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση σε ιδιάζουσες τιμές ενός πίνακα M υπολογίζεται μεσω μία διαδικασιας που αποτελείται απο δύο βήματα. Στο πρώτο βήμα, ο πίνακας υποβιβάζεται σε έναν διδιαγώνιο πίνακα, δηλαδή σε έναν πίνακα του οποιου τα μόνα μη μηδενικά στοιχεία είναι αυτά της κύριας διαγώνιου καθώς και αυτά της υποδιαγωνίου ή της υπερδιαγωνίου. Το βήμα αυτό απαιτεί O(mn2) πράξεις κινητής υποδιαστολής (floating-point operations (flops)), αν υποθέσουμε ότι mn. Στο δεύτερο βήμα υπολογίζουμε την ανάλυση σε ιδιάζουσες τιμές του διδιαγώνιου πίνακα. Αυτό το βήμα μπορεί να γίνει μόνο με επαναληπτικές μεθόδους (όπως οι αλγόριθμοι για τις ιδιοτιμές ). Ωστόσο, στην πράξη αρκεί να υπολογίσουμε την ανάλυση σε ιδιάζουσες τιμές μέχρι μια συγκεκριμενη ακρίβεια, για παράδειγμα την machine epsilon. Αν αυτή η ακρίβεια θεωρηθεί σταθερή τότε το δεύτερο βήμα απαιτεί O(n) βήματα, καθένα από τα οποία κοστίζει O(n) flops. Συνεπώς, το πρώτο βήμα είναι υπολογιστικά πιο ακριβό και έτσι το συνολικό κόστος είναι O(mn2) flops (Trefethen & Bau III 1997, Lecture 31).

Το πρώτο βήμα μπορεί να υλοποιηθεί μέσω των αντικατοπτρισμών του Householder με κόστος 4mn2 − 4n3/3 flops, αν υποθέσουμε ότι μας ενδιαφέρουν μόνο οι ιδιάζουσες τιμές και όχι τα ιδιάζοντα διανύσματα. Αν το m είναι πολυ μεγαλύτερο από το n τότε συμφέρει περισσότερο να υποβιβάσουμε πρώτα τον πίνακα σε τριγωνικό μεσω της QR παραγοντοποίησης και μετά με χρήση των αντικατοπτρισμών Householder να υποβιβάσουμε περαιτέρω τον πίνακα σε διδιαγώνια μορφή. Το συνολικό κόστος τότε είναι 2mn2 + 2n3 flops (Trefethen & Bau III 1997, Lecture 31).

Το δεύτερο βήμα μπορεί να γίνει με μία παραλλαγή του QR αλγορίθμου για τον υπολογισμό των ιδιοτιμών, ο οποίος περιγράφηκε πρώτη φορά από τους Golub & Kahan (1965). Η υπορουτίνα DBDSQR[9] της βιβλιοθήκης LAPACK υλοποιεί αυτήν την επαναληπτική μέθοδο, με μερικές προσθήκες ώστε να καλυφθεί και η περίπτωση που οι ιδιάζουσες τιμές είναι πολύ μικρές (Demmel & Kahan 1990). Η ρουτίνα DGESVD[10] η οποία υπολογίζει την ανάλυση σε ιδιάζουσες τιμές αποτελείται από ένα αρχικό βήμα χρήσης αντικατοπτρισμών Householder, αν είναι απαραίτητο, και μία QR παραγοντοποίηση.

Ο ίδιος αλγόριθμος έχει υλοποιηθεί και στην GNU Scientific Library (GSL). Η GSL προσφέρει επίσης μία εναλλακτική μέθοδο, η οποία χρησιμοποιεί μονόπλευρους Jacobi orthogonalization στο βήμα 2 (GSL Team 2007). Αυτή η μέθοδος υπολογίζει την ανάλυση σε ιδιάζουσες τιμές του διδιαγωνίου πίνακα υπολογίζοντας μία σειρά από αναλύσεις σε ιδιάζουσες τιμές 2x2 πινάκων όμοια με τον τρόπο που ο αλγόριθμος ιδιοτιμών του Jacobi χρησιμοποιεί μεθόδους για τον υπολογισμό ιδιοτιμών 2x2 πινάκων(Golub & Van Loan 1996, §8.6.3). Επίσης μία άλλη μέθοδος για το βήμα 2 χρησιμοποιεί την ιδέα των αλγορίθμων διαίρει και βασίλευε για ιδιοτιμές (Trefethen & Bau III 1997, Lecture 31).

Αναλυτικοί τύποι για 2x2 πίνακες[Επεξεργασία | επεξεργασία κώδικα]

Οι ιδιάζουσες τιμές ενός 2x2 πίνακα μπορούν να βρεθούν αναλυτικά. Έστω όπου οι μιγαδικοί αριθμοί που παραμετροποιούν τον πίνακα, ο μοναδιαίος πίνακας, και οι Pauli πίνακες . Τότε οι δύο ιδιάζουσες τιμές δίνονται από τον τύπο

Ελλατωμένες αναλύσεις σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Στις εφαρμογές δεν συνηθίζεται να είναι απαραίτητη όλη η ανάλυση, συμπεριλαμβανομένης και μιας πλήρους unitary ανάλυσης του μηδενοχώρου του πίνακα. Αντ'αυτού, τις περισσότερες φορές επαρκεί (και είναι και ταχύτερο και πιο οικονομικό στην αποθήκευση) να υπολογίσουμε μια ελλατωμένη μορφή της ανάλυσης. Τα παρακάτω ισχύουν για έναν m×n πίνακα M βαθμίδας r:

"Λεπτή" ανάλυση σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Μόνο τα διανύσματα της n στήλης του U που αντιστοιχούν στα διανύσματα γραμμων του V* υπολογίζονται. Τα εναπομείναντα διανύσματα στηλών του U δεν λαμβανονται υπόψιν. Αυτή η διαδικασία ειναι εμφανώς γρηγορότερη και πιο οικονομική από μια πλήρη ανάλυση αν το nm. Ο Un είναι τοτε ένας m×n πίνακας, ο Σn ένας n×n διαγώνιος, και ο V ένας n×n.

Το πρώτο βήμα στο υπολογισμό της "λεπτής" ανάλυσης σε ιδιάζουσες τιμές είναι συνήθως μια QR ανάλυση του M, που είναι αρκετά ταχύτερη στον υπολογισμό όταν nm.

"Συμπαγής" ανάλυση σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Μόνο τα διανύσματα της r στήλης του U και της r γραμμής του V* που αντιστοιχούν στις μη μηδενικές τιμές Σr υπολογίζονται. Τα υπόλοιπα διανύσματα των U και V* δεν υπολογίζονται. Αυτό είναι ακόμα ταχύτερο και πιο οικονομικό απο την προηγούμενη μέθοδο αν ισχύει rn. Ο πίνακας Ur είναι τότε m×r, ο Σr r×r διαγώνιος, και ο Vr* ένας r×n.

"Αποκομένη" ανάλυση σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Μόνο τα διανύσματα της t στήλης του U και της t γραμμής του V* που αντιστοιχούν στην t μεγαλύτερη ιδιάζουσα τιμή Σt υπολογίζονται. Ο υπόλοιπος πίνακας δε λαμβάνεται υπόψιν. Η μέθοδος αυτή γίνεται ταχύτερη και οικονομικότερη απο την προηγούμενη όταν tr. Ο Ut είναι τότε ένας m×t πίνακας, ο Σt ένας t×t διαγώνιος, και ο Vt* ένας t×n.

Φυσικά η truncated SVD δεν είναι πλέον μια ακριβής ανάλυση του αρχικού πίνακα M, αλλά όπως αναφέρθηκε παραπάνω, ο κατά προσέγγιση πίνακας είναι όπως καταλαβαίνουμε η κοντινότερη προσέγγιση του M που μπορούμε να πετύχουμε από ένα πίνακα βαθμίδας t.

Νόρμες[Επεξεργασία | επεξεργασία κώδικα]

Ky Fan νόρμες[Επεξεργασία | επεξεργασία κώδικα]

Το άθροισμα των k μεγαλύτερων ιδιάζουσων τιμών του M είναι μία νόρμα πίνακα, η Ky Fan k-νόρμα του M.

Η πρώτη από τις Ky Fan νόρμες, η Ky Fan 1-νόρμα ταυτίζεται με την νόρμα του τελεστή του M αν αυτός θεωρηθεί γραμμικός τελεστής μεταξύ των ευκλείδιων χώρων Km και Kn. Με άλλα λόγια, η Ky Fan 1-νόρμα είναι η νόρμα τελεστή που επάγεται από το σύνηθες l2 Ευκλείδιο εσωτερικό γινόμενο. Για αυτό τον λόγο ονομάζεται και 2-νόρμα τελεστή. Εύκολα μπορεί να επαληθευτεί η σχέση μεταξύ της Ky Fan 1-νόρμας και των ιδιάζουσων τιμών. Στη γενική περίπτωση για κάθε φραγμένο τελεστη M μεταξύ χώρων Hilbert (πεπερασμένης ή άπειρης διάστασης) ισχύει ότι :

Ωστόσο, στην περίπτωση των πινάκων για τον M*M½ ισχύει ότι M*M½ = M½M* , οπότε η ||M* M||½ είναι η μεγαλύτερη ιδιοτιμή του M* M½, δηλαδή η μεγαλύτερη ιδιάζουσα τιμή του M.

Η τελευταία από τις Ky Fan νόρμες, το άθροισμα όλων των ιδιάζουσων τιμών, είναι η νόρμα του ίχνους : ||M|| = Tr[(M*M)½] (οι ιδιοτιμές του M* M είναι τα τετράγωνα των ιδιάζουσων τιμών.)

Νόρμα των Hilbert–Schmidt[Επεξεργασία | επεξεργασία κώδικα]

Οι ιδιάζουσες τιμές σχετίζονται και με μία άλλη νόρμα από τον χώρο των τελεστών. Θεωρείστε το Hilbert–Schmidt εσωτερικό γινόμενο επί των n × n πινάκων το οποίο ορίζεται μέσω της σχέσης . Η επαγόμενη νόρμα θα είναι η . Επειδή το ίχνος μένει αναλλοίωτο κάτω από unitary ισοδυναμία, έχουμε ότι

όπου είναι οι ιδιάζουσες τιμές του . Αυτή ονομάζεται νόρμα του Φρομπένιους,Schatten 2-νόρμα, ή Hilbert–Schmidt νόρμα του M. Έυκολα προκύπτει ότι αν

η Φρομπένιους νόρμα του M συμπίπτει με

Ανάλυση τανυστή σε ιδιάζουσες τιμές[Επεξεργασία | επεξεργασία κώδικα]

Το πρόβλημα εύρεσης μιας προσέγγισης ενός τανυστή μέσω πίνακα χαμηλής ταξης δεν είναι ορθά ορισμένο. Με άλλα λόγια, δεν υπάρχει η "καλύτερη" λύση, παραμόνο μια σειρά απο καλύτερες κάθε φορά προσεγγίσεις που συγκλίνουν σε άπειρα μεγάλους πίνακες. Παρ'όλ αυτά, υπάρχουν αρκετοί τρόποι να δοκιμάσουμε να κάνουμε την ανάλυση.

Υπάρχουν δύο ειδών αναλύσεις τανυστών οι οποίες γενικεύουν την ανάλυση σε ιδιάζουσες τιμές στην περίπτωση των πολυδιάστατων διατάξεων . Ο ένας από αυτούς αναλύει ένα τανυστή σε άθροισμα τανυστών πρώτης-τάξης, βλέπε αλγόριθμο Candecomp-PARAFAC (CP). Ο CP αλγόριθμος δεν πρέπει να συγχέεται με την rank-R ανάλυση. Αυτό που κάνει ο CP αλγόριθμος είναι για ένα δωθέν N να αναλύει ένα τανυστή σε ένα άθροισμα από N τανυστές πρώτης-τάξης που ταιριάζουν βέλτιστα με τον αρχικό τανυστή. Ο δεύτερος τρόπος ανάλυσης υπολογίζει τους ορθοκανονικούς χώρους που σχετίζονται με τους διάφορους άξονες ή άλλα χαρηκτηριστικά ενός τανυστή (ορθοκανονικός χώρος γραμμών, χώρος στηλών κτλ.). Η ανάλυση αυτή αναφέρεται στη βιβλιογραφία ως Tucker3/TuckerM, M-mode ανάλυση, πολυγραμμική ανάλυση και κάποιες φορές ως higher-order SVD (HOSVD).

Φραγμένοι τελεστές σε χώρους Hilbert[Επεξεργασία | επεξεργασία κώδικα]

Η παραγοντοποίηση μπορεί να επεκταθεί σε ένα φραγμένο τελεστή ενός διαχωρίσιμου χώρου Hilbert H. Πιο συγκεκριμένα για κάθε φραγμένο τελεστή M, υπάρχει μία μερική ισομετρία U, ένας ορθομοναδιαίος V, ένας μετρικός χώρος (Xμ), και μία μη αρνητική μετρίσημη συνάρτηση f τέτοια ώστε

όπου είναι ο πολλαπλασιαστικός τελεστής της f στον L2(X, μ).

Αυτό μπορεί να αποδειχθεί αν μιμηθούμε το επιχείρημα της γραμμικής άλγεβρας που χρησιμοποιήθηκε παραπάνω για την περίπτωση των πινάκων. VTf V* είναι η μοναδική θετική τετραγωνική ρίζα του M*M, όπως δίνεται από τον συναρτησιακό λογισμό του Borel για αυτοσυζυγείς τελεστές. Ο U δεν χρειάζεται να είναι ορθομοναδιαίος επειδή, σε αντίθεση με την πεπερασμένη περίπτωση, δοθείσης μίας ισομετρίας U1 με μη τετριμμένο πυρήνα, δεν υπάρχει πάντα κατάλληλος τελεστής U2 τέτοιος ώστε ο

να είναι unitary τελεστής.

Όσο για τους πίνακες, η παραγοντοποίηση σε ιδιάζουσες τιμές είναι ισοδύναμη με την πολική ανάλυση για τελεστές: μπορούμε απλά να γράψουμε

και να παρατηρήσουμε ότι ο U V* είναι μερική ισομετρία και η VTf V* θετική.

Ιδιάζουσες τιμές και συμπαγείς τελεστές[Επεξεργασία | επεξεργασία κώδικα]

Για να επεκτείνουμε την έννοια της ιδιάζουσας τιμής και του αριστερού/δεξιού ιδιάζοντος διανύσματος στην περίπτωση των τελεστών, πρέπει να περιοριστούμε στους συμπαγείς τελεστές. Είναι γεγονός πως οι συμπαγείς τελεστές σε χώρους Banach έχουν διακριτό φάσμα. Αυτό ισχύει και για συμπαγείς τελεστές σε χώρους Hilbert, αφού αυτοί οι χώροι είναι ειδική περίπτωση των χώρων Banach. Αν ο Τ είναι συμπαγής, κάθε μη μηδενικό λ στο φάσμα είναι ιδιοτιμή. Ακόμη, ένας συμπαγής αυτοσυζηγής τελεστής μπορεί να διαγωνιοποιηθεί από τα ιδιοδιανύσματά του. Αν ο Μ είναι συμπαγής, το ίδιο είναι και ο Μ*Μ. Εφαρμόζοντας το αποτέλεσμα της διαγωνιοποίησης, η unitary εικόνα της θετικής τετραγωνικής ρίζας του Tf έχει ένα σύνολο ορθοκανονικών ιδιοδιανυσμάτων {ei} που αντιστοιχούν σε αυστηρά θετικές ιδιοτιμές {σi}. Για κάθε ψ ∈ H,

όπου οι σειρές συγκλίνουν με στην νόρμα του H. Παρατηρήστε πως η παραπάνω έκφραση ισχύει και στην περίπτωση της πεπερασμένης διάστασης. Τα σi καλούνται ιδιάζουσες τιμές του M. Τα {U ei} και {V ei} μπορούν να θεωρηθούν αριστερά και δεξιά ιδιάζοντα διανύσματα του M αντίστοιχα.

Οι συμπαγείς τελεστές σε χώρους Hilbert είναι η κλειστή θήκη των πεπερασμένης βαθμίδας στην ομοιόμορφη τοπολογία τελεστών. Η παραπάνω έκφραση (άθροισμα) είναι μία εξήγηση αυτού του ισχυρισμού. Μία άμεση συνέπεια αυτού είναι:

Θεώρημα: Ο M είναι συμπαγής αν και μόνο αν ο M*M είναι συμπαγής.

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση ενός πίνακα σε ιδιάζουσες τιμές αρχικά αναπτύχθηκε από όσους ασχολήθηκαν με την διαφορική γεωμετρία, με σκοπό να ελλέγξουν αν η διγραμμική μορφή ενός πίνακα, μπορεί να ισούται με μία άλλη χρησιμοποιώνας ανεξάρτητους ορθογώνιους μετασχηματισμούς των δύο χώρων στους οποίυος δρα η διγραμμική μορφή. Ο Eugenio Beltrami και ο Camille Jordan ανακάλυψαν ξεχωριστά, το 1873 και 1874 αντίστοιχα, ότι οι ιδιάζουσες τιμές των διγραμμικών μορφών, γραμμένες σε μορφή πίνακα, συνιστούν ένα πλήρες σύνολο αναλλοίωτων για διγραμμικές μορφές κάτω απο ορθογώνιες αντικαταστάσεις. Ο James Joseph Sylvester επίσης κατασκεύασε την ανάλυση πίνακα σε ιδιάζουσες τιμές για πραγματικούς τετραγωνικούς το 1889, ανεξάρτητα και από τον Beltrami και από τον Τζόρνταν. Ο Sylvester ονόμασε τις ιδιάζουσες τιμές κανονικούς πολλαπλασιαστές (canonical multipliers) του πίνακα Α. Ο τέταρτος μαθηματικός που ανέλυσε έναν πίνακα σε ιδιάζουσες τιμές, ανεξάρτητα των προηγουμένων, ήταν ο Autonne το 1915, ο οποίος έφτασε εκεί μέσω της πολικής ανάλυσης. Η πρώτη απόδειξη της ανάλυσης ενός πίνακα σε ιδιάζουσες τιμές για ορθογώνιους και μιγαδικούς πίνακες, φέρεται να έγινε από τον Carl Eckart και τον Gale Young το 1936,[11] οι οποίοι την είδαν σαν γενίκευση του μετασχηματισμού του κύριου άξονα για ερμιτιανούς πίνακες.

Το 1907, ο Erhard Schmidt όρισε μία έννοια ανάλογη με αυτή των ιδιαζόντων τιμών για τους ολοκληρωτικούς τελεστές (που είναι συμπαγής, κάτω απο ορισμένες αδύναμες υποθέσεις. Δεν γνώριζε για την δουλειά που γινόταν παράλληλα πάνω στις ιδιάζουσες τιμές πεπερασμένων πινάκων. Η θεωρία αναπτύχθηκε περαιτέρω από τον Émile Picard το 1910, ο οποίος ήταν ο πρώτος που αποκάλεσε τα στοιχεία ιδιάζουσες τιμές (ή στα γαλλικά: valeurs singulières).

Πρακτικές μέθοδοι του υπολογισμού της ανάλυσης πίνακα σε ιδιάζουσες τιμές, χρονολογούνται από το 1954, 1955 με τον Kogbetliantz και το 1958 με τον Hestenes.[12] Που θυμίζουν αρκετά τον αλγόριθμο υπολογισμού ιδιοτιμών του Jacobi, που χρησιμοποιεί περιστροφές επιπέδων ή περιστροφές του Givens. Παρ' ότι αυτές αντικαταστάθηκαν από τη μέθοδο των Gene Golub και William Kahan που εκδόθηκε το 1965,[13] που χρησιμοποιεί μετασχηματισμούς του Householder ή αντανακλάσεις. Το 1970, ο Golub και ο Christian Reinsch[14] δημοσίευσαν μία παραλαγή του αλγορίθμου Golub/Kahan που είναι και η πιο πολυχρησιμοποιημένη μέχρι σήμερα.

Σχετικά πεδία[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. The Singular Value Decomposition in Symmetric (Lowdin) Orthogonalization and Data Compression
  2. O. Alter, P. O. Brown and D. Botstein (September 2000). «Singular Value Decomposition for Genome-Wide Expression Data Processing and Modeling». PNAS 97 (18): 10101–10106. doi:10.1073/pnas.97.18.10101. http://dx.doi.org/10.1073/pnas.97.18.10101. 
  3. O. Alter and G. H. Golub (November 2004). «Integrative Analysis of Genome-Scale Data by Using Pseudoinverse Projection Predicts Novel Correlation Between DNA Replication and RNA Transcription». PNAS 101 (47): 16577–16582. doi:10.1073/pnas.0406767101. http://dx.doi.org/10.1073/pnas.0406767101. 
  4. O. Alter and G. H. Golub (August 2006). «Singular Value Decomposition of Genome-Scale mRNA Lengths Distribution Reveals Asymmetry in RNA Gel Electrophoresis Band Broadening». PNAS 103 (32): 11828–11833. doi:10.1073/pnas.0604756103. http://dx.doi.org/10.1073/pnas.0604756103. 
  5. N. M. Bertagnolli, J. A. Drake, J. M. Tennessen and O. Alter (November 2013). «SVD Identifies Transcript Length Distribution Functions from DNA Microarray Data and Reveals Evolutionary Forces Globally Affecting GBM Metabolism». PLoS One 8 (11): e78913. doi:10.1371/journal.pone.0078913. Highlight. http://dx.doi.org/10.1371/journal.pone.0078913. 
  6. S. Walton, , O. Hassan , K. Morgan, Reduced order modelling for unsteady fluid flow using proper orthogonal decomposition and radial basis functions, Applied Mathematical Modelling, http://www.sciencedirect.com/science/article/pii/S0307904X13002771
  7. Gharib Shirangi, M., History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, Journal of Petroleum Science and Engineering, http://www.sciencedirect.com/science/article/pii/S0920410513003227
  8. Sarwar, Badrul; Karypis, George; Konstan, Joseph A.; Riedl, John T. (2000) (PDF). Application of Dimensionality Reduction in Recommender System -- A Case Study. University of Minnesota. http://files.grouplens.org/papers/webKDD00.pdf. Ανακτήθηκε στις May 26, 2014. 
  9. Netlib.org
  10. Netlib.org
  11. Eckart, C.; Young, G. (1936). «The approximation of one matrix by another of lower rank». Psychometrika 1 (3): 211–8. doi:10.1007/BF02288367. https://archive.org/details/sim_psychometrika_1936-09_1_3/page/211. 
  12. Hestenes, M. R. (1958). «Inversion of Matrices by Biorthogonalization and Related Results». Journal of the Society for Industrial and Applied Mathematics 6 (1): 51–90. doi:10.1137/0106005. MR 0092215. 
  13. Golub, G. H.; Kahan, W. (1965). «Calculating the singular values and pseudo-inverse of a matrix». Journal of the Society for Industrial and Applied Mathematics: Series B, Numerical Analysis 2 (2): 205–224. doi:10.1137/0702016. MR 0183105. 
  14. Golub, G. H.; Reinsch, C. (1970). «Singular value decomposition and least squares solutions». Numerische Mathematik 14 (5): 403–420. doi:10.1007/BF02163027. MR 1553974. https://archive.org/details/sim_numerische-mathematik_1970_14_5/page/403. 

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]