Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
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 32 references indexed in Scilit:
- Polynomial degree bounds for matrix semi-invariantsAdvances in Mathematics, 2017
- Some nonlinear Brascamp–Lieb inequalities and applications to harmonic analysisJournal of Functional Analysis, 2010
- Nonnegative tensor factorization as an alternative Csiszar–Tusnady procedure: algorithms, convergence, probabilistic interpretations and novel probabilistic tensor latent variable analysis algorithmsData Mining and Knowledge Discovery, 2010
- Subadditivity of The Entropy and its Relation to Brascamp–Lieb Type InequalitiesGeometric and Functional Analysis, 2009
- 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
- On a reverse form of the Brascamp-Lieb inequalityInventiones Mathematicae, 1998
- Completely positive linear maps on complex matricesLinear Algebra and its Applications, 1975