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.

I am seeking for an efficient algorithm to count the number of 1's in the outer product $\textbf{u}\textbf{v}^T$, where $\textbf{u}$ and $\textbf{v}$ are both binary column vectors.

The dimension of $\textbf{u}$ is about 50, and the dimension of $\textbf{v}$ is about 20,000. I have a loop of about 1,000,000 iterations, in each iteration, one (and only one) element of both $\textbf{u}$ and $\textbf{v}$ are randomly chosen and are overwritten with 0 or 1 (could be the same as the old value).

I would like to know something in MATLAB that could finish this task on a desktop machine (no parallel, no cluster) within 3 seconds (or 5 seconds, depend on hardware). I've tried $bsxfun()$, $gpuArray()$, and all those tricks I know of, but without luck.

share|improve this question
    
Sorry, I made a mistake. It was not for the whole matrix $\textbf{u}\textbf{v}^T$, but for a pre-defined index subset, say $\sum_{(i,j) \in S} M(i,j)$, where $M=\textbf{u}\textbf{v}^T$ and $S$ is a pre-defined subset. –  David Tan Nov 28 '12 at 18:33
add comment

1 Answer 1

up vote 4 down vote accepted

If both $u,v$ are 0-1 vectors, the number of ones in $uv^T$ is the no. of ones in $u$ times the no. of ones in $v$. So, how about sum(u)*sum(v)?

Edit: That doesn't mean you should really sum up $u$ and $v$ inside the loop, because even MATLAB's sum function is still very slow. Instead, you may keep track of count $r=$ no. of ones in $u$ and the count $c=$ no. of ones in $v$. For example, in each iteration, if the $i$-th element of $u$ is selected and it switches from 0 to 1, increment $r$ by $1$. Update $c$ in a similar manner. Now the number of ones is computed as $r\times c$ at the end of each iteration. On my 4-year old PC with the antique MATLAB 5.3 installed, one million iterations cost only 7 seconds.

share|improve this answer
    
Say $S=\{(1,2),(1,3),(2,1)\}$, $\textbf{u}=(1,0,0,1)^T,\textbf{v}=(1,1,0,0)^T$, the outer product is $(1100;0000;0000;1100)$. So the sum I wanted is $1+0+0=1$. Next, if $\textbf{u}(3)$ is flipped to 1, we end up with $(1100;0000;1100;1100)$, the sum is still $1+0+0=1$ (but the matrix changed). Note, the subset $S$ will not change during the whole process. –  David Tan Nov 28 '12 at 18:44
    
@DavidTan: In your modified problem, you are essentially counting the no. of 1s in a (sparse?) submatrix $S$. since $S$ is merely a list of points without special structure, I don't think one can make a counting procedure much faster than a brute force count. But surely don't take my word for it. You may pose a new question to the forum, and see if the others can help. –  user1551 Nov 29 '12 at 11:40
add comment

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.