Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given:

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

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

  • a dense matrix $E$ $(nxn)$ 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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
    
@dabd Yes, I tried to use the same notation as in your post. –  user7530 Jan 29 '13 at 21:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.