title: How to calculate an error-minimizing approximation to a numerical array
body: <p>Given an array of numerical values (integers or floats, either is fine) and a positive integer N, I want to return an array of N values such that, if each value in the original array is replaced by its closest match in the returned array, squared error (i.e. (original_value - approximation) ^ 2) is minimized. Basically, to find a smaller array that best approximates the input array.</p>
  
  <p>The case for N = 1 is trivial, with some basic algebra one can easily show the answer is the mean of the values. </p>
  
  <p>One can also show that after sorting the input array, each "return" value must correspond to a sequential set of values from the input array, its value being their mean. So for N = 2, at worst we can just start with one set with sorted_input[0] and another set with all other values, and one by one sequentially move items to the first set, returning whatever combination minimizes error in O(n) (ignoring the sorting costs)</p>
  
  <p>However, at N = 3 and beyond it's not clear how to proceed. Trying all combinations naively becomes O(n^(N-1)), and although it feels like they should exist, I can't prove any optimizations are "safe" (i.e. won't get stuck in some local minimum that gives a non-optimal result)</p>
  
  <p>It may very well be the case that the problem is actually NP-hard (I can't even figure how to verify a solution in polynomial time!), but it feels like the sort of problem where a bit of mathematical trickery can result in huge speedups, so I figured I would ask for any ideas. Note that I'm looking for the <em>optimal</em> solution, not just a decent approximation.</p>