Stochastic Billiards for Sampling from the Boundary of a Convex Set
作者： A. B. Dieker , Santosh S. Vempala
关键词: Discrete mathematics 、 Markov chain Monte Carlo 、 Markov chain 、 Coupling from the past 、 Mathematics 、 Boundary (topology) 、 Convex set 、 Applied mathematics 、 Slice sampling 、 Markov chain mixing time 、 Markov property
摘要: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through Markov Chain Monte Carlo paradigm. This paper studies how many steps underlying chain are required to get samples (approximately) uniform distribution on set, sets with an upper bound curvature boundary. Our main theorem implies polynomial-time algorithm such sets.
arxiv.org
columbia.edu 
sci-hub.se 参考文章(24)
Shing-Tung Yau, Isoperimetric constants and the first eigenvalue of a compact riemannian manifold Annales Scientifiques De L Ecole Normale Superieure. ,vol. 8, pp. 487- 507 ,(1975) , 10.24033/ASENS.1299
Persi Diaconis, Susan Holmes, Mehrdad Shahshahani, Sampling From A Manifold arXiv: Statistics Theory. pp. 102- 125 ,(2013) , 10.1214/12-IMSCOLL1006
Hariharan Narayanan, Partha Niyogi, Sampling Hypersurfaces through Diffusion international workshop and international workshop on approximation randomization and combinatorial optimization algorithms and techniques. pp. 535- 548 ,(2008) , 10.1007/978-3-540-85363-3_42
Mikhail Belkin, Hariharan Narayanan, Partha Niyogi, Heat flow and a faster algorithm to compute the surface area of a convex body Random Structures & Algorithms. ,vol. 43, pp. 407- 428 ,(2013) , 10.1002/RSA.20513
Santosh Vempala, Geometric Random Walks: a Survey Combinatorial and Computational Geometry, 2007, ISBN 0-521-84862-8, págs. 577-616. pp. 577- 616 ,(2007)
Steven N. Evans, Stochastic billiards on general tables Annals of Applied Probability. ,vol. 11, pp. 419- 437 ,(2001) , 10.1214/AOAP/1015345298
Laszlo Lovasz, Santosh Vempala, Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization foundations of computer science. pp. 57- 68 ,(2006) , 10.1109/FOCS.2006.28
Martin Dyer, Peter Gritzmann, Alexander Hufnagel, On The Complexity of Computing Mixed Volumes SIAM Journal on Computing. ,vol. 27, pp. 356- 400 ,(1998) , 10.1137/S0097539794278384
Martin Dyer, Alan Frieze, Ravi Kannan, A random polynomial time algorithm for approximating the volume of convex bodies Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 375- 381 ,(1989) , 10.1145/73007.73043
Francis Comets, Serguei Popov, Gunter M. Schütz, Marina Vachkovskaia, Billiards in a General Domain with Random Reflections Archive for Rational Mechanics and Analysis. ,vol. 191, pp. 497- 537 ,(2009) , 10.1007/S00205-008-0120-X