most recent 30 from http://mathoverflow.net 2013-06-18T21:20:13Z http://mathoverflow.net/feeds/question/15821 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15821/approximating-a-set-with-fixed-number-of-elements Nemanja 2010-02-19T16:31:48Z 2010-02-19T20:27:22Z

<p>I have a set <em>S</em> of real numbers, and I would like to create a new set <em>R</em> with exactly n real numbers (not necessarily from the set) that represent it best.</p> <p>What I mean by best?</p> <p>Well, I have query that asks for given point what is the closest point from S to that point, and when I ask same thing for set R I would like to have best fit to the real answers.</p> <blockquote> <p>To be specific, how do I minimize the <a href="http://en.wikipedia.org/wiki/Hausdorff%5Fdistance" rel="nofollow">Hausdoff distance</a> between <em>S</em> and <em>R</em>?</p> </blockquote> <p>I hope I've been clear enough in what i want. I've heard of mathoverflow, so I said to myself why wouldn't I ask for help there. </p> <p>Thank you in advance.</p> <p>(<strong>Edited</strong> in light of the comments below.)</p>

http://mathoverflow.net/questions/15821/approximating-a-set-with-fixed-number-of-elements/15823#15823 Russell O'Connor 2010-02-19T17:01:16Z 2010-02-19T17:06:32Z

<p>You can measure the distance between closed sets using the <a href="http://en.wikipedia.org/wiki/Hausdorff%5Fmetric" rel="nofollow">Hausdorff metric</a>. Two closed sets will have distance 0 iff they are the same set.</p> <p>To compute the best approximation will probably depend quite a bit on how your (hopefully closed) set is represented.</p>

http://mathoverflow.net/questions/15821/approximating-a-set-with-fixed-number-of-elements/15827#15827 sheldon-cooper 2010-02-19T17:42:03Z 2010-02-19T20:27:22Z

<p>I'd use k-means clustering (with k = n) to find the n centroids and use these centroids as the set R. </p> <p>k-means minimizes the expected L2 distance (i.e. $|x-c|^2$, not $|x-c|$, in case that's important -- in many cases it's not) between a point and its centroid. If all of your new testing points are in the training set, then the ideal distance (in S) would be 0, and the new distance (in R given by the centroids) will be minimized by k-means. If your testing points are different from the training points, but come from the same distribution, then this will minimize an upper bound on the distance.</p> <p>In principle, k-means clustering is NP-hard in most cases. One particular algorithm (called k-means algorithm) seems to work well in many practical cases.</p>

http://mathoverflow.net/questions/15821/approximating-a-set-with-fixed-number-of-elements/15838#15838 Suresh Venkat 2010-02-19T19:50:31Z 2010-02-19T19:50:31Z

<p>This is the $k$-center problem (or in your notation, the $n$-center problem). you're given a set $S$ of points, and you want to find a set $R$ of $n$ points such that the set of balls of radius $r$ around each point in $R$ cover all of $S$, and $r$ is minimized. </p> <p>Your metric space is the line, so this problem is relatively easy to solve. Here's a two-step approach: First, "guess" the optimal solution r (ie. pick some value of r). Now go from left to right, assigning centers greedily, which is to say, as far away from the previously placed center as possible, while covering all points. If you use up $n$ points before covering all of $S$, your guess was wrong, and you need to restart with a larger value of r. Else, you're done.</p> <p>Now of course $r$ is a real number, but there are only discretely many "guesses", since the optimal r must be such that there are two points at distance exactly $r$ from a center (otherwise r is not optimal). so the total set of choices of r is merely the set constructed from measuring the pairwise distances and halving them. </p> <p>All of this assumes you're in algorithms-land, which means that you have reasonable ways of representing points and comparing them. </p> <p>p.s this algorithm is well known (not original). </p>