<p>I have a vector (er, array) that is the sum of a number of other known vectors. I would like to reverse the process and find the specific known vectors that were summed to make the final vector. The problem appears to be similar to the subset-sum problem. I see some algorithms for the subset sum problem on the internet. However, it's not clear if they would work for my scenario. </p>

<p>Do you have any suggested algorithms for this problem? Can someone help me write the problem in summation notation? Can you see some way of grouping the vectors out of the solution set for a branch and bound algorithm approach?</p>

<p>I've attempted to solve the problem with a matrix multiply; details here: <a href="https://math.stackexchange.com/questions/516208/minimize-ax-b-where-x-is-a-binary-vector">https://math.stackexchange.com/questions/516208/minimize-ax-b-where-x-is-a-binary-vector</a></p>

<p>I've attempted to solve the problem with genetic algorithms. I'm no longer a believer in evolution. Details here: <a href="https://stackoverflow.com/questions/17297313/genetic-algorithms-name-the-piece-that-drives-the-mutation-location">https://stackoverflow.com/questions/17297313/genetic-algorithms-name-the-piece-that-drives-the-mutation-location</a></p>

<p>(The known vectors are smaller than the final result, but I can fake a full length through an approach of "known vectors at all possible offsets". My numbers all range between -1 and 1. It seems I could add 1 to make them all positive.)</p>

CC BY-SA 3.0
2013-11-26T11:12:32.410Z
How long is your vector? A small fixed length? Or variable and possibly very long?
Alnitak
CC BY-SA 3.0
2013-11-26T15:27:43.960Z
I can sample my data such that the final vector will be 100k numbers in length. The known pieces will be 10k numbers long. Any given number has no more than 10 pieces contributing to it.
Brannon
CC BY-SA 3.0
2013-11-26T16:05:15.833Z
There is an easy reduction from the 'vectorized' version of subset sum and the normal subset sum by padding each 'column' with enough zeros so that subsequent additions will not 'bleed' into the other columns (that is overflow via addition).  Though only one type of reduction, this gives you a rough sense of how the bit size of the entries compares with the number of integers you have.  In general, dynamic programming solutions only work for bit sizes that are exponentially smaller than the number of numbers.
user834
CC BY-SA 3.0
2013-11-26T16:08:10.470Z
LLL and other lattice reduction techniques have enjoyed moderate success with larger instances, but as far as I know, there are no good algorithms for anything other than when bit sizes that are exponentially smaller than the list length.
user834
CC BY-SA 3.0
2013-11-30T20:55:25.803Z
A straightforward reduction from exact 3d matching implies that this problem is NP-hard even when the sum vector is all 1s, and each addend vector has three 1s and all other coordinates 0.
Jeffε
CC BY-SA 3.0
2013-12-02T00:42:13.570Z
Why don't you tell us the exact parameters?  What are the lengths of the vectors?  You said the target vector is a sum of other known vectors.  How many known vectors are there?  How large is the sum?  (i.e., the target vector is a sum of $k$ out of $n$ known vectors; what are $k$ and $n$?)  Also, I could not understand your prior comment: all vectors have to be the same length, so I don't understand how some can be 10K in length and some others are 100K in length.  That doesn't make any sense to me.  Clarification?  Also, please edit these details into the question.
D.W.
<optimization><genetic-algorithms><dynamic-algorithms>
dynamic algorithms for the subset-sum problem hold for vectors?
Brannon
# dynamic algorithms for the subset-sum problem hold for vectors?

(Asked by: username_0 on 2013-11-26)

I have a vector (er, array) that is the sum of a number of other known vectors. I would like to reverse the process and find the specific known vectors that were summed to make the final vector. The problem appears to be similar to the subset-sum problem. I see some algorithms for the subset sum problem on the internet. However, it's not clear if they would work for my scenario.

Do you have any suggested algorithms for this problem? Can someone help me write the problem in summation notation? Can you see some way of grouping the vectors out of the solution set for a branch and bound algorithm approach?

I've attempted to solve the problem with a matrix multiply; details here: <https://math.stackexchange.com/questions/516208/minimize-ax-b-where-x-is-a-binary-vector>

I've attempted to solve the problem with genetic algorithms. I'm no longer a believer in evolution. Details here: <https://stackoverflow.com/questions/17297313/genetic-algorithms-name-the-piece-that-drives-the-mutation-location>

(The known vectors are smaller than the final result, but I can fake a full length through an approach of "known vectors at all possible offsets". My numbers all range between -1 and 1. It seems I could add 1 to make them all positive.)

**Tags:** optimization, genetic-algorithms, dynamic-algorithms
> **Comments:**
> **username_1**: How long is your vector? A small fixed length? Or variable and possibly very long?  
> **username_0**: I can sample my data such that the final vector will be 100k numbers in length. The known pieces will be 10k numbers long. Any given number has no more than 10 pieces contributing to it.  
> **username_2**: There is an easy reduction from the 'vectorized' version of subset sum and the normal subset sum by padding each 'column' with enough zeros so that subsequent additions will not 'bleed' into the other columns (that is overflow via addition).  Though only one type of reduction, this gives you a rough sense of how the bit size of the entries compares with the number of integers you have.  In general, dynamic programming solutions only work for bit sizes that are exponentially smaller than the number of numbers.  
> **username_2**: LLL and other lattice reduction techniques have enjoyed moderate success with larger instances, but as far as I know, there are no good algorithms for anything other than when bit sizes that are exponentially smaller than the list length.  
> **username_3**: A straightforward reduction from exact 3d matching implies that this problem is NP-hard even when the sum vector is all 1s, and each addend vector has three 1s and all other coordinates 0.  
> **username_4**: Why don't you tell us the exact parameters?  What are the lengths of the vectors?  You said the target vector is a sum of other known vectors.  How many known vectors are there?  How large is the sum?  (i.e., the target vector is a sum of $k$ out of $n$ known vectors; what are $k$ and $n$?)  Also, I could not understand your prior comment: all vectors have to be the same length, so I don't understand how some can be 10K in length and some others are 100K in length.  That doesn't make any sense to me.  Clarification?  Also, please edit these details into the question.  

---

## 0 answers

