Algorithmic aspects of Brascamp-Lieb inequalities
Preprint
Abstract
The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute feasibility of BL-datum, the optimal BL-constant and a weak separation oracle for the BL-polytope. The same result holds for the so-called Reverse BL inequalities of Barthe. The best known algorithms for any of these tasks required at least exponential time. The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors have provided a polynomial time algorithm. This reduction implies algorithmic versions of many of the known structural results, and in some cases provide proofs that are different or simpler than existing ones. Of particular interest is the fact that the operator scaling algorithm is continuous in its input. Thus as a simple corollary of our reduction we obtain explicit bounds on the magnitude and continuity of the BL-constant in terms of the BL-data. To the best of our knowledge no such bounds were known, as past arguments relied on compactness. The continuity of BL-constants is important for developing non-linear BL inequalities that have recently found so many applications.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Polynomial degree bounds for matrix semi-invariantsAdvances in Mathematics, 2017
- A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing2016
- Some nonlinear Brascamp–Lieb inequalities and applications to harmonic analysisJournal of Functional Analysis, 2010
- Volumes of sections of cubes and related problems2006
- Classical complexity and quantum entanglementJournal of Computer and System Sciences, 2004
- Semi-invariants of quivers as determinantsTransformation Groups, 2001
- Semi-invariants of quivers for arbitrary dimension vectorsIndagationes Mathematicae, 2001
- Semi-invariants of quivers and saturation for Littlewood-Richardson coefficientsJournal of the American Mathematical Society, 2000
- On a reverse form of the Brascamp-Lieb inequalityInventiones Mathematicae, 1998
- Completely positive linear maps on complex matricesLinear Algebra and its Applications, 1975