Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

2009/04/03 by Karthekeyan Chandrasekaran, Daniel Dadush, Chandrasekaran, Karthekeyan +3 · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Probability (math.PR) #cs.DS #math.FA #math.PR

paper · pdf · doi:10.48550/arxiv.0904.0583

arxiv created 2009/04/03 · arxiv updated 2009/12/01

Abstract

Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard.

Cited by

• Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates

Related

• The Geometry of Efficient Nonconvex Sampling
• Thin shell implies spectral gap up to polylog via a stochastic localization scheme
• Isoperimetric inequalities in high-dimensional convex sets
• Isoperimetric inequalities in unbounded convex bodies
• A sharp quantitative version of Hales' isoperimetric honeycomb theorem