提出高效采样算法，统一处理凸与星形体的均匀采样问题。
The Geometry of Efficient Nonconvex Sampling
- 基于等周条件与体积增长性设计采样算法
- 复杂度多项式依赖维度与几何常数
- 适合需高效均匀采样的高维几何计算场景
我们提出一种高效算法，可在暖启动条件下，从任意紧致集 $\mathcal{X} \subset \mathbb{R}^n$ 中进行均匀采样，前提是满足等周条件和自然的体积增长条件。该结果显著推广了已知的凸体与星形体采样结果。算法复杂度在维度、$\mathcal{X}$ 上均匀分布的庞加莱常数以及集合的体积增长常数上均为多项式关系。
原文摘要 · Abstract (English)
We present an efficient algorithm for uniformly sampling from an arbitrary compact body $\mathcal{X} \subset \mathbb{R}^n$ from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on $\mathcal{X}$ and the volume growth constant of the set $\mathcal{X}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。