Stochastic billiards for sampling from the boundary of a convex set
作者： A. B. Dieker , Santosh Vempala
DOI:
关键词: Markov chain 、 Curvature 、 Upper and lower bounds 、 Applied mathematics 、 Mathematics 、 Sampling (statistics) 、 Convex set 、 Bounded function 、 Boundary (topology) 、 Markov chain Monte Carlo
摘要: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through Markov Chain Monte Carlo (MCMC) 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
harvard.edu
128.84.21.199参考文章(15)
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
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
C. G. E. Boender, R. J. Caron, J. F. McDonald, A. H. G. Rinnooy Kan, H. E. Romeijn, R. L. Smith, J. Telgen, A. C. F. Vorst, Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra Operations Research. ,vol. 39, pp. 945- 954 ,(1991) , 10.1287/OPRE.39.6.945
Martin Dyer, Alan Frieze, Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies Journal of the ACM. ,vol. 38, pp. 1- 17 ,(1991) , 10.1145/102782.102783
László Lovász, Hit-and-run mixes fast Mathematical Programming. ,vol. 86, pp. 443- 461 ,(1999) , 10.1007/S101070050099
David Applegate, Ravi Kannan, Sampling and integration of near log-concave functions symposium on the theory of computing. pp. 156- 163 ,(1991) , 10.1145/103418.103439