Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling

1.1 The Brascamp-Lieb inequalities: basic notions

• A BL datum pairs linear maps with nonnegative exponents; Barthe’s reverse form has corresponding feasibility and constant questions, and its optimal constant is determined by the BL constant.The introduction also situates BL inequalities as encompassing familiar inequalities including Hölder’s and Loomis–Whitney’s.Source: §1.1 · pp. 3–4

1.2 The Brascamp-Lieb inequalities: known and new results

• In time poly(b, d), the algorithm tests membership in the BL polytope and, when infeasible, returns a violated dimension inequality.The witness is a basis for a subspace V with dim(V) > Σ_j p_j dim(B_jV).Source: §1.2 · p. 5
• For feasible data, BL(B, p) ≤ exp(O(b log(bd))), and a poly(b, d, 1/ε)-time algorithm computes a (1 + ε)-approximation.The algorithm also outputs a scaling B′ with BL(B′, p) ≤ 1 + ε.Source: §1.2 · p. 6

1.3 Efficient computation of the BL-constant via scaling

• Every geometric BL datum has BL-constant 1, while an isotropy- or projection-normalized datum has BL-constant at least 1.For feasible data, the scaling analysis also gives the upper bound exp(O(b log(bd))).Source: §1.3 · pp. 7–8
• The BL scaling algorithm alternates between enforcing isotropy and projection, and converges in polynomial time to a geometric datum whenever the input datum is feasible.Each normalization fixes one condition and may disturb the other; the procedure repeats the two steps alternately.Source: §1.3 · pp. 7–8
• BL scaling’s alternating minimization reaches the BL-constant infimum in polynomial time, using the BL constant as a progress potential.The analysis combines commutative invariant theory and non-commutative skew-field theory, as explained in [GGOW16].Source: §1.3 · p. 10
• Smoothness of the scaling algorithm yields explicit quantitative continuity bounds for BL constants, beyond prior qualitative results whose proofs use compactness.The reduction transfers the algorithm’s quantitative continuity analysis to BL data; the passage introducing Theorem 1.12 does not provide the bound’s formula.Source: §1.3 · pp. 10–11

1.4 Applications of Brascamp-Lieb in Computer Science, Optimization and Beyond

• Rank-2 BL polytopes encode linear matroid intersection polytopes, including bipartite matching polytopes, while general linear matroid matching remains an open encoding question.The authors note that this BL encoding uses rank-2 projectors, unlike Gurvits’ rank-1 operator-scaling encoding, and say the relative power of the formulations by rank is unclear.Source: §1.4 · p. 12
• [LS17] gives Sum-of-Squares feasibility testing exponential in d, whereas the paper’s algorithms depend polynomially on d.The passage presents this contrast as motivating questions about connections between operator scaling and Sum-of-Squares algorithms.Source: §1.4 · p. 13

• Completely positive operators are represented using Kraus matrices, and an operator is doubly stochastic when both it and its dual preserve the identity.Source: §2 · p. 14
• Capacity is introduced as a complexity measure for completely positive operators and is related to Brascamp-Lieb constants for a special subset.Source: §2 · p. 14
• Alternating right and left normalizations forms Algorithm G, which seeks a doubly stochastic scaling; positive capacity guarantees a scaling within distance ε of doubly stochastic.Source: §2 · p. 15
• A square completely positive operator is rank non-decreasing exactly when its capacity is positive.Source: §2 · p. 15
• Polynomial-time algorithms test rank non-decrease and approximate capacity, while outputting an almost doubly stochastic scaling; a separate algorithm can produce a rank-decrease witness.Source: §2 · p. 16

• Rectangular completely positive operators are linear maps between matrix spaces represented using rectangular Kraus matrices.Source: §3 · p. 16
• The block construction embeds a rectangular operator into a square one, with cap(eT) = cap(T)^n1 and fractional-rank non-decrease equivalent to rank non-decrease of eT.Source: §3 · p. 18
• A rectangular completely positive operator is fractional-rank non-decreasing exactly when its capacity is positive.Source: §3 · p. 20
• Positive capacity is also equivalent to the adjoint being fractional-rank non-decreasing.Source: §3 · p. 21
• When a rectangular operator has positive capacity, Algorithm 3 can find a scaling within ε of doubly stochastic.Source: §3 · p. 21
• Deterministic polynomial-time algorithms test fractional-rank non-decrease, approximate capacity, and output an almost doubly stochastic scaling; a square-operator witness algorithm also transfers to the rectangular case.Source: §3 · p. 22

4 Reduction from Brascamp-Lieb to completely positive operators

• For each Brascamp-Lieb datum (B, p), the corresponding operator T(B,p) has capacity cap(T(B,p)) = 1/BL(B, p)^2; this correspondence and capacity’s connection to rank expansion yield the finiteness conditions.Source: §4 · p. 22
• The reduction builds operator matrices from copies of each B_i acting on different parts of the space, yielding a fractional-rank non-decreasing operator when the datum satisfies the stated dimension condition.For integer B_i, the constructed matrices are also integer and preserve the entry bound.Source: §4 · pp. 23–24
• BL(B, p) is finite exactly when every subspace V satisfies the stated dimension inequality.This recovers the finiteness characterization associated with.Source: §4 · p. 25
• A deterministic poly(b, d)-time algorithm tests finiteness and, when it fails, outputs a subspace violating the dimension inequalities.The violating subspace is obtained from the image of a positive semidefinite matrix produced by the operator test.Source: §4 · pp. 25–26

4.1 Connection to quiver semi-invariants

• The reduction can be viewed as a special case of reducing star-quiver semi-invariants to the Kronecker quiver; infeasibility corresponds to vanishing on the datum.Figure 1 labels nodes by dimension and weight and edges by maps from head to tail.Source: §4.1 · pp. 26–27, Figure 1 · p. 27

5 Upper bound on the Brascamp-Lieb constant

• BL(B, p) ≤ exp(4n log(n^2d)) for integer matrices and exponents p_i = c_i/d, when the BL constant is finite.This bound is independent of the magnitude of the integer matrix entries.Source: §5 · p. 28
• BL(B, p) ≤ exp(12nm log(mn)) for integer matrices and arbitrary positive real exponents, when the BL constant is finite.The bound is independent of the common denominator d.Source: §5 · p. 28
• BL(B, p) ≤ exp(4n log(n^2d) + neb) for rational matrices with entry bit-size at most eb and exponents p_i = c_i/d.The rational-matrix bound follows by scaling the matrices to integers.Source: §5 · pp. 28–29
• Eliminating d from the rational-matrix bound is possible, but the exponential bound then becomes quadratic.The integer-exponent argument uses convexity in p and bounds the common denominator of BL-polytope vertices by m! · nm.Source: §5 · pp. 28–29

6 Computing the Brascamp-Lieb constant

• Algorithm eG computes BL(B, p) within a multiplicative factor of (1 ± ǫ) in time poly(n, d, log M, 1/ǫ).The input has integer matrices with entries bounded in absolute value by M and exponents p_i = c_i/d.Source: §6 · p. 29
• The reduction gives BL(B, p) = (1/cap(eT(B,p)))^(1/2nd), so approximating the transformed operator's capacity yields an approximation to the BL constant.The transformed operator is constructed from the Brascamp-Lieb operator, and capacity is approximated using Algorithm G.Source: §6 · p. 29
• An estimate α in [(1 − ǫ) cap(eT(B,p)), cap(eT(B,p))] yields a BL estimate in [BL(B, p), (1 + ǫ)BL(B, p)].Algorithm G approximates capacity within a multiplicative factor of 1 ± ǫ.Source: §6 · p. 29

7 Continuity of the Brascamp-Lieb constant

• For rational exponents, sufficiently small matrix perturbations preserve finiteness of the BL constant and give the stated continuity bound.The perturbation threshold is δ ≤ exp(−P(n, d, b, log(m))), with P polynomial, and the bound is 1 + P(n, d, b, log(m)).Source: §7 · p. 30
• The operator-capacity continuity argument can be extended to irrational inputs, but without explicit bounds.The extension is described through changes to the proof in [GGOW16].Source: §7 · p. 31
• For irrational p, the reduction to operators no longer applies, and the authors do not establish how many algorithm steps suffice for the BL constant to approach 1.The progress-per-step bound depends on the common denominator d, which is unavailable for irrational p.Source: §7 · p. 31

Rank-1 data and basis polytopes

• Rank-1 BL polytopes are exactly basis polytopes, linking this special case to a well-studied combinatorial polytope.The passage attributes this identification to Barthe.Source: §8 · p. 31

Rank-2 data and matroid intersection

• The BL polytope for the constructed rank-2 datum equals the linear matroid intersection polytope, giving a BL encoding of that optimization problem.The authors note that linear matroid intersection was already known to be in P and hope similar encodings could handle other problems with exponentially sized linear programs.Source: §8 · p. 32
• Because perfect bipartite matching polytopes are special cases of linear matroid intersection polytopes, they are also special cases of BL polytopes for rank-2 data.Whether general perfect matching polytopes are BL polytopes remains an open question.Source: §8 · p. 34

Normalization and the BL constant

• For feasible data satisfying the stated normalization conditions, BL(B, p) ≥ 1, with equality iff the datum is geometric.This strengthens the result attributed to.Source: §9 · pp. 34–35
• Either projection-normalization or isotropy-normalization alone suffices for the same lower bound and equality characterization.Source: §9 · p. 35

Proof approach

• The proof strategy extends the operator-scaling argument to irrational exponent vectors rather than relying on a rationality assumption.The authors use an AM-GM consequence for positive semidefinite matrices in the argument.Source: §9 · p. 35

Iteration bound

• The iteration analysis applies in the irrational-exponent case, where the rational case can instead be handled through the operator reduction.The theorem considers feasible data with rational matrix entries and bounded entry bit-size.Source: §10 · pp. 37–38
• The proof bounds the initial BL constant by exp(12nm log(nm) + nb).Source: §10 · p. 38

Effect of normalization steps

• The analysis also uses that projection normalization decreases the BL constant, while a quantitative decrease bound for that step is not needed.Starting normalized is without loss of generality because normalization can be achieved in one extra iteration.Source: §10 · p. 38
• An isotropy-normalization step decreases the BL constant by a factor of exp(−ε/12) under the analyzed condition.The proof tracks the decrease when the current datum is projection-normalized.Source: §10 · p. 38

Contributions

• The reduction to completely positive operators yields polynomial-time algorithms for BL-polytope membership, a violating inequality, and approximation of BL constants.The paper also uses operator-scaling algorithms for rank-decrease testing and capacity computation [GGOW16] [IQS15].Source: §11 · p. 39

Algorithmic open questions

• For exponent entries with common denominator d, the algorithms run in poly(d) time, and improving this dependence to poly(log(d)) remains open.Source: §11 · p. 39
• Approximating BL constants to a (1+ε) factor takes poly(1/ε) time, and improving this to poly(log(1/ε)) is left open.Source: §11 · p. 39
• The weak separation oracle is not known to support efficient linear optimization over BL polytopes.The authors note that their current oracle does not seem strong enough for the general reduction from separation to optimization.Source: §11 · p. 39

Structural open questions

• The operator viewpoint does not extend the Gaussian-density inequalities to arbitrary non-negative densities in full generality, while star-quiver operators correspond to BL inequalities.Whether other quivers yield new inequalities is left as an open question.Source: §11 · p. 39