I have a very large set of 400x400 binary matrices M. For a given binary matrix A, how do I find the matrix B within the set M such that it has the least hamming distance from A?
Asked
Active
Viewed 107 times
0
-
Compute all the hamming distances d(A, B), and take the B for which it's minimal? – One Lyner Jun 25 '20 at 20:02
-
oops, forgot to include infinitely large set of binary matrices! edited it – Pratik Kulkarni Jun 25 '20 at 20:08
-
What size are your matrices? There are only `2^(n.m)` binary matriecs of size n x m . – One Lyner Jun 25 '20 at 20:10
-
they are 400x400 – Pratik Kulkarni Jun 25 '20 at 20:11
-
Is there any structure, and how large is "very large"? If there is no structure, you have to at least read all the matrices in M. If it's really "very large" this will be very long... – One Lyner Jun 25 '20 at 20:24
1 Answers
1
This is probably a duplicate of this question:
Efficiently find binary strings with low Hamming distance in large set
The fact that your string represents a matrix does not change anything to the hamming distance.
For something fancier, you can also look at this recent paper:
https://www.cas.mcmaster.ca/ashtiani/papers/online-nearest-neighbor.pdf
One Lyner
- 1,964
- 1
- 6
- 8