Maximize entrywise 1-norm of matrix product

Question

I have $8$ sets $E_1, \ldots, E_8$, each one of size $256$, whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find:

$$\underset{M_1 \in E_1, \ldots, M_8 \in E_8}{\max} ||M_1 \times \ldots \times M_8||_1$$

where:

$$||M||_1=\sum_{i=1}^4\sum_{j=1}^4 M_{i,j}$$

A reasonable time complexity might be approximately $2^{32}$ (time complexity of the naive algorithm is $2^{79}$).

My first idea would be to look for interpretations in various mathematic fields:

• geometry: matrix product in an euclidian space.
• probability: it reminds me of Markov chains (but the $M_i$ are not normalized).

Is there any known work about this?

Answer 1

Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far. I don't know how well it will work; you'll probably have to implement and try it to find out.

Suppose we have two sets $S_1,S_2$ of matrices, and we want to find $M_1 \in S_1, M_2 \in S_2$ that maximizes $\|M_1 \times M_2\|_1$. Here's a plausible approach. First, sort the matrices in each set by decreasing value of $\|\cdot\|_1$ norm. At each stage, we'll keep track of the largest value of $\|M_1 \times M_2\|_1$; let $\ell$ denote that largest-seen-so-far value. We'll exploit the inequality

$$\|M_1 \times M_2\|_1 \le \|M_1\|_1 \times \|M_2\|_1$$

to prune the set of combinations we need to test. In particular, we'll enumerate matrices $M_1 \in S_1$ in order of decreasing $\|\cdot\|_1$ value. For a fixed $M_1$, only need to examine matrices $M_2 \in S_2$ such that $\|M_2\|_1 > \ell/\|M_1\|_1$ (thanks to the above inequality, there's no point in examining the other candidates for $M_2$). For each candidate pair, we'll compute the value of $\|M_1 \times M_2\|_1$ and update $\ell$ if it is larger than any seen so far.

In this way, we obtain the following algorithm:

• Set $\ell := -\infty$.

• For each $M_1 \in S_1$, in decreasing order of $\|\cdot\|_1$ norm:

  • For each $M_2 \in S_2$, in decreasing order of $\|\cdot\|_1$ norm:

    • If $\|M_2\|_1 \le \ell/\|M_1\|_1$, break out of the inner loop and go on to the next iteration of the outer loop.

    • Otherwise, if $\|M_1 \times M_2\|_1 > \ell$, set $\ell := \|M_1 \times M_2\|_1$.

What's the running time of this approach, if $S_1$ and $S_2$ are each of size $n$? I don't know. At worst, it is $O(n^2)$, but one could hope that it might be significantly better -- if we're very lucky, it'll be more likely $O(n \log n)$ (to sort the two sets).

How do we apply this to your problem? Naively, we can set

$$\begin{align*} S_1 &= \{M_1 \times M_2 \times M_3 \times M_4 : M_i \in E_i\}\\ S_2 &= \{M_5\times M_6 \times M_7 \times M_8 : M_i \in E_i\} \end{align*}$$

and then apply the above algorithm. Here $|S_1|=|S_2|=2^{32}$, so if we're very lucky, this might be efficient enough to apply to your situation.

With a bit more sophistication and implementation complexity, you might be able to apply this recursively. The above procedure gives a way to enumerate products $M_1 \times M_2$ in decreasing order of $\|M_1 \times M_2\|_1$, given a set of candidates for $M_1,M_2$. So, you could apply that to $E_1 \times E_2$ and $E_3 \times E_4$ to find $S-1 = E_1 \times E_2 \times E_3 \times E_4$, etc. You could also use some kind of iterative deepening, to only enumerate combinations such that the norm of their product exceeds some lower bound, and gradually decrease the lower bound as needed.