Matlab: оптимальное дистанционное сопоставление элементов двух множеств - PullRequest
Новая
       4

Matlab: оптимальное дистанционное сопоставление элементов двух множеств

2 голосов
/ 05 августа 2011

У меня есть два числовых вектора с плавающей точкой, которые содержат одинаковые значения вплоть до небольшой ошибки, но не обязательно отсортированы одинаковым образом;например, A=rand(10);a=eig(A);b=eig(A+1e-10); (помните, что eig выводит собственные значения в не указанном порядке).

Мне нужно найти перестановку p, которая соответствует соответствующим элементам, то есть p=mysterious_function(a,b), такую ​​что norm(a-b(p))маленький.

Существует ли существующая функция, которая делает это разумным и безопасным способом, или мне действительно нужно развернуть мою собственную медленную и плохо проверенную на ошибки реализацию?

IЭто нужно только для целей тестирования, не нужно чрезмерно оптимизировать его.Обратите внимание, что решение, которое включает в себя сортировку обоих векторов с sort, терпит неудачу в случае векторов, содержащих сложные аргументы с равным модулем, такие как типичный вывод eig().

Ответы [ 2 ]

4 голосов
/ 05 августа 2011

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

0 голосов
/ 06 августа 2011

Я полагаю, что решение sort(), от которого вы отказались, может сработать; Критерий, который вы определили minimize norm(a-b), по определению учитывает модуль (абсолютное значение) комплексного числа: norm(a-b) == sqrt(sum(abs(a-b).^2))

И, как вы знаете, SORT упорядочивает комплексные числа на основе их абсолютного значения: sort(a) эквивалентно sort(abs(a)) для комплексного ввода. 

%# sort by complex-magnitude
[sort(a) sort(b)]

Пока один и тот же порядок применяется к обоим, вы также можете попробовать лексикографическое упорядочение (сортировка по вещественной части, если она равна, затем сортировка по мнимой части): 

%# lexicographic sort order
[~,ordA] = sortrows([real(a) imag(a)],[1 2]);
[~,ordB] = sortrows([real(b) imag(b)],[1 2]);
[b(ordB) a(ordA)]

Если вы слишком ленивы для реализации венгерского алгоритма , который @ AnthonyLabarre предложил, перейдите к грубому принуждению: 

A = rand(5);
a = eig(A);
b = eig(A+1e-10);

bb = perms(b);                                       %# all permutations of b
nrm = sqrt( sum(abs(bsxfun(@minus, a,bb')).^2) );    %'
[~,idx] = min(nrm);                                  %# argmin norm(a-bb(i,:))
[bb(idx,:)' a]

Помимо того, что собственные значения, возвращаемые EIG, не гарантируются для сортировки, есть еще одна сложность, с которой вам придется иметь дело, если вы также сопоставляете собственные векторы: они не уникальны в том смысле, что если v является собственным вектором тогда k*v тоже один, особенно для k=-1. Обычно вы применяете соглашение о знаках, например: умножьте на - / + 1, чтобы у самого большого элемента в каждом векторе был положительный знак.

...