Optimum pairing of blindly separated signals

What is going on?

The indeterminacies of the original sources is essential feature of blind methods. In linear ICA model, the sources can be estimated up to the original order, signs, and scales. It can be assumed, to avoid the indeterminacy of the original scales, that the original signals have unit variance. Then, the signs and the order remain unknown, which is called a permutation problem. The original order of the signals needs to be retrieved in several cases, e. g., in order to compare each estimated signal with its original counterpart (if known), or reorder separated components in different frequency bins to achieve deconvolution of the signals. Then, usually a definition of some pairwise matching criterion is stated (correlation), and, based on this, the signals are reordered so that their mutual similarity is maximized.

The problem, whereto the reordering leads up, can be formulated in terms of graph theory as the one to find optimal matching in a complete bipartite graph. Our algorithm utilizes the optimal matching method called the Kuhn-Munkres algorithm, in contrast to the commonly used method known in graph theory as the greedy algorithm, which is suboptimal.

Corresponding paper: here,

Matlab code: here

Example of utilization:

>> Wold=[2 3 ;-1 6] 
Wold =

    2   3
   -1   6

>> Wnew=[1.3 -5.8; 2.4 2.9] 
Wnew =

    1.3000     -5.8000
    2.4000      2.9000

>> [W_reshufled Permutation]=nearest2(Wnew, Wold)
W_reshufled =

     2.4000     2.9000
    -1.3000     5.8000

Permutation =

    0     1
    1     0