# Selecting five binary vectors that when multiplied elementwise are most similar to another vector

I have a sparse $$60000\times10000$$ matrix where each element is either a $$1$$ or $$0$$ as follows.

$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 & 1 & 0 & \cdots & 1 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & \cdots & 0 \end{bmatrix}$$

Each row represents a different point in time such that the first row is $$t=1$$ and the last row is $$t=60000$$. Each column in the matrix is a different combination of signals (ie. $$1$$s and $$0$$s). I want to choose five column vectors from $$M$$, $$c_1, c_2, c_3, c_4, c_5$$ and take the Hadamard (ie. element-wise) product:

$$s = c_1 \circ c_2 \circ c_3 \circ c_4 \circ c_5$$

The result is a new vector $$s$$ where $$1$$s only remain in a row if they were present in every vector $$c_1, c_2, c_3, c_4, c_5$$ for that row. I need an algorithm that finds the optimal strategy vector $$s_{opt}$$ that is most similar to the optimal strategy vector $$s^{*}$$. The optimal strategy vector $$s^{*}$$ is predefined and static, of the same dimensions as $$s$$, and has the optimal placement of 1s and 0s.

The easiest solution is to test every combination possible; however, choosing $$5$$ columns from $$10000$$ results in $$10^{20}$$ different possible combinations. Note that the five vectors chosen from $$M$$ to form a strategy $$s$$ must not be distinct. As such, I want to find an algorithm that returns the five vectors $$c_{1}$$ through $$c_{5}$$ that yield the optimal strategy $$s_{opt}$$.

I believe this is a discrete optimisation (integer programming) problem. Ideally, I would like to maximise the similarity of the two vectors, $$\operatorname{sim}(s_{opt},s^{*})$$. The Jaccard Index is used because I'd rather have a false negative (ie. a 0 in row $$i$$ of $$s_{opt}$$ when it is a 1 in $$s_i^{*}$$) than a false positive (ie. a 1 where it should have been 0). Furthermore, the metric is commonly used for 'binary vectors'.

$$\operatorname{sim}(s,s^{*})=\frac{s \cdot s^{*}}{\sum_{i=1}^{60000}\left (s_{i} + s_{i}^{*} \right ) - s \cdot s^{*}}$$

Note that the operation ($$\cdot$$) refers to the dot product and not the Hadamard product.

However, as the metric is non-linear I fear it may make any algorithm too complex. An alternative could be replacing all $$0$$s in $$s^{*}$$ with '$$-1$$' and then computing the dot product $$s^{*} \cdot s_{opt}$$.

Any help on designing/choosing an algorithm as well as practical advice on how to implement it is much appreciated! Thanks!

• Since the order of vectors is irrelevant, there are only 10^20 / 120 combinations… still too much to handle, and I cannot think of any shortcuts, because the 5th column will totally change the result of the first four. Maybe unless the target vector has very close to either 0 or 60,000 ones. Aug 8, 2021 at 23:46
• About 20% of the target vector is ones @gnasher729. Solving all combinations is definitely not a good solution. I would like to find some sort of heuristic that maybe doesn’t find the absolute best solution but that can run faster. Aug 9, 2021 at 9:30