We are given the row vectors $A_1, A_2, \ldots, A_N \in \mathbb{R}^{1 \times r}$, the matrices $B_1, B_2, \ldots, B_M \in \mathbb{R}^{r \times s}$ and the column vectors $C_1, C_2, \ldots, C_L \in \mathbb{R}^{s \times 1}$. The product $A_i B_j C_k$ is a real scalar for all $(i, j, k)$, thus we can find the maximum $x = \max_{i, j, k} A_i B_j C_k$.

Obviously, we can compute $x$ in time $O(NMLrs)$ be calculating $A_i B_j C_k$ for all index combinations. My question is whether we can do better (e.g. find $x$ in $O((NM + ML)rs)$)? If that's impossible, what about finding some good upper bound for $x$?

One idea is to find the convex hull of $\{ A_i B_j \mid i = 1, 2, \ldots, N;\; j = 1, 2, \ldots M \}$, which is spanned by some vectors of the form $A_i B_j$. Then we can only try and multiply those vectors only (instead of all $NM$ possible combinations) with the $C_k$ vectors. However, the convex hull might require all $NM$ vectors, and I have no idea how to compute it fast enough.

Another idea is to find \begin{equation} m^{(+1)}[p] = \max_{i, j} (A_i B_j)[p], \quad m^{(-1)}[p] = \min_{i, j} (A_i B_j)[p], \end{equation} i.e. upper and lower bounds on the $p$th components of the vectors $A_i B_j$. Then \begin{equation} x \le \max_k \sum_{p = 1}^s m^{(\operatorname{sgn} C_k[p])}[p] \cdot C_k[p], \end{equation} but this looks like a very poor bound. In particular, it can only be sharp if there are some $(i, j)$ such that every element of $A_i B_j$ is extremal.

I would be most happy if there was a fast (even if approximate) algorithm for the generalization where chains of matrix products in the form $A_{i_A} B_{i_B} \cdots X_{i_X}$ are considred. I expect that can be obtained by straightforward induction from the solution of the problem above.

  • $\begingroup$ you've got some poor index choice... $\endgroup$ – user394255 Jan 29 '17 at 11:26
  • $\begingroup$ How could I improve it? $\endgroup$ – Kristóf Marussy Jan 29 '17 at 11:27
  • $\begingroup$ usually we denote $u$,$v$ etc. as vectors and denote matrices of size $n \times n$, $m \times m$ etc.. $\endgroup$ – user394255 Jan 29 '17 at 11:29
  • $\begingroup$ Yeah, but I needed something for the number of matrices given for the $O$-notation. But I can change the dimensionality of the spaces for something more readable, I guess. $\endgroup$ – Kristóf Marussy Jan 29 '17 at 11:32
  • $\begingroup$ You can re-use computations: to compute $A_1 B_1 C_1$ and $A_1 B_1 C_2$, you can remember $A_1 B_1$. The problem seems rather hopeless, even with $B$ fixed I do not see a trivial solution. $\endgroup$ – LinAlg Jan 29 '17 at 11:52

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.