Skip to main content
Top
Published in:

17-10-2023

Convex Analysis on Hadamard Spaces and Scaling Problems

Author: Hiroshi Hirai

Published in: Foundations of Computational Mathematics | Issue 6/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we address the bounded/unbounded determination of geodesically convex optimization on Hadamard spaces. In Euclidean convex optimization, the recession function is a basic tool to study the unboundedness and provides the domain of the Legendre–Fenchel conjugate of the objective function. In a Hadamard space, the asymptotic slope function (Kapovich et al. in J Differ Geom 81:297–354, 2009), which is a function on the boundary at infinity, plays a role of the recession function. We extend this notion by means of convex analysis and optimization and develop a convex analysis foundation for the unbounded determination of geodesically convex optimization on Hadamard spaces, particularly on symmetric spaces of nonpositive curvature. We explain how our developed theory is applied to operator scaling and related optimization on group orbits, which are our motivation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
To see the consistency with his formulation, use the relation \(b_{\lambda \cdot \mathcal{E}}(gg^{\dagger }) = - \log \det (\mathop {\textrm{diag}}\lambda , g^{\dagger }g)\) for any upper triangular matrix g, where \(\det (\mathop {\textrm{diag}}\lambda , g^{\dagger }g)\) is the relative determinant in the sense of [19].
 
2
From \(\frac{\textrm{d}}{{\textrm{d}}t} \mid _{t=0} \langle \pi (e^{tH_0})u, \pi (e^{tH_0})v\rangle =0\) for \(H_0 \in \mathfrak {u}\), we have \(\langle \Pi (H_0)u,v\rangle + \langle u, \Pi (H_0)v\rangle =0\). Thus, \(\Pi (H_0)^{\dagger } = - \Pi (H_0)\). For \(H = H_0+i H_1\) with \(H_0,H_1 \in \mathfrak {u}\), we have \(\Pi (H)^\dagger = \Pi (H_0)^{\dagger } - i \Pi (H_1)^{\dagger } = - \Pi (H_0) + i \Pi (H_1) = \Pi (-H_0+ i H_1) = \Pi (H^{\dagger })\).
 
3
By \(\pi (k^{\dagger }) = \pi (k^{-1}) = \pi (k)^{-1} = \pi (k)^\dagger \) for \(k \in K\) and polar decomposition \(g= k e^{iH}\) for \(k \in K\) and \(H \in \mathfrak {u}\), we have \(\pi (g^{\dagger }) = e^{- i \Pi (H^{\dagger })} \pi (k^{\dagger }) = e^{-i\Pi (H)^{\dagger }} \pi (k)^{\dagger } = (\pi (k)e^{i\Pi (H)})^{\dagger } = \pi (g)^{\dagger }\).
 
4
This fact can be seen from Proposition 2.33 and the fact that the moment map \(\mu : \pi (G)v {\setminus } \{0\} \rightarrow i \mathfrak {u} (=T_I)\) in [15] is written as \(\mu (\pi (g)v) = g^\dagger df_v(gg^\dagger ) g\).
 
Literature
1.
go back to reference P. Abramenko and K. S. Brown, Buildings—Theory and Applications. Springer, New York, 2008.CrossRef P. Abramenko and K. S. Brown, Buildings—Theory and Applications. Springer, New York, 2008.CrossRef
2.
go back to reference Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, and A. Wigderson, Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. arXiv:1804.01076, 2018, the conference version in STOC 2018. Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, and A. Wigderson, Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. arXiv:​1804.​01076, 2018, the conference version in STOC 2018.
3.
go back to reference S. Amari and K. Nagaoka, Methods of Information Geometry. American Mathematical Society, Providence, RI, 2000. S. Amari and K. Nagaoka, Methods of Information Geometry. American Mathematical Society, Providence, RI, 2000.
4.
go back to reference R. Bergmann, R. Herzog, M. S. Louzeiro, D. Tenbrinck, and J. Vidal-Núñez, Fenchel duality theory and a primal-dual algorithm on Riemannian Manifolds. Foundations of Computational Mathematics 2 (2021), 1465–1504, 2021.MathSciNetCrossRef R. Bergmann, R. Herzog, M. S. Louzeiro, D. Tenbrinck, and J. Vidal-Núñez, Fenchel duality theory and a primal-dual algorithm on Riemannian Manifolds. Foundations of Computational Mathematics 2 (2021), 1465–1504, 2021.MathSciNetCrossRef
5.
go back to reference M. Bačák, Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, Berlin, 2014.CrossRef M. Bačák, Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, Berlin, 2014.CrossRef
6.
go back to reference W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser Verlag, Basel, 1995.CrossRef W. Ballmann, Lectures on Spaces of Nonpositive Curvature. Birkhäuser Verlag, Basel, 1995.CrossRef
7.
go back to reference W. Ballmann, M. Gromov, and V. Schroeder, Manifolds of Nonpositive Curvature, Boston, MA, 1985.CrossRef W. Ballmann, M. Gromov, and V. Schroeder, Manifolds of Nonpositive Curvature, Boston, MA, 1985.CrossRef
8.
go back to reference J. Bennett, A. Carbery, M. Christ, and T. Tao, The Brascamp–Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis 17 (2007) 1343–1415.MathSciNetCrossRef J. Bennett, A. Carbery, M. Christ, and T. Tao, The Brascamp–Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis 17 (2007) 1343–1415.MathSciNetCrossRef
9.
go back to reference N. Boumal, An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge, 2023.CrossRef N. Boumal, An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge, 2023.CrossRef
10.
go back to reference H. Brascamp and E. Lieb, Best constants in Young’s inequality, its converse, and its generalization to more than three functions. Advances in Mathematics20 (1976), 151–173.MathSciNetCrossRef H. Brascamp and E. Lieb, Best constants in Young’s inequality, its converse, and its generalization to more than three functions. Advances in Mathematics20 (1976), 151–173.MathSciNetCrossRef
11.
go back to reference M. R. Bridson and A. Haefliger, Metric Spaces of Non-positive Curvature. Springer-Verlag, Berlin, 1999.CrossRef M. R. Bridson and A. Haefliger, Metric Spaces of Non-positive Curvature. Springer-Verlag, Berlin, 1999.CrossRef
12.
go back to reference M. Brion, Sur l’image de l’application moment. In: M. -P. Malliavin (eds): Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986), Lecture Notes in Mathematics 1296, Springer, Berlin (1987), pp 177–192.CrossRef M. Brion, Sur l’image de l’application moment. In: M. -P. Malliavin (eds): Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986), Lecture Notes in Mathematics 1296, Springer, Berlin (1987), pp 177–192.CrossRef
13.
go back to reference P. Bürgisser, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, arXiv:1711.08039, 2017, the conference version in ITCS 2018. P. Bürgisser, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, arXiv:​1711.​08039, 2017, the conference version in ITCS 2018.
14.
go back to reference P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Efficient algorithms for tensor scaling, quantum marginals and moment polytopes. arXiv:1804.04739, 2018, the conference version in FOCS 2018. P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Efficient algorithms for tensor scaling, quantum marginals and moment polytopes. arXiv:​1804.​04739, 2018, the conference version in FOCS 2018.
15.
go back to reference P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv:1910.12375, 2019, the conference version in FOCS 2019. P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, and A. Wigderson, Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv:​1910.​12375, 2019, the conference version in FOCS 2019.
16.
go back to reference D. A. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms, 4th edition, Springer, Cham, 2015.CrossRef D. A. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms, 4th edition, Springer, Cham, 2015.CrossRef
17.
go back to reference P. B. Eberlein, Geometry of Nonpositively Curved Manifolds. University of Chicago Press, Chicago, IL, 1996. P. B. Eberlein, Geometry of Nonpositively Curved Manifolds. University of Chicago Press, Chicago, IL, 1996.
18.
go back to reference M. Fortin and C. Reutenauer, Commutative/non-commutative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire 52 (2004), B52f. M. Fortin and C. Reutenauer, Commutative/non-commutative rank of linear matrices and subspaces of matrices of low rank. Séminaire Lotharingien de Combinatoire 52 (2004), B52f.
20.
go back to reference C. Franks, T. Soma, and M. X. Goemans, Shrunk subspaces via operator Sinkhorn iteration. arXiv:2207.08311, 2022, the conference version in SODA 2023. C. Franks, T. Soma, and M. X. Goemans, Shrunk subspaces via operator Sinkhorn iteration. arXiv:​2207.​08311, 2022, the conference version in SODA 2023.
21.
go back to reference S. Fujishige, Submodular Functions and Optimization, 2nd Edition. Elsevier, Amsterdam, 2005. S. Fujishige, Submodular Functions and Optimization, 2nd Edition. Elsevier, Amsterdam, 2005.
22.
go back to reference A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Operator scaling: theory and applications. Foundations of Computational Mathematics 20 (2020), 223–290.MathSciNetCrossRef A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Operator scaling: theory and applications. Foundations of Computational Mathematics 20 (2020), 223–290.MathSciNetCrossRef
23.
go back to reference A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Algorithmic and optimization aspects of Brascamp–Lieb inequalities, via Operator Scaling. Geometric and Functional Analysis 28 (2018) 100–145.MathSciNetCrossRef A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Algorithmic and optimization aspects of Brascamp–Lieb inequalities, via Operator Scaling. Geometric and Functional Analysis 28 (2018) 100–145.MathSciNetCrossRef
24.
go back to reference V. Guillemin and S. Sternberg, Convexity properties of the moment mapping, Inventiones Mathematicae 67 (1982) 491–513.MathSciNetCrossRef V. Guillemin and S. Sternberg, Convexity properties of the moment mapping, Inventiones Mathematicae 67 (1982) 491–513.MathSciNetCrossRef
25.
go back to reference L. Gurvits, Classical complexity and quantum entanglement, Journal of Computer and System Sciences 69 (2004), 448–484.MathSciNetCrossRef L. Gurvits, Classical complexity and quantum entanglement, Journal of Computer and System Sciences 69 (2004), 448–484.MathSciNetCrossRef
26.
go back to reference M. Hamada and H. Hirai, Computing the nc-rank via discrete convex optimization on CAT(0) spaces, SIAM Journal on Applied Geometry and Algebra 5 (2021), 455–478.MathSciNetCrossRef M. Hamada and H. Hirai, Computing the nc-rank via discrete convex optimization on CAT(0) spaces, SIAM Journal on Applied Geometry and Algebra 5 (2021), 455–478.MathSciNetCrossRef
27.
go back to reference H. Hirai, L-convexity on graph structures. Journal of the Operations Research Society of Japan 61 (2018), 71–109.MathSciNetCrossRef H. Hirai, L-convexity on graph structures. Journal of the Operations Research Society of Japan 61 (2018), 71–109.MathSciNetCrossRef
28.
go back to reference H. Hirai, H. Nieuwboer, and M. Walter, Interior-point methods on manifolds: theory and applications, arXiv:2303.04771, 2023, the conference version in FOCS 2023. H. Hirai, H. Nieuwboer, and M. Walter, Interior-point methods on manifolds: theory and applications, arXiv:​2303.​04771, 2023, the conference version in FOCS 2023.
29.
go back to reference J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis. Springer-Verlag, Berlin, 2001.CrossRef J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis. Springer-Verlag, Berlin, 2001.CrossRef
30.
go back to reference G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Non-commutative Edmonds’ problem and matrix semi-invariants. Computational Complexity 26 (2017), 717–763.MathSciNetCrossRef G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Non-commutative Edmonds’ problem and matrix semi-invariants. Computational Complexity 26 (2017), 717–763.MathSciNetCrossRef
31.
go back to reference M. Kapovich, B. Leeb, and J. Millson, Convex functions on symmetric spaces, side lengths of polygons and the stability inequalities for weighted configurations at infinity. Journal of Differential Geometry 81 (2009), 297–354.MathSciNetCrossRef M. Kapovich, B. Leeb, and J. Millson, Convex functions on symmetric spaces, side lengths of polygons and the stability inequalities for weighted configurations at infinity. Journal of Differential Geometry 81 (2009), 297–354.MathSciNetCrossRef
32.
go back to reference G. Kempf and L. Ness, The length of vectors in representation spaces, In K. Lønsted (ed.) Algebraic Geometry (Summer Meeting, Copenhagen, August 7–12, 1978), Lecture Notes in Mathematics 732, Springer, Berlin, 1979, pp. 233–243.CrossRef G. Kempf and L. Ness, The length of vectors in representation spaces, In K. Lønsted (ed.) Algebraic Geometry (Summer Meeting, Copenhagen, August 7–12, 1978), Lecture Notes in Mathematics 732, Springer, Berlin, 1979, pp. 233–243.CrossRef
33.
go back to reference B. Kleiner and B. Leeb, Rigidity of invariant convex sets in symmetric spaces. Inventiones Mathematicae 163 (2006), 657–676.MathSciNetCrossRef B. Kleiner and B. Leeb, Rigidity of invariant convex sets in symmetric spaces. Inventiones Mathematicae 163 (2006), 657–676.MathSciNetCrossRef
34.
go back to reference A. W. Knapp, Lie Groups Beyond an Introduction, Second Edition, Birkhäuser, Boston, 2002. A. W. Knapp, Lie Groups Beyond an Introduction, Second Edition, Birkhäuser, Boston, 2002.
35.
36.
go back to reference M. S. Louzeiro, R. Bergmann, and R. Herzog, Fenchel duality and a separation theorem on Hadamard manifolds. SIAM Journal on Optimization 32 (2022), 854–873.MathSciNetCrossRef M. S. Louzeiro, R. Bergmann, and R. Herzog, Fenchel duality and a separation theorem on Hadamard manifolds. SIAM Journal on Optimization 32 (2022), 854–873.MathSciNetCrossRef
37.
go back to reference L. Lovász, Submodular functions and convexity. In A. Bachem, M. Grötschel, and B. Korte (eds.): Mathematical Programming—The State of the Art. Springer-Verlag, Berlin, 1983, pp. 235–257.CrossRef L. Lovász, Submodular functions and convexity. In A. Bachem, M. Grötschel, and B. Korte (eds.): Mathematical Programming—The State of the Art. Springer-Verlag, Berlin, 1983, pp. 235–257.CrossRef
38.
go back to reference K. Murota, Discrete Convex Analysis. SIAM, Philadelphia, 2004. K. Murota, Discrete Convex Analysis. SIAM, Philadelphia, 2004.
39.
go back to reference L. Ness and D. Mumford, A stratification of the null cone via the moment map. American Journal of Mathematics 106 (1984), 1281–1329.MathSciNetCrossRef L. Ness and D. Mumford, A stratification of the null cone via the moment map. American Journal of Mathematics 106 (1984), 1281–1329.MathSciNetCrossRef
40.
go back to reference R. T. Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970.CrossRef R. T. Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970.CrossRef
41.
go back to reference U. G. Rothblum and H. Schneider, Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra and Its Applications 114/115 (1989), 737–764.MathSciNetCrossRef U. G. Rothblum and H. Schneider, Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra and Its Applications 114/115 (1989), 737–764.MathSciNetCrossRef
42.
go back to reference T. Sakai, Riemannian Geometry, American Mathematical Society, Providence, RI, 1996.CrossRef T. Sakai, Riemannian Geometry, American Mathematical Society, Providence, RI, 1996.CrossRef
43.
go back to reference A. Schrijver, Combinatorial Optimization—Polyhedra and Efficiency. Springer, Berlin, 2003. A. Schrijver, Combinatorial Optimization—Polyhedra and Efficiency. Springer, Berlin, 2003.
44.
go back to reference R. Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Mathematics Statistics 35 (1964), 876–879.MathSciNetCrossRef R. Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Mathematics Statistics 35 (1964), 876–879.MathSciNetCrossRef
45.
Metadata
Title
Convex Analysis on Hadamard Spaces and Scaling Problems
Author
Hiroshi Hirai
Publication date
17-10-2023
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 6/2024
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-023-09628-5

Premium Partner