8
$\begingroup$

I have two sets of vectors $(\mathbf{l}_i)_{1\le i \le n}$ and $(\mathbf{r}_i)_{1 \le i \le n}$. Each vector $\mathbf{l}_i$ is in $[0,1]^4$, same for $\mathbf{r}_j$. I'd like to maximize the dot product $\mathbf{l}_i \cdot \mathbf{r}_j$, i.e. find tuples $(i,j)$ s.t. $\mathbf{l}_i \cdot \mathbf{r}_j$ is as big as possible.

To be clear, if $\mathbf{l}_i=(\mathbf{l}_{i,1},\mathbf{l}_{i,2},\mathbf{l}_{i,3},\mathbf{l}_{i,4})$ and $\mathbf{r}_{j}=(\mathbf{r}_{j,1},\mathbf{r}_{j,2},\mathbf{r}_{j,3},\mathbf{r}_{j,4})$, then:

$$\mathbf{l}_i \cdot \mathbf{r}_j=\sum_{k=1}^4 \mathbf{l}_{i,k} \mathbf{r}_{j,k}$$

  • The number of tuples I'd like to find should be ideally a parameter of the algorithm, i.e. find the $K$ tuples $(i,j)$ that lead to the greatest values of $\mathbf{l}_i \cdot \mathbf{r}_j$. I won't mention $K$ in the complexities below, let's say $K \ll n$.

  • I'm looking for $O(n \log^k n)$ ideas. The naive algorithm takes $\Theta(n^2)$ time, which is too big for me ($n \approx 2^{20}$).

  • My first idea was to try to solve the problem in dimension 2, with the additional constraint on the input $|\mathbf{r}_j|=1$. In that case it is easy to design a $O(n \log n)$ algorithm: sort all $\mathbf{r}_j$ according to their angle with $(1,0)$, then for all $i$, find $\mathbf{l}_i$ in that list by binary search.

In my opinion, intermediary tasks might be:

  • Try to generalize the formula $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}| |\mathbf{v}| \cos(\mathbf{u},\mathbf{v})$ to dimension $4$.
  • Try to remove the condition $|\mathbf{r}_j|=1$ from the algorithm in dimension $2$.

I have no idea on how to solve these two problems.

I'm asking this in a single question because I'm also interested in more general algorithms that may give approximations (e.g. that solve the "maximum dot product" problem in arbitrary dimension).

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you read this paper: arxiv.org/pdf/1202.6101.pdf ? Their problem is to find the max inner product for only one vector, but the authors seem to suggest that the problem is hard. $\endgroup$
    – WhatsUp
    Commented Jun 14, 2017 at 13:02
  • $\begingroup$ @WhatsUp: No, I didn't even know that the version with online queries of the problem had an official name ("MIPS"). Thank you! I skimmed through the litterature about it. $\endgroup$
    – md5
    Commented Jun 20, 2017 at 15:47

4 Answers 4

Reset to default
5
$\begingroup$

As a completely different approach, assuming that $d < \log n$, one can generate $O(\log n)$ random vectors $w_i$ with unit norm. For each $w_i$ we look at $\langle l_i, w_i \rangle$ and $\langle r_i, w_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d < \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d << \log n$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting approach! Can you justify why this will find the correct (optimal) solution, with high probability? Is there a proof of correctness for this? And why are $O( \log n)$ vectors enough? $\endgroup$
    – D.W. ♦
    Commented Jun 21, 2017 at 16:16
  • $\begingroup$ Actually, the main point here is $d$. The density for the angle (see math.stackexchange.com/questions/1246748/…) is $~sin^{d-2} \theta$. So in order to have that $\theta \leq t = \arccos(r)$, the probability of a single random vector is then $p = \int_0^t sin^2 x dx = t/2 - sin(2t)/4 \approx t^3/3$. One then needs $\frac{\ln \delta}{\ln 1-p}$ random vectors, to succeed with probability $1 - \delta$. Thus, for r=0.99 (i.e., the dot product will be up to 1% smaller), and $\delta=0.01$ one needs about 4927 vectors. $\endgroup$
    – MotiNK
    Commented Jun 23, 2017 at 6:53
  • $\begingroup$ Sorry some rearranging: For $||w||=1$, consider that $\langle l_i, w\rangle \langle r_i, w\rangle = |l_i||r_i|\cos \beta_l \cos \beta_r$. Note that $\cos \beta_l \cos \beta_r = \cos(\beta_l \pm \beta_r) \pm \sin\beta_l \sin\beta_r $, where the $\pm$ signs are both - if $w$ passes between $l_i$ and $r_i$, otherwise they are both +. So the end result is accurate up to a value of $\pm |l_i||r_i|\sin\beta_l \sin\beta_r$. If the angle between $l_i$ and $r_i$ is small, then w.h.p. there is $w$ such that $\beta_l \approx \beta_r$ and $\sin^2 \arccos(r) = 1 - \cos^2 \arccos(r) = 1-r^2$. $\endgroup$
    – MotiNK
    Commented Jun 23, 2017 at 7:19
  • $\begingroup$ Finally, if the angle between $|l_i|$ and $|r_i|$ is "large" (but their absolute values are large enough to be in the results!), there will be some vector that will pass approximately between them and we will still have that $\beta_l \approx \beta_r$ (i.e., there exists some vector which doesn't approximate them well, but is approximately between them). For this vector, the values of $\langle l_i, w\rangle and $\langle r_i, w\rangle$ will be large, so they should be identified as candidates within the results. $\endgroup$
    – MotiNK
    Commented Jun 23, 2017 at 7:22
1
$\begingroup$

In the case of unit-length vectors, this problem reduces to the problem of finding the $K$ pairs of closest points in 4-dimensional space. There are reasonable algorithms for that.

In particular, note that

$$\|\mathbf{u}-\mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2 - 2 \; \mathbf{u} \cdot \mathbf{v},$$

where $\| \cdot \|$ is the 2-norm. If $\|\mathbf{u}\|=\|\mathbf{v}\|=1$, then it follows that

$$\|\mathbf{u}-\mathbf{v}\|^2 = 2 - 2 \; \mathbf{u} \cdot \mathbf{v},$$

so maximizing the dot-product $\mathbf{u} \cdot \mathbf{v}$ is equivalent to minimizing the Euclidean distance between the two vectors, $\|\mathbf{u}-\mathbf{v}\|$. You can use any standard data structure and algorithm for nearest neighbor search for that problem, such as a $k$-d tree. In particular, when the dimension is fixed (as it is here), there is apparently a $O(n \log n)$ algorithm to find the nearest neighbor to each point, from which we can immediately find the $K$ pairs of nearest vectors and thus read off the solution to your problem. See also https://en.wikipedia.org/wiki/Closest_pair_of_points_problem.

When the vectors aren't unit-length, this trick doesn't work any longer, and I don't know how to solve your problem. The following question on CSTheory.SE says there is a $\tilde{O}(n^{4/3})$ algorithm for the problem, but I don't know if it can be done in $O(n \log n)$ time: https://cstheory.stackexchange.com/q/34503/5038

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer. The relation between $||\mathbf{u}-\mathbf{v}||^2$ and $\mathbf{u} \cdot \mathbf{v}$ is in some sense the generalization of $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}||\mathbf{v}|\cos(\mathbf{u},\mathbf{v})$ I was hoping. If computational geometry experts are pointing out a $\tilde{O}(n^{4/3})$ complexity, I don't expect to find a better one. $\endgroup$
    – md5
    Commented Jun 21, 2017 at 15:53
1
$\begingroup$

Not guaranteed to be exact at all, but likely to work pretty well. Let $m > 1$. Perform a k-means++ clustering first (using something like a cover tree for finding the nearest centroid) with $k = O(\sqrt n)$ for each of $l$ and $r$ (where you can do up to $O(\log^{m-1} n)$ clustering iterations). Then compare all the pairwise dot products between $l$ and $r$ centroids, in order to find the top $O(\log^m n)$ clusters to consider. Then check between all the vector pairs between the clusters found. Overall complexity is then $O(n\log^m n)$, assuming that each cluster has $O(\sqrt n)$ points in it.

Improve this answer
$\endgroup$
1
$\begingroup$

Here is another idea.

Key observation:

Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\{O\} \cup \{l_i : 1 \leq i \leq n\}$. Then one may only consider those $l_i$ which are vertices of $H$. Same for those $r_j$.

Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.

The problem is then: how many vectors still remain after this procedure.

Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.

More precisely, if the vectors are uniformly distributed, then it is known e.g. from this paper that the number of remaining vectors is, in average, $O((\log n)^3)$, which is quite small.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Computing a convex hull in $\mathbf{R}^4$ is $\Omega(n^2)$, right? $\endgroup$
    – md5
    Commented Jun 21, 2017 at 11:25
  • $\begingroup$ I was actually not familiar with the convex hull algorithms, so I just gathered information from the wiki page. From what I learnt, there are algorithms, e.g. quickhull, which are at least empirically fast enough. Since this idea is based anyhow on some assumptions of the distribution of the vectors, I wouldn't care much about the worst-case complexity ... $\endgroup$
    – WhatsUp
    Commented Jun 22, 2017 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.