Source-linked AI summary
Improved $\ell_0$-Isoperimetry for Convex Bodies via Mass Transport
Manuel Fernandez
TL;DR
The paper develops improved ℓ0 isoperimetry for convex bodies under unconditional Q-regularity. It uses coordinate-based routing and obtains stronger lower bounds, improved CHAR mixing-time bounds, and complementary upper bounds.
Problem
Existing direct lower bounds were limited to ℓ2 and ℓ∞ regularity, while extending canonical-path reasoning to a continuous Hamming graph presents routing and overlap challenges.
Method
The proof routes labeled volume through coordinate staircases formed by successive coordinate sweeps, while controlling their length and containment in the convex body.
Results
Theorem 1.1 gives a lower-bound scale cr/(n^2R), improving refined ℓ2- and ℓ∞-regularity bounds by a factor of n and adding a log(e/s) small-set gain.
Takeaways & Limitations
The result applies directly to every unconditional Q-regularity class, supports improved CHAR mixing-time bounds, and is complemented by constructions within a factor of n of the lower bound.
Takeaways & Limitations
Theorem 1.1 is conjectured to admit another factor-n improvement, and the intermediate-regime optimality remains unresolved.
Abstract
from arXiv · showhide
We study $\ell_0$ isoperimetry for a convex body $K\subset \mathbb{R}^n$, $n\ge2$. For a Borel set $S\subset K$, let $\partial_0^K S$ be the set of points in $K \setminus S$ that can be reached from $S$ by changing at most one coordinate (i.e. the $\ell_0$ boundary of $S$). Suppose that, for some unconditional convex body $Q \subset \mathbb{R}^n$, numbers $r,R>0$, and possibly different centers $x_0,y_0$, \[ x_0+rQ \subset K\subset y_0+RQ. \] Writing $s=\text{vol}(S)/\text{vol}(K)$, we prove that whenever $0<s \le 1/2$, \[ \frac{\text{vol}(\partial_0^K S)}{\text{vol}(S)} \ge \frac{cr}{nR} \min\left\{1,\frac{\log(e/s)}{n}\right\}, \] where $c > 0$ is an absolute constant. Consequently, the associated $\ell_0$-isoperimetric coefficient is at least $cr/(n^2R)$. Previous direct lower bounds were only known for $\ell_2$ and $\ell_\infty$ regularity whereas our lower bound holds directly for any $Q$-regularity, where $Q$ is an unconditional convex body. Compared to $\ell_2$ and $\ell_\infty$ regularity, our lower bound result improves upon the previously best known lower bounds, for any $s$, by a factor of $n$. As an application of our result, we give improved mixing time bounds for the Coordinate Hit and Run walk (CHAR). Our proof of the lower bound is based on a modification of the method of canonical paths applied to a continuous Hamming graph over our convex body. Our construction of canonical paths can be viewed as a suitable coordinate discretization of certain mass transport maps from $S$ to $S^c$. We also give complementary upper-bounds for any $Q$-regularity, with an overall factor of $n$ gap between the two.
1 Introduction
The paper develops improved ℓ0 isoperimetry for convex bodies with unconditional Q-regularity, applies it to CHAR mixing, and constructs complementary upper bounds. Its lower bound improves prior ℓ2 and ℓ∞ scales by a factor of n, while the upper and lower bounds remain within an overall factor of n in key regimes.
- Definitions: The ℓ0 boundary consists of points outside S reachable by changing at most one coordinate, defining a continuous Hamming-graph boundary measured by volume.The paper studies the associated coefficients ξ0(K) and ψ0(K).
- Lower bound: The lower bound has scale c(r/R)n^-2 for balanced sets and gains a factor log(e/s) as s decreases, saturating at s ≤ e^(1-n).It improves refined Euclidean and ℓ∞ lower bounds by a factor of n and applies to every ℓp regularity class.
- CHAR application: Theorem 1.1 yields improved mixing-time bounds for Coordinate Hit and Run, including effective outer regularity that depends on subset size.The application uses truncation and scale-dependent conductance estimates.
- Upper bounds: Complementary Q-cylinder and Q-cone constructions give upper boundary ratios O(r/(nR)) for constant-sized sets and O(r/R) for exponentially small sets.These constructions require R ≥ Cr and leave an O(n) gap from the lower bounds in the corresponding regimes.
- Proof strategy: The proof modifies canonical paths for a continuous Hamming graph by discretizing mass-transport maps into coordinate staircases with controlled congestion.The construction addresses continuum many vertices and edges and routes positive-volume sets through coordinate boundaries.
2 Notation and preliminaries
This section defines the coordinate-based geometry and isoperimetric quantities, then develops the convex-analytic and transport tools used to prove boundary lower bounds.
- The paper assumes n ≥2 and uses Borel sets throughout, with volume-one normalization for ambient convex bodies in Sections 2 and 3.
- An unconditional convex body is invariant under arbitrary coordinate sign changes, and its Minkowski functional defines the Q-norm.Unconditionality also makes diagonal coordinate contractions and coordinate projections contractions with respect to the Q-norm.
- Q-regularity with parameters (r, R) means that K lies between an inner copy x0 + rQ and an outer copy y0 + RQ, with centers allowed to differ.
- ℓ0 boundary and coefficients: The ℓ0 boundary consists of points outside S sharing all but at most one coordinate with a point of S; coordinate moves are exactly such one-coordinate transitions.The boundary is the exterior vertex boundary of the continuous graph whose edges join points on common coordinate fibers.
- ℓ0 boundary and coefficients: The one-set and separator coefficients quantify boundary or separator volume relative to set volume, and Proposition 2.6 establishes equivalence between their formulations.The separator coefficient is the ℓ0-isoperimetric form coefficient introduced in prior work.
- Transport and routing tools: The first-exit lemma converts coordinate routings from A ⊂ S to K \ S into lower bounds on the ℓ0 boundary when each map has controlled image expansion.Canonical-path motivation is adapted to continuum volume using Borel routing maps and measurable first-exit sets.
3 The lower bound
The lower-bound proof routes mass through dyadic homothetic shells and then from the homothetic core using coordinate staircases derived from transport maps. A shell dichotomy and Brenier transport yield the stated boundary lower bound for small sets.
- 3.1 The lower bound: The radial map doubles shell depth, bijectively sending A_u to A_2u for u < 1/4.This provides the basic shell-to-shell transport used in the dyadic decomposition.
- 3.1 The lower bound: Canonical paths are adapted to the continuous Hamming graph by routing source points through maps whose consecutive images differ in at most one coordinate.The construction uses injective coordinate staircases so boundary crossings can be controlled by volume congestion.
- 3.1 The lower bound: Shell transport either forces mass into the next shell or charges first exits to the ℓ0 boundary, producing the shell reduction.The localized first-exit estimate uses M ≤ CnR/r coordinate steps and the disjointness of selected shell bands.
- 3.2 Brenier transport from the homothetic core: The resulting lower bound is vol(∂_0^K S)/vol(S) ≥ cr/(nR) min{1, log(e/s)/n}, and the associated coefficient is at least cr/(n^2R).The proof combines the shell dichotomy with the core boundary estimate for all Borel S of relative volume at most 1/2.
- 3.2 Brenier transport from the homothetic core: Brenier transport maps core mass into the Q-inner parallel body and discretizes each transport ray into coordinate moves with injective intermediate maps.Equal-volume and unequal-volume constructions handle targets of equal and larger volume, respectively.
4 Upper bounds
The upper-bound constructions use slanted Q-cylinders and Q-cones, analyzed through parametrizations and coordinate-order statistics. These examples establish complementary boundary ratios for constant-sized and exponentially small sets.
- 4 Upper bounds: The paper constructs diagonal Q-cylinders and diagonal Q-cones as complementary examples for upper bounds under Q-regularity.Both constructions are analyzed after normalizing the unconditional body Q to isotropic position.
- 4.1 Cylinders: The cylinder analysis relies on an ordered-coordinate spacing lemma for a typical uniform point in the isotropic section F_Q.A deterministic index with controlled spacing identifies coordinate-separated classes used to construct the boundary estimate.
- 4.1 Cylinders: The cylinder has a constant-sized subset whose relative ℓ0 boundary volume is O(r/(Rn)).Its Q-regularity follows from containment in (L+r)Q and inclusion of an inner copy comparable to rQ.
- 4.2 Cones: The cone analysis partitions points by sign counts and coordinate thresholds, with ordered coordinates determining the relevant parameter intervals.For suitable j and u, these intervals separate the set A_{u,j} from its boundary region M_{u,j}.
- 4.2 Cones: For the cone construction, the boundary-to-set ratio is O(r/L), while the set can be chosen exponentially small through a suitable parameter u.The volume calculation gives a range for vol(A_{u,j})/vol(K), and the regularity verification supplies an inner copy of radius comparable to r.
5 Closing Remarks
The closing remarks identify two open directions: improving the lower bound to the conjectured optimal scale and understanding behavior as inner and outer Q-regularity converge.
- Optimal ℓ0-isoperimetric inequality: The authors conjecture that the lower bound in Theorem 1.1 can improve by an additional factor of n, matching the example in Theorem 1.6.Their attempted coarser coordinate-staircase analysis preserved average compression but could not prevent staircases from leaving the body.
- Optimal ℓ0-isoperimetric inequality: A further local analysis of the transport approach is suggested as necessary for improving the ℓ0 lower bound.The current global analysis already improves earlier local-analysis bounds, but the coarser routing obstacle remains unresolved.
- Further improving ℓ0 isoperimetry for unconditional convex bodies: Theorem 1.6 requires a sufficiently large outer-to-inner regularity ratio, while an axis-aligned cube has ℓ0-isoperimetric coefficient Θ(n^-1/2).This shows that the large-ratio condition cannot simply be removed by setting R=r.
- Further improving ℓ0 isoperimetry for unconditional convex bodies: The worst-case behavior as inner and outer regularity converge remains an open question for Q-regular convex bodies.The cube’s boundary ratio for subsets is at least of order n^-1/2 and grows as subset volume tends to zero.
6 Appendix
The appendix verifies the routing properties used in the lower-bound proof, including coordinate-by-coordinate changes, injectivity, Lipschitz control, and Jacobian lower bounds for radial and Brenier-based maps.
- Shell transport: The shell-routing maps interpolate radially and then update coordinates one at a time, so consecutive maps differ in at most one coordinate.The endpoint maps are the identity and the radial map, while intermediate maps remain injective and Lipschitz.
- Brenier transport: These determinant and injectivity bounds permit the area-formula estimates needed to control volume expansion throughout the routing.The same argument handles the endpoint and intermediate hybrid maps, including the ℓ=0 case by fiberwise analysis.
- Shell transport: The radial interpolation preserves controlled shell depth, with η(y) ≤ 2η(x) along intermediate maps.This localization keeps staircase points within the required shell band.
- Brenier transport: For Brenier transport, the map ∇φ pushes normalized Lebesgue measure on the source set to normalized Lebesgue measure on the target set.Its displacement interpolation is combined with coordinate projections to form the routing maps.
- Brenier transport: Injectivity of coordinate hybrids follows from monotonicity of the Brenier map together with injectivity of the identity and transport maps.A hypothetical collision would contradict the nonnegative monotonicity inner product.