search

fouticus / nsfbm

Non-Uniform Sampling of Fixed Binary Matrices
GNU General Public License v3.0
2 stars 0 forks source link

consistency of weight matrix W #6

Open michalkvasnicka opened 4 years ago

michalkvasnicka commented 4 years ago

The algorithms should at first check if the matrix W (in a case of structural zeros w_{ij} = 0) is able to produce any matrix A.

fouticus commented 4 years ago

I'm not aware of a way to check this condition in the presence of structural zeros (efficiently). This would be an interesting research direction

Also see comment on #5

michalkvasnicka commented 4 years ago

In a case of permutations matrices A (which mainly interest me), where fixed margins (columns and rows) of matrices A must be equals to 1, is a good test the "sinkhorn-knopp" algorithm. When balanced matrix Ws after Sinkhorn alg application on matrix W contains only zeros (or nearly zeros) over any columns or rows then the W matrix is inconsistent and it is not able to produce any permutations.

Is possible to apply again Hungarian algorithm, too. If that find any correct permutation A, then W is consistent.

Another way is define matrix C (C_ij = 0 when W_ij = 0 and C_ij = 1 when W_ij != 0) and then try to compute permanent perm(C) (if W is consistent, then perm(C) > 0) ... but this approach is very numerical intensive for large matrices due to the its NP-hard behaviour.