# Approximate maximum dot product between a vector and set of vectors using only a single vector representation for the latter

If we have a vector $$q$$ and a set of vectors $$D = \{d_1, d_2, ..., d_l\}$$ is there a way to create functions $$QF$$ and $$DF$$ such that $$QF(q)^TDF(D) \approx \max_i(q^Td_i)$$ ?

Use case:

I want to build an information retrieval system in which documents are represented by an arbitrary but small ($$<100$$) number of vectors and the query is represented by a single vector. Ideally, I would like to sort the documents based on $$\max_i(q^Td_i)$$ but storing all vectors and computing on query time each $$q^Td_i$$ term for each document does not scale. I was wondering if there is a way to combine the $$d_i$$ into a single vector and use this vector somehow to approximate the aforementioned score.

• the single vector can be constructed by taking maximum entry from each vector for each dimension. This guarantees that the dot product will be maximum Jun 11 at 15:24
• with some care to take account of sign of entry per dimension (here for example you can match the sign of the query vector for this entry) Jun 11 at 15:25
• Nice question. max seems very non-linear so it would be strange if it existed, it would be very interesing to know the theoretical answer (mathoverflow or cs.theory might have more experts). Thinking of the practical side, did you consider similarity search in the table of your vectors first and looking up the document second? The first step must have an extremely solid background both from the theoretical and the practical side and the second step is completely standard. Jun 18 at 7:05