Алгоритм, который принимает 2 'подобные' матрицы и 'выравнивает' друг другу

Question

Прежде всего, название очень плохое из-за моего недостатка в сжатой лексике. Я попытаюсь описать, что я делаю, а затем снова задаю свой вопрос.

Справочная информация

Скажем, у меня есть 2 матрицы размером n х m, где n является число экспериментальных векторов наблюдений, длина каждой из m (временных рядов, по которой были собраны наблюдения). Одной из этих матриц является исходная матрица, называемая S, другая - реконструированная версия S, называемая Y.

---

Давайте предположим, что Y правильно реконструирует S. Однако из-за ограничений алгоритма реконструкции Y не может определить истинную амплитуду векторов в S, и не гарантирует, что он обеспечит правильный знак для этих векторов (векторы могут быть перевернуты). Кроме того, порядок векторов наблюдений в Y может не соответствовать первоначальному порядку соответствующих векторов в S.

Мой вопрос

Есть ли алгоритм или метод для создания новой матрицы, которая является «Перестройка» в Y к S, так что, когда Y и S нормированы, алгоритм может (1) найти векторы в Y, которые соответствуют векторам в S и восстановить исходный порядок векторов, и (2) также соответствуют признакам векторов?

---

Как всегда, я действительно ценю всю предоставленную помощь. Благодаря!

Answer 1

Как насчет простого вычисления нормированной формы для каждого вектора в обеих матрицах и сравнения? Это должно дать вам точное взаимно однозначное соответствие для каждого вектора в каждой матрице.

Нормальная форма вектора является тот, который соответствует:

v_norm = v/||v|| 

, где ||v|| является евклидова норма для вектора. Для v=(v1, v2, ..., vn) у нас есть ||v|| = sqrt(v1^2 + ... + vn^2).

Оттуда вы можете восстановить порядок и вернуть каждому вектору его первоначальную длину и направление (вектор или его противоположность).

Алгоритм должен быть довольно простым отсюда, просто решите свою реализацию. Этот метод должен иметь квадратичную сложность . В комментарии вы можете достичь сложности O(nlogn) по этому алгоритму. Если вам нужно что-то лучше этого, линейная сложность - в частности, вам понадобится гораздо более сложный алгоритм, о котором я не могу сейчас думать.