2020/04/20 by Nima Anari, Michał Dereziński, Anari, Nima +1
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
paper · pdf · doi:10.48550/arxiv.2004.09079
openalex publication_date 2020/04/20 · 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\ndistribution over subsets S of a ground set [n], we say that \μ is in\nisotropic position if P[e \∈ S] is the same for all e\∈ [n]. We design a\nnew approximate sampling algorithm that leverages isotropy for the class of\ndistributions \μ that have a log-concave generating polynomial; this class\nincludes determinantal point processes, strongly Rayleigh distributions, and\nuniform distributions over matroid bases. We show that when \μ is in\napproximately isotropic position, the running time of our algorithm depends\npolynomially on the size of the set S, and only logarithmically on n. When\nn is much larger than the size of S, this is significantly faster than\nprior algorithms, and can even be sublinear in n. We then show how to\ntransform a non-isotropic \μ into an equivalent approximately isotropic form\nwith a polynomial-time preprocessing step, accelerating subsequent sampling\ntimes. The main new ingredient enabling our algorithms is a class of negative\ndependence inequalities that may be of independent interest.\n As an application of our results, we show how to approximately count bases of\na matroid of rank k over a ground set of n elements to within a factor of\n1+\ε in time O((n+1/\ε2)\⋅ poly(k, \log n)). This is the\nfirst algorithm that runs in nearly linear time for fixed rank k, and\nachieves an inverse polynomially low approximation error.\n