# Optimize matrix multiplications

Given:

• vectors $v1, v2$ $(n\times1)$ where entries in each vector are in the interval $[0,1]$. $v1$ and $v2$ can be sparse or dense

• a dense symmetric matrix $M$ $(n\times n)$ (actually a logic matrix where entries are $0$ or $1$)

• a dense matrix $E$ $(n\times n)$ where $E(i,j) = 1-E(j,i)$ if $E(i,j) \neq 0$, $E(i,j) = 0$ if $i=j$ and $E(i,j$) is in the interval $[0,1[$. Is there a name for this type of matrix?

I would like to compute $s = Sum[(v1 * v2^{T}) .* M]$ where .* is the element-wise multiplication operation and Sum is the sum over all entries of the resulting matrix. ^$T$ is the transposition operation.

Given $s$ I would like to obtain $x = Sum[(v1 \cdot v2^{T}) \cdot * E] / s$

Is there any computationally more efficient way to perform these multiplications and obtain $x$?

Thanks.

-
Welcome to MSE! It helps to format your questions in MathJax. I formatted your question, but it could still use improving, but I wanted to leave that to you. Regards – Amzoti Jan 29 '13 at 16:52
it's another way of writing s = v1'Mv2, which is preferable both in notation and for computation. – karakfa Jan 29 '13 at 17:04

The $(i,j)$th entry of the outer product matrix $vw_T$ is, by the definition of matrix multiplication, $$\sum_{k=1}^1 v_{ik}w^T_{kj} = v_{i1}w^T_{1j} = v_i w_j.$$ Therefore the $(i,j)$th entry of the entrywise product $vw^T * M$ is $v_iw_jM_{ij}$, and as Karakfa points out, $$\sum_{i,j} (vw^T * M)_{ij} = \sum_{i,j} v_i w_j M_{ij} = \sum_i v_{i1} \sum_j M_{ij}w_{j1} = \sum_i v^T_{1i} (Mw)_{i1} = v^TMw.$$ Therefore you want to compute $$x= \frac{v_1^T E v_2}{v_1 ^T M v_2},$$ which requires only two matrix-vector multiplications (and two much cheaper vector dot products, and a scalar division).
I don't see any way of taking advantage of $E$'s structure.
for large dimentions this trick might help (triangular decomposition). By definition diag(E) = 1/2, if not adjust with a scalar multiple of I. Define B st. $b_{ij} = e_{ij}-0.5$. Or, stretching notation $B = E - 0.5$. We can decompose $B = L - L',$ where L is a lower triangular matrix (with zero diagonals). Let $v=v_1$ and $w=v_2$ to simplify. Now, $vEw' = v'Bw + 0.5*\text{sum}(v)*\text{sum}(w).$ Also $v'Bw = v'Lw - v'L'w = v'Lw - w'Lv.$ – karakfa Jan 29 '13 at 18:35
I defined the matrix $E$ wrongly. I updated the initial question with the correct definition so I don't know if the trick above applies. – dabd Jan 29 '13 at 20:53
In your notation $*$ is element-wise multiplication here: $vw^T * M$ – dabd Jan 29 '13 at 21:03
In my concrete problem the dimension is $n = 1326$. – dabd Jan 29 '13 at 21:10