×

Stochastic billiards for sampling from the boundary of a convex set. (English) Zbl 1331.60152

Summary: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov chain Monte Carlo paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.

MSC:

60J22 Computational methods in Markov chains
65C05 Monte Carlo methods
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Applegate D, Kannan R (1991) Sampling and integration of near log-concave functions. STOC ’91: Proc. Twenty-Third Annual ACM Sympos. Theory Comput. (ACM, New York), 156-163. CrossRef
[2] Bárány I, Füredi Z (1987) Computing the volume is difficult. Discrete Comput. Geom. 2:319-326. CrossRef · Zbl 0628.68041
[3] Belkin M, Narayanan H, Niyogi P (2013) Heat flow and a faster algorithm to compute the surface area of a convex body. Random Structures Algorithms 43(4):407-428. CrossRef · Zbl 1277.68295
[4] Boender CGE, Caron RJ, Rinnooy Kan AHG, Romeijn HE, Smith RL, Telgen J, Vorst ACF (1991) Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra. Oper. Res. 39(6):945-954. Link · Zbl 0800.68969
[5] Boneh A, Golan A (1979) Constraints’ redundancy and feasible region boundedness by random feasible point generator (RFPG). Third Eur. Congress Oper. Res. (EURO III), Amsterdam.
[6] Comets F, Popov S, Schütz GM, Vachkovskaia M (2009) Billiards in a general domain with random reflections. Arch. Ration. Mech. Anal. 191:497-537. CrossRef · Zbl 1186.37049
[7] Cousins B, Vempala S (2013) A cubic algorithm for computing Gaussian volumes. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1215-1228. CrossRef
[8] Diaconis P, Holmes S, Shahshahani M (2013) Sampling from a manifold. Collections, Vol. 10 (Institute of Mathematical Statistics, Beachwood, OH), 102-125. CrossRef · Zbl 1356.62015
[9] Dieker AB, Kim S-H (2014) A high-dimensional ellipsoid-based method for ranking and selection. Preprint.
[10] Dyer M, Gritzmann P, Hufnagel A (1998) On the complexity of computing mixed volumes. SIAM J. Comput. 27:356-400. CrossRef · Zbl 0909.68193
[11] Dyer ME, Frieze AM, Kannan R (1989) A random polynomial time algorithm for approximating the volume of convex bodies. Proc. 21st ACM Sympos. Theory Comput. STOC ’89 (ACM, New York), 375-381. CrossRef
[12] Evans SN (2001) Stochastic billiards on general tables. Ann. Appl. Probab. 11(2):419-437. CrossRef · Zbl 1015.60058
[13] Lalley S, Robbins H (1988) Stochastic search in a convex region. Probab. Theory Related Fields 77(1):99-116. CrossRef · Zbl 0617.60086
[14] Lovász L (1998) Hit-and-run mixes fast. Math. Prog 86:443-461. · Zbl 0946.90116
[15] Lovász L, Simonovits M (1993) Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms 4:359-412. CrossRef · Zbl 0788.60087
[16] Lovász L, Vempala S (2006) Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. FOCS ’06 (IEEE Computer Society, Washington, DC), 57-68. CrossRef
[17] Lovász L, Vempala S (2006) Hit-and-run from a corner. SIAM J. Comput. 35:985-1005. CrossRef · Zbl 1103.52002
[18] Lovász L, Vempala S (2006) Simulated annealing in convex bodies and an O^{*}(n^{4}) volume algorithm. J. Comput. Syst. Sci. 72(2): 392-417. CrossRef · Zbl 1090.68112
[19] Milman E (2011) Isoperimetric bounds on convex manifolds. Houdré C, Ledoux M, Milman E, Milman M, eds. Concentration, Functional Inequalities and Isoperimetry, Contemporary Mathematics, Vol. 545 (AMS, Providence, RI), 195-208. CrossRef · Zbl 1229.60021
[20] Narayanan H, Niyogi P (2008) Sampling hypersurfaces through diffusion. Approximation, Randomization and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 5171 (Springer, Berlin), 535-548. CrossRef · Zbl 1159.68647
[21] Romeijn HE (1991) Shake-and-bake algorithms for the identification of nonredundant linear inequalities. Statist. Neerlandica 45:31-50. CrossRef · Zbl 0806.65058
[22] Romeijn HE (1998) A general framework for approximate sampling with an application to generating points on the boundary of bounded convex regions. Statist. Neerlandica 52:42-59. CrossRef · Zbl 0961.60503
[23] Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32:1296-1308. Link · Zbl 0552.65004
[24] Vempala S (2005) Geometric random walks: A survey. MSRI Combin. Computational Geometry 52:573-612. · Zbl 1106.52002
[25] Yau ST (1975) Isoperimetric constants and the first eigenvalue of a compact Riemannian manifold. Ann. Sci. École Norm. 8(4):487-507. · Zbl 0325.53039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.