Abstract
We are interested in efficient algorithms for generating random samples from geometric objects such as Riemannian manifolds. As a step in this direction, we consider the problem of generating random samples from smooth hypersurfaces that may be represented as the boundary \(\partial A\) of a domain A ⊂ ℝd of Euclidean space. A is specified through a membership oracle and we assume access to a blackbox that can generate uniform random samples from A. By simulating a diffusion process with a suitably chosen time constant t, we are able to construct algorithms that can generate points (approximately) on \(\partial A\) according to a (approximately) uniform distribution.
We have two classes of related but distinct results. First, we consider A to be a convex body whose boundary is the union of finitely many smooth pieces, and provide an algorithm (Csample) that generates (almost) uniformly random points from the surface of this body, and prove that its complexity is \(O^*(\frac{d^4}{\epsilon})\) per sample, where ε is the variation distance. Next, we consider A to be a potentially non-convex body whose boundary is a smooth (co-dimension one) manifold with a bound on its absolute curvature and diameter. We provide an algorithm (Msample) that generates almost uniformly random points from \(\partial A\), and prove that its complexity is \(O(\frac{R}{\sqrt{\epsilon}\tau})\) where \(\frac{1}{\tau}\) is a bound on the curvature of \(\partial A\), and R is the radius of a circumscribed ball.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ball, K.: An Elementary Introduction to Modern Convex Geometry. Mathematical Sciences Research Institute Publications, vol. 31, pp. 1–58. Cambridge Univ. Press, Cambridge (1997)
Borell, C.: The Brunn-Minkowski inequality in Gauss space. Inventiones Math. 30, 205–216 (1975)
Belkin, M., Narayanan, H., Niyogi, P.: Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. In: Proc. of the 44th IEEE Foundations of Computer Science (FOCS 2006) (2006)
Bertsimas, D., Vempala, S.: Solving convex programs by random walks. Journal of the ACM (JACM) 51(4), 540–556 (2004); Proc. of the 34th ACM Symposium on the Theory of Computing (STOC 2002), Montreal (2002)
Coifman, R.R., Lafon, S.: “Diffusion maps”. Applied and Computational Harmonic Analysis: Special issue on Diffusion Maps and Wavelets 21, 5–30 (2006)
Diaconis, P.: Generating random points on a Manifold, Berkeley Probability Seminar (Talk based on joint work with S. Holmes and M. Shahshahani)
Diaconis, P.: Personal Communication
Dyer, M., Frieze, A., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex sets. Journal of the Association for Computing Machinary 38, 1–17 (1991)
Lovász, L., Vempala, S.: Hit-and-run from a corner. In: Proc. of the 36th ACM Symposium on the Theory of Computing, Chicago (2004)
Lovász, L., Vempala, S.: Simulated annealing in convex bodies and an O *(n 4) volume algorithm. In: Proc. of the 44th IEEE Foundations of Computer Science (FOCS 2003), Boston (2003)
Matthews, P.: Mixing Rates for Brownian Motion in a Convex Polyhedron. Journal of Applied Probability 27(2), 259–268 (1990)
Matthews, P.: Covering Problems for Brownian Motion on Spheres. Annals of Probability 16(1), 189–199 (1988)
Kaczynski, T., Mischaikov, K., Mrozek, M.: Computational Homology. Springer, New York (2004); (Applied Math. Sci. 157)
Niyogi, P., Weinberger, S., Smale, S.: Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete and Computational Geometry (2004)
Pan, V.Y., Chen, Z., Zheng, A.: The Complexity of the Algebraic Eigenproblem. Mathematical Sciences Research Institute, Berkeley (1998) (MSRI Preprint, 1998-71)
Rudelson, M.: Random vectors in the isotropic position. J. of Functional Analysis 164(1), 60–72 (1999); Encyclopedia of Mathematics and its Applications. Cambridge University Press (1993)
Vempala, S.: Personal Communication
Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete and Computational Geometry 33(2), 247 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Narayanan, H., Niyogi, P. (2008). Sampling Hypersurfaces through Diffusion. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_42
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.