2011-08-05 5 views
2

小さな誤差まで同じ値を含み、必ずしも同じ方法でソートされるわけではない2つの浮動小数点数ベクトルがあります。たとえば、A=rand(10);a=eig(A);b=eig(A+1e-10);eigは固有値を指定された順序で出力しないことに注意してください)。Matlab:2組の要素の最適距離のマッチング

対応する要素、すなわちp=mysterious_function(a,b)と一致する順列pを見つける必要があります。norm(a-b(p))は小さいです。

これを安全かつ安全に実行する既存の機能がありますか、それとも、自分自身の遅いエラーチェックの実装を実際に展開する必要がありますか?

これはテスト目的でのみ必要ですが、あまりにも最適化する必要はありません。 で両方のベクトルをソートする解決策は、等価な複素数引数を含むベクトルの場合、典型的な出力がeig()の場合に失敗することに注意してください。

答えて

4

linear assignment problemを解決したいようです。私は自分でそれをテストしていませんが、this piece of codeがあなたを助けます。

+0

これを見ていただき、ありがとうございます(私はタグを "割り当て問題"にしたいと思いますが、評判が足りません)。私は現在、同様のコードを使用していますが、エラーが発生しやすい定型ラッパーを作成する必要がありました。私はあらかじめ缶詰めされたものを見つけることを望みました。これは私の目にはかなり共通の問題でした。 –

0

あなたが破棄したsort()ソリューションが実際にあなたのために役立つかもしれないと私は信じています。あなたが知っているように、その絶対値に基づいてSORT注文複素数をnorm(a-b) == sqrt(sum(abs(a-b).^2))

そして:あなたはminimize norm(a-b)を定義した基準は、複素数の係数(絶対値)を考慮し、定義によって、ある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)] 

あなたは、提案Hungarian algorithm@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も1であり、特にk=-1である。通常は、 -/+ 1で乗算して、各ベクトルの最大要素が正の符号を持つような記号規約を適用します。

+2

固有値が正確に計算された場合、ソートベースのソリューションが機能します。実際の固有値が1i、1、-1で、 'a'に' [0.99; -1.01; 1i] 'が含まれ、' b 'に[1.01; -0.99; 1i]があれば、ソートベースの解はすべて失敗に繋がる。実際には、共通の順序を導き出すために「a」と「b」で別々に動作するすべてのソリューションが失敗すると考えられます。 –

+0

@FedericoPoloni:いいカウンター・サンプル(辞書式の順序付けは機能しますが)...私は割り当て問題を解決する方法を検討しています:) – Amro

関連する問題