on KLS localization lemma

Overview

The Localization Lemma, introduced by Kannan, Lovász, and Simonovits (Kannan, Lovász & Simonovits, 1995), is a transformative dimension-reduction technique in high-dimensional geometry. It allows one to prove $n$-dimensional integral inequalities involving log-concave functions by reducing them to 1-dimensional “needles.” This post provides a rigorous derivation of the bisection method, details the convergence to $\delta$-needles using a dense subspace sequence, and discusses the sharp Payne-Weinberger constant for convex domains (Payne & Weinberger, 1960).

🏷️ Foundational Statement

The power of the lemma lies in its ability to preserve the “global” integral constraints of a measure while collapsing its support onto a one-dimensional segment.

Localization Lemma (Integral Version)

Let $\Omega \subset {\mathbb{R}}^n$ be a bounded open convex set. Let $f,g:\Omega \to \mathbb{R}$ be integrable continuous functions such that:

$${\int }_{\Omega }f(x)dx>0\text{and}{\int }_{\Omega }g(x)dx=0$$

Then there exists a line segment (needle) $\Delta \subset \Omega$ and a positive affine function $\ell :\Delta \to \mathbb{R}$ such that:

$${\int }_{\Delta }f(x)\ell (x{)}^{n-1}dx>0\text{and}{\int }_{\Delta }g(x)\ell (x{)}^{n-1}dx=0$$

The geometric weight $\ell (x{)}^{n-1}$ arises from the disintegration of Lebesgue measure. Intuitively, $\ell (x)$ represents the “width” of the convex set along the needle, and its power $n-1$ accounts for the $(n-1)$-dimensional volume of the cross-sections that are being averaged out.

🏷️ Rigorous Derivation of the Bisection Method

The derivation follows a three-stage analytic process: establishing the existence of a single bisection, constructing a refining partition, and analyzing the geometric limit.

Stage 1: Topological Foundation

The core of the recursive step is the Topological Bisection Lemma, which ensures we can always split a measure while preserving a zero-integral constraint.

Lemma: Subspace-based Bisection

Let $E_0\subset {\mathbb{R}}^n$ be an affine subspace of dimension $n-2$. For any continuous and integrable function $g$ on a convex set $K$ such that ${\int }_{K}gdx=0$, there exists a hyperplane $H$ containing $E_0$ that partitions $K$ into two convex sets $K^{+}$ and $K^{-}$ such that:

$${\int }_{K^{+}}gdx={\int }_{K^{-}}gdx=0$$

Proof: The Bisection Step

We consider the subspace $E_0^{\perp }\cong {\mathbb{R}}^2$ orthogonal to $E_0$. Any hyperplane $H$ containing $E_0$ is uniquely determined by its intersection with $E_0^{\perp }$, which forms a line through the origin in ${\mathbb{R}}^2$. We parameterize these hyperplanes by unit vectors $\theta \in S^1\subset E_0^{\perp }$.

Let $H(\theta )$ be the hyperplane through $E_0$ with normal $\theta$, and $H(\theta {)}^{+}$ be the corresponding half-space. Define the integral map:

$$\Phi (\theta )={\int }_{K\cap H(\theta {)}^{+}}g(x)dx$$

1. Continuity: The map $\Phi (\theta )$ is continuous. Small rotations of $\theta$ lead to small changes in the volume of $K\cap H(\theta {)}^{+}$, and since $g$ is continuous and integrable, the integral changes continuously (Dominated Convergence Theorem).
2. Oddness: Rotating the hyperplane by $\pi$ radians ($180^{\circ }$) simply flips the half-space: $H(\theta +\pi {)}^{+}={\mathbb{R}}^n\setminus H(\theta {)}^{+}$ (up to a set of measure zero). Since the total integral ${\int }_{K}g=0$, we have ${\int }_{H(\theta +\pi {)}^{+}}g={\int }_{K}g-{\int }_{H(\theta {)}^{+}}g=-\Phi (\theta )$.
3. The Root: By the Intermediate Value Theorem, any continuous odd function on a circle must have at least one root. Thus, there exists some ${\theta }_0$ such that $\Phi ({\theta }_0)=0$. This ${\theta }_0$ defines the hyperplane $H$ that bisects $K$ into two pieces $K^{+}$ and $K^{-}$, both satisfying the constraint.

Stage 2: Finite Partitioning and the Piercing Argument

To ensure the pieces converge to 1D segments (needles), we must bisect in “enough” directions. This requires selecting subspaces from the Affine Grassmannian $A{G}_{n,n-2}$, the manifold of all $(n-2)$-dimensional affine subspaces in ${\mathbb{R}}^n$.

1. Selection: We choose a sequence $\{E_i{\}}_{i=1}^{\infty }$ that is dense in $A{G}_{n,n-2}$.
2. The Piercing Concept: A convex set is “thin” if it does not contain any large 2D discs. Because our sequence of subspaces is dense, any disc $D\subset K$ of radius $\delta /10$ will eventually be “pierced” (intersected) by some $E_i$.
3. Compactness: Since the set of all such discs in $K$ is compact, a finite number of subspaces $\{E_1,\dots ,E_N\}$ is sufficient to pierce every possible disc of radius $\delta /10$ in $K$.
4. Partitioning: We perform $N$ recursive bisections using hyperplanes containing these $E_i$. This generates a partition of $K$ into $2^N$ convex bodies $K_1,\dots ,K_{2^N}$.

graph TD
    K["K: ∫g=0, ∫f>0"] --> K_p["K+: ∫g=0, ∫f_p"]
    K --> K_m["K-: ∫g=0, ∫f_m"]
    K_p --> K_p1["K1: ∫g=0"]
    K_p --> K_p2["K2: ∫g=0"]
    K_m --> K_m1["K3: ∫g=0"]
    K_m --> K_m2["K4: ∫g=0"]
    style K stroke:#f66,stroke-width:2px
    style K_p stroke:#6f6

By construction, none of the resulting $K_j$ can contain a 2D disc of radius $\delta /10$ (as the dense subspaces would have already split it). This forcing of “flatness” in $n-1$ directions ensures each $K_j$ is a $\delta$-needle: it lies within a $\delta$-neighborhood of some line $\ell$.

Stage 3: The Geometric Limit and Affine Weight

As $\delta \to 0$, the partition refines, and we consider the sequence of pieces $K_m$ that satisfy our target inequality (e.g., ${\int }_{K_m}f>0$). These pieces converge to a line segment $\Delta$.

The measure on $K$ is log-concave, and by the Brunn-Minkowski theorem, the function $w(x)={\text{vol}}_{n-1}(K\cap (x+L^{\perp }))$, which measures the $(n-1)$-dimensional “thickness” along the needle, has the property that $w^{1/(n-1)}$ is concave. In the limit of infinite bisections with hyperplanes passing through a dense set of subspaces, this concavity collapses into an affine function $\ell (x)$. Thus, the disintegrated measure on the segment $\Delta$ becomes:

$$d\nu =\ell (x{)}^{n-1}{e}^{-\psi (x)}dx$$

where $e^{-\psi }$ is the original log-concave density. This establishes a 1D reduction that is consistent with the treatment of singular points in on boundary integral with stationary phase.

🏷️ When and How to Use

Applying the localization lemma effectively requires transforming a high-dimensional integral problem into a specific form that allows for bisection.

When to Use

Localization is the tool of choice when:

• Dimension-Independent Constants: You are seeking a bound (e.g., a spectral gap or isoperimetric constant) that should not depend on the dimension $n$.
• Convexity and Log-Concavity: The underlying domain is convex and the measure is log-concave, as these properties are required to ensure the 1D limit measure has a tractable affine-weighted density.
• Isoperimetric Problems: You need to bound the “surface area” of a partition of a convex set.

How to Use: A Systematic Workflow

1. Formulate the Integral Inequality: Frame the objective as an implication: “If ${\int }_{K}f>0$ and ${\int }_{K}g=0$, then (a certain goal).” For instance, to prove $\mathbb{E}{f}^2\le C\mathbb{E}|\nabla f{|}^2$, one might set $g=f$ (assuming $\int f=0$).
2. Choose the Bisection Mode:
   • Monotone Selection (Single Needle): Use this for existence proofs. If you only need to find one subset where a condition holds, simply follow the “winning” half of each bisection.
   • Full Tree (Needle Decomposition): Use this for global inequalities. Bisect every piece in the partition until they are all $\delta$-needles. This is necessary for bounds like Reverse Hölder or Poincaré, where the inequality must hold across the entire measure.
3. Solve the 1D Problem: The complexity shifts from geometry to analysis. On the needle $\Delta$, you must prove the target inequality for the 1D measure $d\nu =\ell (x{)}^{n-1}{e}^{-\psi (x)}dx$. This often reduces to solving a 1D differential equation or using properties of log-concave functions on intervals.
4. Integrate back to ${\mathbb{R}}^n$: Since the inequality holds on every needle in the partition, sum the integrals across all pieces $K_j$ and take the limit as $\delta \to 0$ to recover the global $n$-dimensional result.

🏷️ Functional Inequalities and Optimal Constants

Localization is used to lift inequalities like Poincaré from 1D to $n$ dimensions.

The Payne-Weinberger Theorem

One of the most celebrated results facilitated by localization is the sharp bound on the Poincaré constant for convex domains. Localization reduces the $n$-dimensional Poincaré inequality to a 1D problem on a segment $\Delta$ with density $\ell (x{)}^{n-1}$. Solving the 1D eigenvalue problem for the Laplacian with this weight yields the sharp Payne-Weinberger constant:

$${\lambda }_1(K)\ge \frac{{\pi }^2}{{\text{diam}}^2(K)}$$

This bound is independent of $n$, proving that convexity alone is sufficient to guarantee spectral gaps that do not vanish as the dimension increases. This spectral gap is critical for the stability results discussed in on concentration of information and log-concave distributions.

🔗 See Also

• on concentration of information and log-concave distributions --- Provides a major application of the Localization Lemma in information theory, where the spectral gap ensures rapid convergence of entropy.
• on eigenvalue estimate of kernel --- Localization is often used to bound the first non-trivial eigenvalue of operators on convex domains via 1D reduction.
• on improved Nyström bounds --- Discusses dimension-reduction in kernel methods, which shares conceptual roots with the geometric bisection strategy of localization.
• on boundary integral with stationary phase --- The disintegration of measures onto needles mirrors the analysis of oscillatory integrals along critical trajectories.

📚 References

🐻  Kannan, R., Lovász, L. & Simonovits, M. 1995. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry 13(3), 541–559.

🐻  Payne, L.E. & Weinberger, H.F. 1960. An optimal Poincaré inequality for convex domains. Archive for Rational Mechanics and Analysis 5(1), 286–292.