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

Question

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

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

Допустим, у меня есть 2 матрицы размером n x 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) в этом алгоритме. Если вам нужно что-то лучше, чем линейная сложность, в частности, вам понадобится гораздо более сложный алгоритм, о котором я сейчас не могу думать.