2020/04/20 by Nima Anari, Michał Dereziński, Anari, Nima +1 · 3 citations
Computer Science · Mathematics · #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2004.09079
arxiv created 2020/04/20 · openalex publication_date 2020/04/20 · arxiv updated 2020/04/21 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We define a notion of isotropy for discrete set distributions. If μ is a distribution over subsets S of a ground set [n], we say that μ is in isotropic position if P[e ∈ S] is the same for all e∈ [n]. We design a new approximate sampling algorithm that leverages isotropy for the class of distributions μ that have a log-concave generating polynomial; this class includes determinantal point processes, strongly Rayleigh distributions, and uniform distributions over matroid bases. We show that when μ is in approximately isotropic position, the running time of our algorithm depends polynomially on the size of the set S, and only logarithmically on n. When n is much larger than the size of S, this is significantly faster than prior algorithms, and can even be sublinear in n. We then show how to transform a non-isotropic μ into an equivalent approximately isotropic form with a polynomial-time preprocessing step, accelerating subsequent sampling times. The main new ingredient enabling our algorithms is a class of negative dependence inequalities that may be of independent interest. As an application of our results, we show how to approximately count bases of a matroid of rank k over a ground set of n elements to within a factor of 1+ε in time O((n+1/ε2)⋅ poly(k, log n)). This is the first algorithm that runs in nearly linear time for fixed rank k, and achieves an inverse polynomially low approximation error.