patternMinor
Among $k$ unit vectors, find odd set with sum length less than 1
Viewed 0 times
sumamongvectorssetwithlengththanlessfindodd
Problem
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-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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#88439, answer score: 2
Revisions (0)
No revisions yet.