Muestreo eficiente de puntos desde una red entera.

Question

Deje $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denota el conjunto de los enteros puntos en el positivo orthant de la $\ell_1$ bola de radio $m$ donde $m < n$. Para cada una de las $x \in \mathcal{L}$, siendo w : $\mathcal{L}$ $\rightarrow$ $\mathcal{R}^+$ denotan una manera eficiente computable función de ponderación. Deje $\mathcal{D}$ definir una distribución de probabilidad sobre $\mathcal{L}$ que selecciona cada elemento de a $\mathcal{L}$ con probabilidad proporcional a su peso: $$\Pr_\mathcal{D}[x] = \frac{w(x)}{\sum_{y\in\mathcal{L}}w(y)}$$

Me gustaría (aproximadamente) de la muestra a partir de esta distribución de manera eficiente, donde de manera eficiente los medios en tiempo polinomial en n, la dimensión del espacio. El algoritmo puede consultar la función peso $w$ un polinomio número de veces. En general, esto es duro, pero conozco a dos hechos adicionales acerca de la función de ponderación que sospecho que el problema manejable.

1) El peso de la función es convexa: en particular, para cualquier C, el conjunto de puntos con el peso mínimo de C se encuentra en el interior de algunos convexo polytope.

2) El peso de la función de Lipschitz: para cualquier $x,y \in \mathcal{L} : ||x-y||_1 \leq 1$, $|w(x) - w(y)| \leq$ poli(n).

Hay un método conocido que permitiría muestreo eficiente de esta distribución?

Answer 1

Es su peso convexo o cóncavo? Su propiedad 1) es auto-contradictoria.

En el cóncavo caso, usted puede tomar un uniforme, polinomio tamaño de la muestra a partir de su simple y seleccione su punto de esta selección basado en la actual pesos.

En el caso convexo, el mismo algoritmo funciona si el promedio de $w$ es comparable a la máxima (ambos pueden ser obtenidos en el polinomio tiempo tomando una muestra uniforme y locales descenso respectivamente). Si ese no es el caso, entonces usted puede probar la misma propiedad para la proyección de $w$ sobre una de las facetas de la $\mathcal L$. Si esta proyección tiene la propiedad requerida, se muestra de esa faceta de acuerdo a las proyecciones de peso y, a continuación, muestra a partir de la fibra sobre el punto seleccionado de acuerdo a $w$ si la propiedad aún no se sostiene, toma un $n-2$ dimensiones de la cara, etc. Al llegar a los vértices, ya sabes que $w$ se concentra alrededor de los vértices de $\mathcal L$ y se pueden encontrar barrios de ellos con casi todo el peso y que tiene la propiedad de que la media de $w$ ser comparable con el máximo de $w$ dentro de estos barrios (elija la totalidad de la $L$ y repetidamente reducir por un factor de $1-\frac{1}{poly}$ y la prueba de la condición). De los barrios, elegir uno de acuerdo a su peso total, y dentro de el elegido, tomar un polinomio de tamaño uniforme de la muestra y la muestra de acuerdo a $w$ desde dentro de ella.

Answer 2

Sí, solo hay una función de peso w.