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!

  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Aug 8 at 23:46
  • $\begingroup$ 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. $\endgroup$ Aug 9 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.