Efficiently sampling points from an integer lattice. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:31:22Z http://mathoverflow.net/feeds/question/10864 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice Efficiently sampling points from an integer lattice. Wilson 2010-01-06T00:02:59Z 2010-01-06T10:00:20Z <p>Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m &lt; n$. For each $x \in \mathcal{L}$, let w : $\mathcal{L}$ $\rightarrow$ $\mathcal{R}^+$ denote an efficiently computable weighting function. Let $\mathcal{D}$ define a probability distribution over $\mathcal{L}$ that selects each element from $\mathcal{L}$ with probability proportional to its weight: $$\Pr_\mathcal{D}[x] = \frac{w(x)}{\sum_{y\in\mathcal{L}}w(y)}$$</p> <p>I would like to (approximately) sample from this distribution efficiently, where efficiently means in time polynomial in n, the dimension of the space. The algorithm may query the weight function $w$ a polynomial number of times. In general, this is hard, but I know two additional facts about the weighting function that I suspect make the problem tractable.</p> <p>1) The weight function is convex: in particular, for any C, the set of points with weight at least C lies inside some convex polytope.</p> <p>2) The weight function is Lipschitz: for any $x,y \in \mathcal{L} : ||x-y||_1 \leq 1$, $|w(x) - w(y)| \leq$ poly(n).</p> <p>Is there a known method that would allow efficient sampling from this distribution?</p> http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice/10878#10878 Answer by Wilson for Efficiently sampling points from an integer lattice. Wilson 2010-01-06T04:17:29Z 2010-01-06T04:17:29Z <p>Yes, there is just one weight function w. </p> http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice/10904#10904 Answer by Thorny for Efficiently sampling points from an integer lattice. Thorny 2010-01-06T10:00:20Z 2010-01-06T10:00:20Z <p>Is your weight convex or concave? Your property 1) is self-contradictory.</p> <p>In the concave case, you can just take a uniform, polynomial size sample from your simplex and select your point from this selection based on the actual weights.</p> <p>In the convex case, the same algorithm works if the average of $w$ is comparable to the maximum (both can be obtained in polynomial time by taking a uniform sample and by local descent respectively). If that is not the case, then you can test the same property for the projection of $w$ onto one of the facets of $\mathcal L$. If this projection has the required property, you sample from that facet according to the projected weight and then sample from the fiber over the selected point according to $w$ if the property still does not hold, you take an $n-2$ dimensional face etc. When you get down to vertices, you already know that $w$ is concentrated around the vertices of $\mathcal L$ and can find neighbourhoods of them containing almost all of the weight and having the property of the average of $w$ being comparable to the maximum of $w$ within these neighbourhoods (choose the entire $L$ and repeatedly shrink it by a factor of $1-\frac{1}{poly}$ and test the condition). From those neighbourhoods, choose one according to their total weight, and within the chosen one, take a polynomial size uniform sample and sample according to $w$ from within it.</p>