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.
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
sumfunction 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.