Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $0$ or $1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\ V_2=(c_{2,1} ... c_{2,l}),\\ .....\\ V_n=(c_{n,1} ... c_{n,l})\end{array}$$ each $c_{i,j}$ are $0$ or $1$. $n\lt 2^l$ is some number. (For example in my case: $n=2^{10}, l=20$).

Problem: I need to calculate inner products $(R, V_i)$ - how to do this in the fastest way ? I mean how to organize calculations such that number of additions will be the smallest ? The point is that some vectors have same subsequences of 1 and 0, so I do not need to calculate several times such pieces.

Background: $V_i$ is fixed once and forever, "R" is coming every "millisecond".

Example: $V_1 = (1, 1 , 0 , 1)$ $V_2 = (1, 1 , 1 , 1)$

Algorithm:

x = r_1+r_2+r_4
y= x+r_3

So $(R, V_1) = x$ ; $(R, V_2) = y$; required only 3 additions, instead of naively seen $5=2+3$.

• Do you know anything about the structure of the overlapping subsequences? Nov 6 '10 at 10:05
• Simultaneous crossposting is discouraged. Why do some people try to trick other people into doing duplicate work? mathoverflow.net/questions/45051/… Nov 6 '10 at 13:57
• I do not want to "trick", I am a novice here and there, and just think no so many people looking both forums, actually I do not quite understand why not to make 1 forum. Any way I ask for excuse if cause inconvinience for somebody.
– Alexander
Nov 6 '10 at 15:33
• "Structure of overlapping sequences" - may be there is some specific structure - I do not know - if you advise me what to look I will look for it.
– Alexander
Nov 6 '10 at 15:37
• Actually, Alexander, one of the characteristics of a good question is providing an adequate background, jungle or otherwise. Nov 6 '10 at 19:19

Well, if you dont mind some approximation than regular dimension reduction techniques would give you some speedup as they preserve (approximately) dot product.

Otherwise, you can think about each vector as being a CNF clause. If you just have to decide if the dot product is not zero for all vectors, then what you are asking for is the shortest equivalent DNF to the given CNF (or to be more precise some kind of minimal computation that compute the given CNF). This however is easier than the problem of deciding if the given CNF is never satisfiable, which is co-NP complete. In short, this problem should be computationally hard.

I think there was quite a bit of work on stuff like that in the learning community, especially in the dinosaurs age ;) (80s and earlier?).

• @Sariel Har-Peled: +1 for "dinosaurs age" :) Nov 6 '10 at 10:56
• Well, about approximation - it is better to calculate exactly in my task, appxoximations can be also considered, but has less priroty for me. But if you can suggest some way how to do this - it is highly welcome.
– Alexander
Nov 6 '10 at 16:53
• No I do not want to decide is it zero or not, actually I need to find maximum and second maximum of these products, but for some reasons I think that for the moment the best way to to calculate them all and then get max and submax.
– Alexander
Nov 6 '10 at 16:55
• that's an important data point. if you only want the max (and maybe the second largest) then maybe something better might be doable. Nov 6 '10 at 16:58
• Approximation: The JL lemma preserves angles between vectors. As such, if you take a random projection matrix $M$ and multiply all your vectors $v_i = V_i M$. Now, given $R$ you compute $r= R M$. The matrix $M$ has dimensions $l\times k$, where $k = O( \epsilon^{-2} \log n)$. Thus, given a query $R$, after $O( l k )$ time, you have the vector $r$. Computing $<r,v_i>$, for all $i$ takes $O(n k)$ time, which is an improvement over the naive $O(n l)$. Naturally, the estimates $<r,v_i> \in (1+\pm \epsilon)<r,V_i>$, with high probability in $n$. Nov 7 '10 at 2:13

There are two key points in your question:

• The $V_i$ are fixed
• They are 0-1 vectors.

One idea that comes to mind to exploit these things is to use a trie. Think of each $V_i$ as encoding a string consisting of all the dimensions where the vector has a nonzero entry. If you now build a trie over this set of strings, it will capture the common substructures that you'd like to exploit. For example, in your example above, $V_1$ becomes $124$ and $V_2$ becomes $1234$, and the trie structure will allow you to compute the $12$ segment simultaneously.

But it's not optimal, because the dimensions don't have a natural ordering. If you wanted to couple this with a procedure that reorders the dimensions initially so that in each vector, all the 1s are as close to being consecutive as possible (you can do this heuristically using a hamming-space TSP on the columns of the matrix V), and then build a trie, then you can get even more improvement.

Ultimately given your sizes (1024 and 20), simple heuristics are likely to work better than more complicated ones, so even the simple trie idea might help.

• Dear Suresh, thank you very much for yours kind answer. I will look on "trie". Actually my question is almost the same as you asked -- "sparse FHT". I apreciate Martin's suggestion, but it seems one might get a little more - this I am trying to do.
– Alexander
Nov 6 '10 at 16:46
• Relation with FHT: consider H_2 = (1 1; 1 -1 ) if we add matrix (1 1; 1 1) and divide result by 2: we get (1 1, 1 0) i.e. all "-1" are substituted by zeros. So H_2*v is the same 2*(1 1, 1 0)*v - (1 1; 1 1)*v. In my particular task it is enough to calculate (1 1, 1 0)*v. So from FHT we come to the question above. Taking a sparse vector "v" we obtain some quite generic rectangular matrix with (0,1) components - so the question of fast calculation of sparse FHT is related to this question.
– Alexander
Nov 7 '10 at 7:08

If I've understood the question correctly, this is just multiplying a fixed 0-1 matrix V with given vectors. You want to optimize these multiplications by doing some processing on the matrix V.

You can think of each $(V_i,R)$ as a depth 1 arithmetic circuit. $V R$ will be a very simple arithmetic circuit (depth 1, size $n$ sum of variables for each inner product, so it is a depth 1 circuit of size $n^2$ using only addition). You want to find the minimum size arithmetic circuit which computes the same function.

For general arithmetic circuits this is hard, but I am not sure if it is still hard if you restrict it to such a small and simple subclass of circuits. Assuming that we are going to use only $+$, then it can perhaps be solved by a simple greedy or dynamic algorithm. On the other hand, this can also be a NP-hard problem, since it is very close to computing the minimum size circuit for a given CNF of size $n^2$. (If you could take the product of the results of inner products.)

• Dear Kaveh, thank you very much for yours kind answer. Is my understanding correct that 1) compute min size circuit for general CNF is NP-hard ? (Is it some standard fact ?) 2) Yes it seems that taking a product we came something similar to this problem. Is there any way to deduce that problems are equivalent ?
– Alexander
Nov 6 '10 at 18:44
• @Alexander : You are welcome. 1. Yes, it is NP-hard if I am not making a mistake. Search for "circuit minimization problem". 2. I don't have a reduction right now, that is why I have said that it is very close to circuit minimization for CNF's. Btw, it is probably easier if you just want to reduce the number of additions and don't need to find the best circuit. Nov 6 '10 at 19:56
• Why minimizing number of additions may be easier than "minimum circuit" ? If have an algorithm minimizing addition number - we can make circuit - or may be I have misunderstanding about circuits...
– Alexander
Nov 7 '10 at 7:00
• @Alexander: by reducing the number of additions I meant that we are not looking to find th best/optimal way to add, we just want to reduce the number of them, the new circuit will do better than th original one but there maybe other circuits that have even less additions. Nov 7 '10 at 8:12
• Well, if the problem is NP-hard, is there still some way to test that some "guessed solution" is really the optimal one ?
– Alexander
Nov 7 '10 at 18:49