1

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.

Kasra Manshaei
  • 139
dabd
  • 135
  • 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 Answers1

1

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.

user7530
  • 49,280
  • 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
  • I tested your shortcut and it works perfectly. Now I should try the triangular decomposition. Thanks. Could you please explain how did you derive this? $$\sum_{i,j} (vw^T * M){ij} = \sum{i,j} v_i w_j M_{ij} = v^TMw.$$ – dabd Jan 29 '13 at 22:05
  • @dabd I've added more steps. – user7530 Jan 29 '13 at 22:41
  • Thank you for the details. – dabd Jan 31 '13 at 02:13
  • size of ~1500 is not large, you don't need specific trick. Standard multiplication will be fast as well. Triangulation will help to minimize storage needs and you can do the two vector multiplication in one pass. eg. instead of computing Lw and Lv separately you can create a 2 column matrix [w v] and multiply once by L[w v], then separate the result. Iterating over matrix elements is expensive (comparatively) and this trick will minimize this. – karakfa Jan 31 '13 at 13:45
  • "" is scalar multiplication in 0.5sum(v)*sum(w); where sum(v) is sum of elements of vector v. Or a better notation might be sum(v)=v'1, where 1 is a vector of units (ie scalar value 1) of the right size. – karakfa Jan 31 '13 at 13:46
  • If the values in $E$ are the values of some random variable $X$ and $$x= \frac{v_1^T E v_2}{v_1 ^T M v_2},$$ is the expected value $E[X]$ then how do I compute the variance $Var[X]$ in matrix form?

    I tried using the same formula for $x$ but using a matrix where the entries are $(E_{ij}-x)^2$ instead of $E$ according to the variance definition $Var[X] = E[(X-\mu)^2]$. However, I get a different result than if I use the equivalent definition of variance $Var[X] = E[X^2]-(E[X])^2$. In this case I square the entries in $E$ and apply the original formula and subtract $x$ squared.

     – dabd Feb 07 '13 at 13:29
  • @dabd I recommending posting that as a new question. – user7530 Feb 07 '13 at 15:50