Algorithmus, der 2 'ähnliche' Matrizen verwendet und 'zueinander' ausrichtet

Question

Zunächst ist der Titel sehr schlecht, weil ich kein präzises Vokabular habe. Ich werde versuchen, zu beschreiben, was ich mache, und dann meine Frage erneut stellen.

Background Info

Sagen wir, ich habe 2 Matrizen Größe n x m, wo n die Zahl der experimentellen Beobachtungsvektoren ist, die jeweils mit einer Länge von m (der Zeitreihe, über die die Beobachtungen gesammelt wurden). Eine dieser Matrizen ist die ursprüngliche Matrix mit der Bezeichnung S, die andere ist eine rekonstruierte Version von S, die Y genannt wird.

---

Lasst uns annehmen, dass YS richtig rekonstruiert. Aufgrund der Beschränkungen des Rekonstruktionsalgorithmus kann Y jedoch nicht die wahre Amplitude der Vektoren in S bestimmen, noch ist es garantiert, das richtige Vorzeichen für diese Vektoren bereitzustellen (die Vektoren könnten umgedreht werden). Auch die Reihenfolge der Beobachtungsvektoren in Y stimmt möglicherweise nicht mit der ursprünglichen Reihenfolge der entsprechenden Vektoren in S überein.

My Frage

Gibt es einen Algorithmus oder eine Technik, um eine neue Matrix zu erzeugen, die eine ‚Wiederausrichtung‘ der Y zu S, so dass, wenn Y und S normalisiert sind, kann der Algorithmus (1) Finde die Vektoren in Y, die die Vektoren in S und stellen Sie die ursprüngliche Reihenfolge der Vektoren und (2) entsprechen ebenfalls die Vorzeichen der Vektoren?

---

Wie immer, ich schätze wirklich alle Hilfe gegeben. Vielen Dank!

Answer 1

Wie wäre es, einfach die normalisierte Form für jeden Vektor in beiden Matrizen zu berechnen und zu vergleichen? Das sollte Ihnen eine genaue Eins-zu-eins-Übereinstimmung für jeden Vektor in jeder Matrix geben.

die normale Form eines Vektors ist eine, die auf entspricht:

v_norm = v/||v|| 

wo ||v|| die euklidische Norm für den Vektor ist. Für v=(v1, v2, ..., vn) haben wir ||v|| = sqrt(v1^2 + ... + vn^2).

Von dort können Sie ihre Reihenfolge rekonstruieren und jeden Vektor seine ursprüngliche Länge und Richtung (der Vektor oder sein Gegenteil) zurückgeben.

Der Algorithmus sollte von nun an ziemlich einfach sein, entscheiden Sie sich einfach für Ihre Implementierung. Diese Methode sollte von quadratischer Komplexität sein . Pro Kommentar können Sie tatsächlich O(nlogn) Komplexität auf diesem Algorithmus erreichen. Wenn Sie etwas Besseres brauchen, lineare Komplexität - im Besonderen benötigen Sie einen viel komplizierteren Algorithmus, an den ich momentan nicht denken kann.