Document Open Access Logo

On Geodesically Convex Formulations for the Brascamp-Lieb Constant

Authors Suvrit Sra, Nisheeth K. Vishnoi, Ozan Yildiz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.25.pdf
  • Filesize: 424 kB
  • 15 pages

Document Identifiers

Author Details

Suvrit Sra
  • Massachusetts Institute of Technology (MIT), Cambridge, MA, USA
Nisheeth K. Vishnoi
  • École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland
Ozan Yildiz
  • École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

Cite As Get BibTex

Suvrit Sra, Nisheeth K. Vishnoi, and Ozan Yildiz. On Geodesically Convex Formulations for the Brascamp-Lieb Constant. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.25

Abstract

We consider two non-convex formulations for computing the optimal constant in the Brascamp-Lieb inequality corresponding to a given datum and show that they are geodesically log-concave on the manifold of positive definite matrices endowed with the Riemannian metric corresponding to the Hessian of the log-determinant function. The first formulation is present in the work of Lieb [Lieb, 1990] and the second is new and inspired by the work of Bennett et al. [Bennett et al., 2008]. Recent work of Garg et al. [Ankit Garg et al., 2017] also implies a geodesically log-concave formulation of the Brascamp-Lieb constant through a reduction to the operator scaling problem. However, the dimension of the arising optimization problem in their reduction depends exponentially on the number of bits needed to describe the Brascamp-Lieb datum. The formulations presented here have dimensions that are polynomial in the bit complexity of the input datum.

Subject Classification

ACM Subject Classification
  • Theory of computation → Nonconvex optimization
  • Theory of computation → Convex optimization
Keywords
  • Geodesic convexity
  • positive definite cone
  • geodesics
  • Brascamp-Lieb constant

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zeyuan Allen-Zhu, Garg Ankit, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, USA, June 25-29, 2018. To appear. URL: http://arxiv.org/abs/arXiv:1804.01076.
  2. Tsuyoshi Ando. Concavity of certain maps on positive definite matrices and applications to Hadamard products. Linear Algebra and its Applications, 26:203-241, 1979. URL: http://dx.doi.org/10.1016/0024-3795(79)90179-4.
  3. Keith Ball. Volumes of sections of cubes and related problems. In Geometric Aspects of Functional Analysis, pages 251-260. Springer, 1989. Google Scholar
  4. Franck Barthe. On a reverse form of the Brascamp-Lieb inequality. Inventiones mathematicae, 134(2):335-361, 1998. Google Scholar
  5. Jonathan Bennett, Anthony Carbery, Michael Christ, and Terence Tao. The Brascamp-Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis, 17(5):1343-1415, 2008. Google Scholar
  6. Rajendra Bhatia. Positive definite matrices. Princeton University Press, 2009. Google Scholar
  7. Herm Jan Brascamp and Elliott H Lieb. Best constants in Young’s inequality, its converse, and its generalization to more than three functions. Advances in Mathematics, 20(2):151-173, 1976. Google Scholar
  8. Eric A Carlen and Dario Cordero-Erausquin. Subadditivity of the entropy and its relation to Brascamp-Lieb type inequalities. Geometric and Functional Analysis, 19(2):373-405, 2009. Google Scholar
  9. Eric A. Carlen, Elliott. H. Lieb, and Michael Loss. A sharp analog of Young’s inequality on SN and related entropy inequalities. The Journal of Geometric Analysis, 14(3):487-520, Sep 2004. URL: http://dx.doi.org/10.1007/BF02922101.
  10. Zeev Dvir, Ankit Garg, Rafael Mendes de Oliveira, and József Solymosi. Rank bounds for design matrices with block entries and geometric applications. Discrete Analysis, 2018:5, Mar 2018. URL: http://dx.doi.org/10.19086/da.3118.
  11. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Breaking the quadratic barrier for 3-LCC’s over the reals. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, USA, May 31- June 3, 2014, pages 784-793, New York, NY, USA, 2014. URL: http://dx.doi.org/10.1145/2591796.2591818.
  12. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada, June 19-23, 2017, pages 397-409, 2017. URL: http://dx.doi.org/10.1145/3055399.3055458.
  13. Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences, 69(3):448-484, 2004. Special Issue on STOC 2003. URL: http://dx.doi.org/10.1016/j.jcss.2004.06.003.
  14. Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory, pages 354-375, 2013. Google Scholar
  15. Elliott H Lieb. Gaussian kernels have only Gaussian maximizers. Inventiones Mathematicae, 102(1):179-208, 1990. Google Scholar
  16. Jingbo Liu, Thomas A. Courtade, Paul W. Cuff, and Sergio Verdú. Smoothing Brascamp-Lieb inequalities and strong converses for common randomness generation. In IEEE International Symposium on Information Theory, Barcelona, Spain, July 10-15, 2016, pages 1043-1047. IEEE, 2016. URL: http://dx.doi.org/10.1109/ISIT.2016.7541458.
  17. Jingbo Liu, Thomas A. Courtade, Paul W. Cuff, and Sergio Verdú. Information-theoretic perspectives on Brascamp-Lieb inequality and its reverse. CoRR, abs/1702.06260, 2017. URL: http://arxiv.org/abs/1702.06260.
  18. Kaare Brandt Petersen, Michael Syskind Pedersen, et al. The matrix cookbook. Technical University of Denmark, 7(15):510, 2008. Google Scholar
  19. W. Pusz and S.L. Woronowicz. Functional calculus for sesquilinear forms and the purification map. Reports on Mathematical Physics, 8(2):159-170, 1975. URL: http://dx.doi.org/10.1016/0034-4877(75)90061-0.
  20. Tamás Rapcsák. Geodesic convex functions, pages 61-86. Springer US, Boston, MA, 1997. URL: http://dx.doi.org/10.1007/978-1-4615-6357-0_6.
  21. Hirohiko Shima. The geometry of Hessian structures. World Scientific Publishing, 2007. Google Scholar
  22. Carl Ludwig Siegel. Symplectic geometry. American Journal of Mathematics, 65(1):1-86, 1943. URL: http://www.jstor.org/stable/2371774.
  23. Mohit Singh and Nisheeth K Vishnoi. Entropy, optimization and counting. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 50-59. ACM, 2014. Google Scholar
  24. Suvrit Sra and Reshad Hosseini. Conic geometric optimization on the manifold of positive definite matrices. SIAM Journal on Optimization, 25(1):713-739, 2015. Google Scholar
  25. Damian Straszak and Nisheeth K. Vishnoi. Computing maximum entropy distributions everywhere. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1711.02036.
  26. Nisheeth K Vishnoi. Geodesic convex optimization: Differentiation on manifolds, geodesics, and convexity, Jun 2018. URL: https://nisheethvishnoi.files.wordpress.com/2018/06/geodesicconvexity.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact