Source-linked AI summary
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
TL;DR
The paper studies rapid mixing for a natural Markov chain on d-homogeneous strongly log-concave distributions. It defines the chain through element deletion and weight-proportional completion, proves a spectral gap of at least 1/d, and uses the framework for counting bases and estimating a random-cluster partition function.
Problem
The paper addresses how to sample efficiently from d-homogeneous strongly log-concave distributions and apply this capability to counting bases and estimating a random-cluster partition function.
Method
The paper analyzes a Markov chain that deletes a uniformly chosen element and completes the set with probability proportional to the distribution weights.
Results
A spectral gap of at least 1/d is proved for the chain Mµ, which mixes rapidly and can generate samples arbitrarily close to µ.
Takeaways & Limitations
The framework supports applications to counting matroid bases and estimating the random-cluster model partition function in a new parameter range.
Takeaways & Limitations
The appropriate generalization of the coefficient-scaling operation to non-multiaffine polynomials is deferred to future work.
Abstract
from arXiv · showhide
We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where $0<q<1$. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if $X$ is a pure simplicial complex with positive weights on its maximal faces, we can associate with $X$ a multiaffine homogeneous polynomial $p_{X}$ such that the eigenvalues of the localized random walks on $X$ correspond to the eigenvalues of the Hessian of derivatives of $p_{X}$.
1 Introduction
The paper proves rapid mixing for a natural chain on homogeneous strongly log-concave distributions, yielding approximation algorithms for matroid counting and partition functions. It also connects simplicial-complex walks with polynomial Hessians and derives spectral expansion and sampling consequences.
- 1 Introduction: The natural MCMC chain on a d-homogeneous strongly log-concave distribution mixes rapidly and samples arbitrarily close to the target distribution.The chain drops a uniformly chosen element and resamples a containing support set proportionally to its weight.
- 1 Introduction: For every 0 ≤ k ≤ d − 1, the transition matrix has at most |X(k)| eigenvalues, while the chain has spectral gap at least 1/d.The corresponding total variation mixing time is bounded for any starting support state and error 0 < ǫ < 1.
- 1 Introduction: The method gives an FPRAS for counting matroid bases from an independent-set oracle, with multiplicative error 1 ± ǫ and success probability at least 1 − δ.The runtime is polynomial in n, r, 1/ǫ, and log(1/δ).
- 1 Introduction: For every matroid, the bases exchange graph has expansion at least 1.This establishes the Mihail–Vazirani expansion conjecture stated in the introduction.
- 1 Introduction: The framework also yields FPRAS results for random-cluster partition functions when 0 < q ≤ 1 and for the Tutte polynomial in the stated region.It consequently supports approximate sampling of random forests and computation of the reliability polynomial.
- 1 Introduction: Pure simplicial complexes with positive maximal-face weights correspond to multiaffine homogeneous polynomials whose derivative Hessians encode localized-walk eigenvalues.Strong log-concavity corresponds to the relevant spectral-gap property, and homogeneous multiaffine strongly log-concave polynomials remain so after coefficient powers α ≤ 1.
2 Preliminaries
The preliminaries establish the polynomial, matrix, Markov-chain, graph-expansion, and matroid terminology used later. They also introduce strong log-concavity and the key spectral tools connecting these objects.
- Polynomial and log-concavity terminology: The paper represents distributions on subsets by multiaffine polynomials and studies strong log-concavity through Hessians and derivatives.Strong log-concavity is used with respect to the all-ones vector unless otherwise specified.
- Linear algebra: A stochastic matrix has nonnegative entries with each row summing to one, while PSD and NSD matrices have respectively nonnegative and nonpositive eigenvalues.The Schur product, Perron-Frobenius, Cauchy interlacing, and congruence lemmas provide the spectral foundations for later arguments.
- Spectral tools: A central spectral principle is that a symmetric matrix with at most one positive eigenvalue retains that property under suitable congruences and PSD transformations.This principle underlies the passage from Hessian properties to random-walk spectral bounds.
- Markov chains and expansion: Reversible Markov chains are self-adjoint under a stationary-distribution-weighted inner product and can be viewed as random walks on weighted undirected graphs.Their second eigenvalue and conductance control mixing through variational and Cheeger-type inequalities.
- Matroids: The basis of a rank-r matroid is an independent set of size r, and matroid rank is the size of a maximal independent subset.These definitions support the later interpretation of Markov-chain states as matroid bases.
3 Walks on Simplicial Complexes
This section defines upper and lower walks on weighted pure simplicial complexes and analyzes their stationarity, reversibility, and spectra. Local spectral expansion yields quantitative bounds on eigenvalues of these high-dimensional walks.
- Walk definitions: Upper and lower walks move between adjacent face dimensions through a weighted bipartite incidence graph.The upper walk chooses a containing higher-dimensional face proportionally to its weight and then deletes a uniformly random element.
- Walk properties: The upper walk is undefined on top-dimensional faces because no higher-dimensional simplex exists.Thus, the construction applies only for face levels k<d.
- Walk properties: The corresponding walks share a stationary distribution proportional to face weights and have stochastic, self-adjoint, PSD transition matrices with matching nonzero eigenvalues.These properties follow by expressing both chains as two-step walks on the same bipartite graph.
- Local spectral expansion: A weighted complex is a λ-local-spectral-expander when every link’s 1-skeleton has second eigenvalue at most λ, equivalently spectral gap at least 1−λ.The definition examines links of all simplices below the top dimension.
- Spectral bounds: For a 0-local-spectral-expander, Theorem 3.3 bounds the number of eigenvalues above successive thresholds for the upper walks.The theorem provides estimates for all eigenvalues, not only the largest nontrivial one.
4 From Strongly Log-Concave Polynomials to Local Spectral Expanders
The paper maps strongly log-concave multiaffine homogeneous polynomials to weighted simplicial complexes whose links are local spectral expanders. This correspondence transfers Hessian spectral information to high-dimensional random walks and matroid basis exchange.
- Polynomial-complex correspondence: A polynomial p=∑S c_Sx_S defines a pure weighted simplicial complex whose maximal faces are the monomials’ supports and whose weights are their coefficients.All lower-dimensional faces are included and weighted inductively.
- Local expansion from Hessians: If p is strongly log-concave, the associated weighted complex is a 0-local-spectral-expander.The proof identifies normalized Hessians of derivatives with random-walk matrices on links and applies the one-positive-eigenvalue property.
- Polynomial-complex correspondence: For every face τ, its induced weight equals (d−k)! times the derivative p_τ evaluated at the all-ones vector.Here p_τ is obtained by differentiating once with respect to every element of τ.
- Mixing consequences: The resulting spectral estimates imply rapid mixing for the natural chain on a d-homogeneous strongly log-concave distribution.The chain’s second-eigenvalue bound is obtained by combining the polynomial-complex correspondence with the local-expansion theorem.
- Matroid application: For a matroid, the weighted walk specializes to the basis exchange graph, and the spectral bound combined with Cheeger’s inequality gives expansion at least 1.The weighted graph’s vertices are matroid bases, while its unweighted version is the usual bases exchange graph.
5 Proof of Strong Log-Concavity and Applications
The section proves strong log-concavity for matroid generating polynomials by translating between polynomial Hessians and simplicial-complex expansion. It applies these results to weighted matroid polynomials, random-cluster-type polynomials, and coefficient scaling.
- Polynomial–complex converse: Oppenheim’s criterion states that connected 1-skeletons of all links imply that a weighted pure simplicial complex is a 0-local-spectral-expander.The paper translates link connectivity and quadratic log-concavity into indecomposability and Hessian conditions for polynomials.
- Polynomial proof: The converse argument uses induction on polynomial degree, normalized Hessians, and connectivity to show that each relevant derivative has at most one positive eigenvalue.The normalized Hessian is stochastic and self-adjoint under a polynomial-induced inner product.
- Matroid generating polynomials: For every external field λ∈R^n, the matroid basis generating polynomial is strongly log-concave.Derivatives correspond to contractions; indecomposability follows from matroid exchange, while rank-two contractions yield the required quadratic Hessian condition.
- Random-cluster application: For 0<q≤1, the random-cluster-type matroid polynomial is strongly log-concave, and it converges coefficient-wise to the bases generating polynomial as q→0.The proof verifies indecomposability and quadratic log-concavity using matroid ranks and parallel classes.