0
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ How long is your vector? A small fixed length? Or variable and possibly very long? $\endgroup$ – Alnitak Nov 26 '13 at 11:12
  • $\begingroup$ 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. $\endgroup$ – Brannon Nov 26 '13 at 15:27
  • $\begingroup$ 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. $\endgroup$ – user834 Nov 26 '13 at 16:05
  • 1
    $\begingroup$ 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. $\endgroup$ – user834 Nov 26 '13 at 16:08
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Dec 2 '13 at 0:42

Your Answer

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

Browse other questions tagged or ask your own question.