4
$\begingroup$

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no such set exists?

As some motivation, if I have 3 vectors (so that $n=1$), the minimum value of their pairwise dot products if $-3/2$, given by them forming the corners of a triangle. This places all 3 vectors in the same two-dimensional plane. Anything out of that plane (so, more than 2 dimensions) will raise the minimum to some sum $>-3/2$. If I go to a fewer number of dimensions by constraining all the vectors to 1D, then my only possible sums are -1 or 3.

In general, if I have $2n+1$ vectors, then by putting them at corners of a $2n$-simplex, you get a sum of dot products of $-(2n+1)/2$. But by putting them in 1D, you get a minimum of $-n$. I'd like to find sets of vectors that "don't look very 1D" in the sense that they violate this bound.

This is equivalent to the question, "Find an odd-size set of vectors such that their sum has length less than 1" -- the equivalence can be shown by taking the norm of the sum. I think this is more natural, so I'll change the question title.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't see the equivalence, but I don't understand why it's hard to find an odd-sized set whose sum has length < 1. Just take any vectors $v_1,\dots,v_{2n}$ and any vector $w$ whose length is less than 1, then set $v_{2n+1}=w-v_1-\dots-v_{2n}$, as then the vectors $v_1,\dots,v_{2n+1}$ sum to $w$. That seems to suffice. What am I missing? It seems too simple. Have I misunderstood something? $\endgroup$ – D.W.♦ Feb 22 '18 at 7:26
  • $\begingroup$ Sorry, I guess I was unclear -- I mean, find a set of vectors, in a given set. This is an algorithms question: I hand you $k$ unit vectors, now, can you find in that set some $2n+1 \le k$ that sum to a norm less than 1? How efficiently can you find such a set (or become certain that none exists)? $\endgroup$ – Alex Meiburg Feb 22 '18 at 7:32
  • $\begingroup$ OK. Is $n$ given as an input? Or am I free to choose any size of set, as long as the size is odd? I think it would help to edit the question to state the problem that way, as the current statement in the last paragraph doesn't convey that to me. $\endgroup$ – D.W.♦ Feb 22 '18 at 16:53
  • $\begingroup$ Perhaps LLL lattice reduction might be helpful. $\endgroup$ – D.W.♦ Feb 22 '18 at 16:55
2
$\begingroup$

The latter problem feels similar to the Shortest Vector Problem (SVP) in integer lattices.

The Shortest Vector Problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length as short as possible

Your problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length $\le 1$, such that the number of vectors in the subset is odd

If we omit the "odd-size" constraint for the moment, the two are very similar: one asks for the sum to be as small as possible, the other asks for the sum to be $\le 1$. Thus, any algorithm for SVP would immediately yield an algorithm for your problem (ignoring the odd-size constraint). And solving your problem sounds like it might be about as hard as the SVP (if we replace $\le 1$ with $\le t$ where $t$ is an additional input, your problem becomes as hard as the SVP; reduction by binary search on $t$).

Unfortunately, the SVP is hard: roughly speaking, it's hard if $P \ne NP$ (this isn't quite right, but it's close). This makes me think that your problem might be hard, too.

That said, there are approximation algorithms for the SVP. You can use LLL lattice reduction to find a subset whose sum is not too much larger than the shortest possible. Unfortunately the gap between "the true minimum" and "what LLL finds" is pretty large, so this might not be good enough in practice. But it is something you could try and see if you get lucky.

I'm not sure how to accommodate the extra restriction that the subset be of odd size. You could try solving with LLL reduction and hope the resulting subset has odd size (50% chance). I can't think of a better technique, unfortunately.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I was thinking about this this morning and came to a similar conclusion. I had considered LLL earlier but was worried about odd-size constraint and the 0-1 constraint (that you can't repeat vectors). But: I realized that if you search in the whole integer lattice, and can find a vector with length < 1, this implies some vector in the 0-1 sense as well, and I think you can recover that quickly. (Something something triangle inequality). $\endgroup$ – Alex Meiburg Feb 22 '18 at 19:51
  • $\begingroup$ As for the odd-size constraint, then, we can ask for sums of the form $v_1 + x_2(v_2-v_1) + x_3(v_3-v_1) + \dots + x_k(v_k-v_1) + x_1(2v_1)$, where the $x_1$ are integers. Any sum of this form is an odd number of the original vectors. So then it becomes a 'closest vector problem' (CVP) in all of those, where we're trying to get close to $v_1$. I understand the LLL can also be used to try to find approximate solutions to the CVP. $\endgroup$ – Alex Meiburg Feb 22 '18 at 19:53
2
$\begingroup$

I have now learned that this problem is co-NP-complete. The question can be reduced to testing whether a point in $R^{n^2}$ (given by the Gram matrix generated by the vectors) satisfies all the pure $(2k+1)$-gonal hypermetric inequalities. This fact is stated (without proof?) on Page 454 of "Geometry Cuts and Metrics" by Michel Deza and Monique Laurent, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.215.1108&rep=rep1&type=pdf .

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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