{'fraction_non_alphanumeric': 0.05689880723355137, 'fraction_numerical': 0.02299345902270104, 'mean_word_length': 4.039633909873575, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Old and new challenges in Hadamard spaces

Hadamard spaces have traditionally played important roles in geometry and geometric group theory. More recently, they have additionally turned out to be a suitable framework for convex analysis, optimization and nonlinear probability theory. The attractiveness of these emerging subject fields stems, inter alia, from the fact that some of the new results have already found their applications both in mathematics and outside. Most remarkably, a gradient flow theorem in Hadamard spaces was used to attack a conjecture of Donaldson in Kahler geometry. Other areas of applications include metric geometry and minimization of submodular functions on modular lattices. There have been also applications into computational phylogenetics and imaging. We survey recent developments in Hadamard space analysis and optimization with the intention to advertise various open problems in the area. We also point out several fallacies in the existing proofs.


Introduction
The present paper is a follow-up to the 2014 book [16] with the aim to present new advances in the theory of Hadamard spaces and their applications. We focus primarily on analysis and optimization, because their current development stage is, in our opinion, very favorable. On the one hand, these subject fields are very young and offer many new possibilities for further research, and on the other hand, the existing theory is already mature enough to be applied elsewhere. We will highlight the most notable applications including In spite of the progress described in the present survey, many intriguing questions remain unanswered and many new questions have been raised. We will gather them here, too. Last but not least, we point out that there exist a few rather problematic proofs in this area, which ought to be carefully inspected.
The history of Hadamard spaces can be traced back to a 1936 paper by Wald [202]. Their importance was recognized by Alexandrov [1] in the 1950s and that's why Hadamard spaces are sometimes referred to as spaces of nonpositive curvature in the sense of Alexandrov. Gromov later conceived the acronym CAT(0), where C stands for Cartan, A for Alexandrov and T for Toponogov, and where 0 is the upper curvature bound. Since then, Hadamard spaces have been alternatively called complete CAT(0) spaces. For historical remarks as well as for an authoritative account on CAT(0) spaces in geometry and geometric group theory, the interested reader is referred to the Bridson-Haefliger book [55] Hadamard spaces are, by definition, geodesic metric spaces of nonpositive curvature. More precisely, let (X, d) be a metric space. A mapping γ : [0, 1] → X is called a geodesic if d (γ(s), γ(t)) = |s − A basic notion in convex analysis and optimization is that of strong convexity. A function f : H → (−∞, ∞] is called strongly convex if there exists β > 0 such that for every x, y ∈ H and t ∈ [0, 1]. A prime example of a strongly convex function is f := d (·, x) 2 , for some fixed x ∈ H, as one can see from (1). If f : H → (−∞, ∞] is a strongly convex lsc function, then there exists z ∈ H such that for every x ∈ H; see [16,Proposition 2.2.17]. In particular, each strongly convex function has a unique minimizer. Inequality (3) will appear in the sequel in several special instances (4), (13), (15) and (23). As a first use of strong convexity, we define metric projections onto convex closed sets; see [16, p.33] or [55, p.176]. Given a convex closed set C ⊂ H, recall that its indicator function is defined by It is easy to see that the indicator function ι C : H → (−∞, ∞] is convex and lsc. Since the function f := ι C + d (·, x) 2 , where x ∈ H, is strongly convex and lsc, we obtain immediately from (3) the following important result. We denote the point y by proj C (x). Furthermore, we have (4) d (x, proj C (x)) 2 + d (proj C (x), c) 2 ≤ d(x, c) 2 , for every c ∈ C, which can be viewed as Pythagoras' inequality.
See [  Many Hadamard space theorems surveyed in the present paper have been later proved in some form in more general geodesic spaces, for instance, CAT(1) spaces. We will do our best to provide references to the relevant literature, but our aim here is to present Hadamard space results merely.

Metric and topological structure
This section is devoted to structural properties of Hadamard spaces. We first focus on various results related to the CAT(0) metric and then turn to a topology which is weaker than the topology induced by the metric.
For instance, all strictly convex Banach spaces are Busemann. On the other hand, Hilbert spaces are the only Banach spaces which are CAT(0).
It turns out that the difference between Busemann spaces and CAT(0) can be neatly expressed by the Ptolemy inequality. We say that a metric space satisfies the Ptolemy inequality, or that it is Ptolemaic, if for every x 1 , . . . , x 4 ∈ X.
We can now state the promised result. It is due to Foertsch, Lytchak and Schroeder [82,Theorem 1.3].
Theorem 2.1. A geodesic metric space is a CAT(0) space if and only if it is Busemann and Ptolemaic.
We may now ask whether there exist other conditions which can be imposed on a Busemann space to make it CAT(0). We propose the following.
Problem 2.2. Let (X, d) be a complete Busemann space. Assume that, given a closed convex set C ⊂ X, the metric projection proj C : X → C is a well-defined single-valued nonexpansive mapping. Under which conditions is then (X, d) a Hadamard space?
A possible answer to Problem 2.2 in linear spaces would be: under the condition dim ≥ 3. Indeed, recall a classic result of Kakutani [109,Theorem 3], which says that the nonexpansiveness of (linear) projections in Banach spaces of dimension at least 3 implies that the space is Hilbert. This was later rediscovered by Phelps [175,Theorem 5.2]. A deep study of nonexpansiveness of projections in metric spaces and its relation to the symmetry of orthogonality has been recently carried out by Kell [112].
The following question was raised by Ivanov and Lytchak [101,Question 1].

Problem 2.3. Given a Busemann space, is there a CAT(0) space naturally related to it?
It is for instance known that, given a Busemann space, one cannot in general find a CAT(0) space which is affinely homeomorphic to it (even in linear spaces), or affinely isomorphic to it [101, Section 6].

2.2.
Quadratic and nonquadratic inequalities. We will now proceed by presenting other characterizations of CAT(0). It is known that a geodesic metric space (X, d) is CAT(0) if and only if it satisfies (6) d for every x 1 , . . . , x 4 ∈ X, or, yet equivalently if and only if it satisfies for every x 1 , . . . , x 4 ∈ X. See [16,Theorem 1.3.3]. The fact that inequality (7)-and therefore also (6)-is satisfied in Hadamard space goes back to Reshetnyak [184]. The inverse implication, that is, the fact that (6) implies CAT(0) is a deep result due to Berg and Nikolaev [35,Theorem 6]. A simpler proof was later given by Sato [190]. This characterization of Hadamard spaces answers a question of Gromov [90,Section 1.19+], who asked for a condition implying CAT(0), which would be meaningful also for discrete spaces.
Let us also mention that inequality (6) holds for instance for the metric space X, d 1 2 where (X, d) is an arbitrary metric space, and for ultrametric spaces; see [190,Example 1.2]. Inequality (6) also means that Hadamard spaces have roundness 2. Recall that Enflo [75] defined that a metric space (X, d) has roundness p, where p > 0, if p is the greatest number satisfying for every x 1 , . . . , x 4 . Each metric space has roundness ≥ 1, by virtue of the triangle inequality, and geodesic metric spaces have roundness ≤ 2. On account of (6), CAT(0) spaces have roundness 2. It is also worth mentioning that roundess was in connection with CAT(0) spaces and groups studied by Lafont and Prassidis [134].
Enflo's notion of roundness lead Bourgain, Milman and Wolfson to the definition of the Enflo type of a metric space [47, 3.14]; see also [76,Proposition 3].
Lemma 2.6. Let (H, d) be a Hadamard space. Then for every x 1 , . . . , x n ∈ H we have n i,j=1 Lemma 2.6 has a number of special cases. It gives various quadratic inequalities including (6) as well as nonquadratic inequalities (5) and (7). As a matter of fact, unlike the original proof of (5) from [82], the proof of Lemma 2.6 was achieved without comparisons between geodesic and Euclidean triangles.
There is however a more general phenomenon discovered in [5]. Let's first introduce the terminology from [5]. Given n ∈ N and two matrices A = (a ij ) n i,j=1 , B = (b ij ) n i,j=1 with entries in [0, ∞), we say that a metric space (X, d) satisfies the (A, B)-quadratic metric inequality if n i,j=1 for every x 1 , . . . , x n ∈ X. We say that a metric space (X, d X ) admits a bi-Lipschitz embedding into a metric space (Y, d Y ) if there exist D ≥ 1 and r > 0 and a mapping f : X → Y such that for every x, y ∈ X. Given a bi-Lipschitz embedding f : X → Y, the infimum of D, for which (10) holds true, is called the distortion of f. The infimum of distortions over all bi-Lipschitz embeddings f : X → Y is denoted by c Y (X).
The following is a special case of [5,Proposition 3]. This implies that subsets of Hadamard spaces are fully characterized by quadratic inequalities. In particular, each nonquadratic metric inequality can be obtained as a consequence of quadratic metric inequalities. We have seen a manifestation of this phenomenon above where Lemma 2.6 implied nonquadratic inequalities (5) and (7).
Problem 2.8. Characterize finite metric spaces, which have an isometric embedding into Hadamard spaces.
It is natural to extend the above question of Gromov to bi-Lipschitz embeddings; see [5, 1.4].
Problem 2.9. Characterize finite metric spaces, which have a bi-Lipschitz embedding into Hadamard spaces.
We refer the interested reader to the Andoni-Naor-Neiman paper [5] for detailed discussions and further open problems in this area.
Let's now take a look at bi-Lipschitz embeddings of a finite Hadamard space subset into a Hilbert space. We use the usual asymptotic notation: f (n) = O (g(n)) means there exist n 0 ∈ N and C > 0 such that f (n) ≤ Cg(n) for each n ≥ n 0 , and f (n) = Ω (g(n)) means the same as g(n) = O (f (n)) . Finally, f (n) = Θ (g(n)) means that both f (n) = O (g(n)) and f (n) = Ω (g(n)) .
Bourgain [45,46] proved that an arbitrary metric space with cardinality n, where n ∈ N, can be embedded into a Hilbert space with distortion O (log n) . He also showed that each n-point subset of a metric tree admits such an embedding with distortion Θ √ log log n . These results were later obtained also by Matoušek [145], who used different methods. See also more recent proofs due to Linial and Saks [142] and due to Kloeckner [118]. Let's now ask the following question. What is the minimal D so that each n-point subset of a Hadamard space embeds into a Hilbert space with distortion D? We can conclude from the above discussion that the answer to this question is between √ log log n and log n. As a matter of fact, it is known that D = Θ(log n). This follows from the work of Kondo [127] on expander graphs (see also closely related results of Gromov [92]), which was later extended by Mendel and Naor [147, Theorem 1.1].
For coarse embeddings into Hadamard spaces, the interested reader is referred to a very recent paper by Eskenazis, Mendel and Naor [77].
We close this part by mentioning the work of Chalopin, Chepoi and Naves [61] on isometric embeddings of Busemann surfaces (that is, nonpositively curved two dimensional surfaces) into L 1 . For further interesting properties of Busemann surfaces, see [62] by Chepoi, Estellon and Naves.
2.3. Weak convergence. Since we want to avoid assuming that our Hadamard spaces are locally compact, basic to our considerations is the notion of weak convergence. While local compactness is a standard assumption in geometry and geometric group theory [55], our standpoint is that of (functional) analysis. To our knowledge, Jost was the first to introduce weak convergence in Hadamard spaces [ w → x as t → ∞. This will be used in gradient flow theory later.
In Hilbert spaces, the above definition of weak convergence coincides with the standard one. A wellknown consequence of the Banach-Steinhaus theorem is that a weakly convergent sequence in a Banach space must be bounded. In contrast, in Hadamard spaces we have to put the boundedness assumption into the definition.
Weak convergence is related to an older notion of asymptotic centers. Given a bounded sequence (x n ) ⊂ H, define the function Since ψ is strongly convex, it has a unique minimizer, which we call the asymptotic center of the sequence (x n ) . The definition, in a slightly different form, of asymptotic centers in uniformly convex Banach spaces is due to Edelstein [74]. The following characterization appeared in [78,Proposition 5.2].
Proposition 2.10. A bounded sequence (x n ) ⊂ H weakly converges to a point x ∈ H if and only if x is the asymptotic center of each subsequence of (x n ) .
Like in Hilbert spaces, weak convergence in Hadamard spaces has the following three properties, which are of great importance for the theory.
(i) Each bounded sequence has a weakly convergent subsequence.
(ii) If C ⊂ H is a convex closed set and (x n ) ⊂ C a sequence weakly converging to a point x ∈ H, then x ∈ C. Next we look at an analog of the (weak) Banach-Sachs property. To this end we need the notion of a barycenter of a probability measure from Definition 3.15. Recall also that δ x stands for the Dirac measure at a point x ∈ H. Theorem 2.11 (Banach-Saks property). Let (H, d) be a Hadamard space and (x n ) ⊂ H a sequence weakly converging to a point x ∈ H. Then there exists a subsequence (x n k ) of (x n ) such that the barycenters The weak Banach-Saks property is known to be enjoyed by Hilbert spaces [80]. Its counterpart in Hadamard spaces presented in Theorem 2.11 above was first stated by Jost [ The weak convergence in Hadamard spaces shares with the Hilbert space weak convergence also other properties, for instance, the uniform Kadec-Klee property, or the Opial property; see [16,Chapter 3].
The following question is due to Kirk  In Hilbert space, the desired topology τ is the standard weak topology. However, in general Hadamard spaces the above question remains widely open. Let us mention two natural candidates. Monod defined a topology τ c on H as the weakest topology which makes every bounded convex closed set compact; see [152,Definition 13]. However, the topology τ c seems too weak to be the desired topology from Problem 2.13. We do not know whether τ c is even Hausdorff. We can also attempt to introduce a weak topology as follows. We will say that a set A ⊂ H is open if, for each x 0 ∈ A, there is ε > 0 and a finite family of geodesics γ 1 , . . . , γ N whose ranges all contain x 0 such that the set In this case, however, we do not know whether the sets U x0 (ε, γ 1 , . . . , γ N ) are open.

Convex sets and functions
In this section we concentrate upon basic concepts related to convexity. We start by recalling an important property of metric projections onto closed convex sets.
Another example of a firmly nonexpansive mapping is the proximal mapping; see Section 3.5. Yet another example is the resolvent R λ associated to a nonexpansive mapping, which we define below in (26); see [16,Lemma 4.2.2].
Firm nonexpansiveness in a Hilbert space H is important both in theory and algorithms [32]. It has also connections to various parts of nonlinear analysis and optimization. For instance, a mapping F : H → H is firmly nonexpansive if and only if there exists a maximal monotone operator A : [32,Corollary 23.9]. Here of course the symbol I stands for the identity operator on H.
Let now (H, d) be a Hadamard space and F : H → H a firmly nonexpansive mapping which has a fixed point. It is easy to show that, given a point x ∈ H, the sequence (F n x) weakly converges to a fixed point; see [16, Exercise 6.2].
3.1. Compactness of convex hulls. It is well known that, given a compact set K ⊂ X of a Banach space X, its closed convex hull co K is compact; see for instance [80,Exercise 1.62]. This fact motivates the following question.  . , x N } is compact, then, for each compact set K ⊂ H, its closed convex hull co K is compact.
In other words, Problem 3.3 reduces to the following problem. The above problem is trivial for N = 1 and N = 2, but seem very difficult already for N = 3. As a matter of fact the case N = 3 was posed as an open question by Gromov [90,6.B 1 (f)].

Convex hulls of extreme points. Let
It is easy to see that, given a compact convex set C ⊂ H, it has an extreme point and moreover, the set C is the closed convex hull of its extreme points; see [73,Proposition 2.24]. A much more delicate question is whether each closed convex bounded set C ⊂ H has an extreme point [73,Question 2.23]. The answer is of course yes in Hilbert spaces-by virtue of the Krein-Milman theorem. However, the answer is in general negative due to a recently constructed counterexample of Monod [153].

Reflexivity of Hadamard spaces.
We now look at an analog of reflexivity. It is a standard fact in functional analysis that a Banach space X is reflexive if and only if each nonincreasing family (C i ) i∈I of bounded closed convex sets C i , indexed by an arbitrary directed set I, has nonempty intersection. The following can be found in [ Proposition 3.6. Let (H, d) be a Hadamard space. If (C i ) i∈I is a nonincreasing family of bounded closed convex sets in H, where I is an arbitrary directed set, then i∈I C i = ∅.
Consequently, an arbitrary family (C i ) i∈I of bounded closed convex sets has the following property. If i∈F C i = ∅ for each finite F ⊂ I, then i∈I C i = ∅. The Hilbert ball case of Proposition 3.6 appears in [89, Theorem 18.1].

3.4.
Ultrapowers of Hadamard spaces and convexity. Given a Hadamard space (H, d) and a nonprincipal ultrafilter ω, denote the ultrapower by (H ω , d ω ) . The metric projection proj H : H ω → H is then a 1-Lipschitz retraction and we say that Hadamard spaces are 1-complemented in their ultrapowers.
Let f : H → (−∞, ∞] be a convex lsc function and define This definition appeared in Stojkovic's paper [193 Note that f ω is of course convex. The fact that H ⊂ H ω is a 1-retract is a crucial ingredient in the Plateau problem in Hadamard spaces [204,Theorem 1.6], [205,Theorem 1.3]. In order to state this very interesting result here, we would have to first introduce the general theory of metric currents in metric spaces due to Ambrosio and Kirchheim [4]. Instead, we refer the reader to the original papers and propose the following problem. Note that Stojkovic's proof of the Lie-Trotter-Kato formula (see Theorem 4.10 below) from [193,Theorem 4.4] also relies on ultrapowers of Hadamard spaces. In the simplified proof [17], weak convergence was used instead of the ultrapowers. That was our motivation for raising Problem 3.8.

Moreau envelopes and proximal mappings. Let
This function is a "regularization" of f and has the same set of minimizers as f. It is not difficult to see that Moreau envelopes are convex; see [16,Exercise 2.8]. It is also claimed in [16, p. 42] that the Moreau envelope isn't in general lsc, but it is completely incorrect. As a matter of fact, Moreau envelopes are locally Lipschitz [22, Lemma 2.1].
A closely related notion is the proximal mapping. Given x ∈ H, consider the function This function is strongly convex and hence has a unique minimizer, which we denote by prox f (x). The mapping prox f : H → H is called the proximal mapping associated to the function f. We usually work with an entire family of proximal mappings parametrized by a parameter λ > 0, that is, we consider the proximal mapping prox λf of the function λf for each λ > 0. Proximal mappings were first introduced by Moreau in Hilbert spaces [154,155,156], and then used also in metric spaces (see e.g. Attouch's book [11]). Jost [108], assuming additionally that f is nonnegative, and Mayer [146] were the first to use them later in Hadamard spaces. 5 Proximal mappings were often in the Hadamard space literature (including [16]) called resolvents and denoted by J λ . This terminology comes from Hilbert spaces where the proximal mapping coincides with the resolvent of the convex subdifferential. Indeed, given a convex lsc function f : H → (−∞, ∞] on a Hilbert space H and λ > 0, we have prox λf (x) = (λI + ∂f (x)) −1 , for each x ∈ H, where I : H → H stands for the identity mapping and ∂ denotes the convex subdifferential. 6 Moreau envelopes and proximal mappings are related by the equality which holds for each x ∈ H and λ > 0. A prime example of proximal mappings is the metric projection. Indeed, let C ⊂ H be a convex closed set and ι C : H → (−∞, ∞] be its indicator function. Then prox ιC = proj C . Formula (12) below expresses the dependence of the proximal mapping on the parameter λ and is often referred to as the resolvent identity. It was established by Mayer [ for every λ > µ > 0. Theorem 3.10. The proximal mapping is nonexpansive. 5 As a matter of fact, Jost wanted to establish the existence of prox λf (x) for a general convex lsc function f in [105, Lemma 2], but his proof is incomplete in that it doesn't show that the function in (11) is bounded from below. 6 As for the notation J λ vs. prox λf , we don't mind using either, but since some mathematicians strongly prefer the latter, we stick to it here. Proposition 3.9 allows to improve upon Theorem 3.10 and show that the proximal mapping is even firmly nonexpansive [16, p.45].
Applying variational inequality (3) to the strongly convex function (11) leads to the following important inequality for each y ∈ H. This inequality plays important roles in continuous-and discrete-time gradient flows; see Sections 4 and 6, respectively.
If we replace weak convergence in the above definition by strong one, we obtain the definition of De Giorgi's Γ-convergence [68]. It is easy to see that the Mosco convergence preserves convexity and the limit function is always lsc even if the functions f n are not. Kuwae   This theorem enables to introduce the Mosco topology on the set of convex lsc functions, which is a topology inducing the Mosco convergence; see [22,Section 4] for the details. Another application of Theorem 3.12 is the equivalence between the Frolík-Wijsman convergence and the Mosco convergence of sets. Let us recall a sequence of convex closed sets C n ⊂ H, where n ∈ N, converges to a convex closed set C ⊂ H in the sense of Frolík and Wijsman if d (x, C n ) → d(x, C) for each x ∈ H. The Mosco convergence of sets is defined via indicator functions, that is, a sequence of convex closed sets C n ⊂ H Mosco converges to a convex closed set C ⊂ H if the indicator functions ι Cn Mosco converge to the indicator function ι C . A direct consequence of Theorem 3.12, observed in [22,Corollary 3.4], is that the Frolík-Wijsman and Mosco convergences are equivalent. A Banach space version of Theorem 3.12 can be found in [11,Theorem 3.33].
Jost [108,Definition 1.4.2] defined the Mosco convergence on Hadamard spaces for nonnegative functions by the pointwise convergence of their Moreau envelopes. He also claims it is equivalent to the pointwise convergence of the proximal mappings. This is however not true even on R. Indeed, consider for instance the sequence of constant functions 0, 1, 0, 1, . . . on R, which does not Mosco converge, but the corresponding proximal mappings are all equal to the identity mapping. On the other hand it is known that, under an additional normalization condition, the pointwise convergence of proximal mappings in linear spaces implies the Mosco convergence; see [11,Theorem 3.26]. In Hadamard spaces, only one implication is known. This theorem was proved in [18,Theorem 4.1] and an earlier version for nonnegative functions is due to Kuwae and Shioya [133,Proposition 5.13]. It is therefore natural to raise the following question. See [16,Question 5.2.5].
Problem 3.14. Does the convergence for each x ∈ H and λ > 0, imply, under some additional condition, that the sequence (f n ) converges to f in the sense of Mosco?
3.7. Barycenters of probability measures. Let (X, d) be a metric space and p ∈ [1, ∞). Let P p (X) be the set of probability measures µ on X such that for some/every x ∈ X.
Definition 3.15 (Barycenter). Let µ ∈ P 2 (H). Then the function is strongly convex and we call its unique minimizer the barycenter of µ and denote it by bar(µ).
The existence and uniqueness of barycenters of P 2 (H)-measures were first proved by Korevaar and Schoen [129, Lemma 2.5.1]. Barycenters of finitely supported measures on Hadamard manifolds were, however, studied already by Cartan; see [55, p.178]. Barycenters can be defined for more general probability measures, namely P 1 (H) measures; see Sturm's paper [199,Proposition 4.3].
Given µ ∈ P 2 (H), we denote its variance by With this notation, inequality (3), applied to the strongly convex function in (14), reads The above definitions lead naturally to the notions of the expectation and variance of Hadamard space valued random variables, which are basic building blocks for nonlinear probability theory developed chiefly by Sturm. We refer the reader to [16,Chapter 7] for a gentle introduction to this interesting subject field, and to the references therein for more advanced topics. Interestingly, Hadamard spaces can be fully characterized among complete metric spaces by probability measures [199,Theorem 4.9]. Relatedly, ergodic theorems in Hadamard spaces are due to Austin [12] and Navas [158]. In the erratum [13] to [12], the author corrects his proof of [12,Lemma 2.3], which says that the barycenter mapping bar : P 2 (H) → H is a 1-Lipschitz mapping with respect to the 2-Wasserstein distance, by proving a stronger statement with the 1-Wasserstein distance. This fact 7 was however proved already by Sturm [199,Theorem 6.3] and reproduced in [16,Proposition 2.3.10].
We also note that barycenters of probability measures in CAT(1) spaces were recently studied by Yokota [208,209].
We finish this Section by remarking that some notions from convex analysis in Hilbert spaces have not been sufficiently developed in Hadamard spaces yet, for instance convex subdifferentials or the Fenchel 7 even for P 1 (H) measures duality theory. However research along these lines has already begun; see for instance [157] and the references therein.

Continuous-time gradient flows
Let H be a real Hilbert space and f : H → (−∞, ∞] be a convex lsc function. Consider the following gradient flow problem −ẋ(t) ∈ ∂f (x(t)) , for a.e. t ∈ (0, ∞), (16a) where x 0 ∈ H is a given initial value at time t = 0. This Cauchy problem and its numerous generalizations have been well understood for a long time. We refer the reader to Brezis' classic book [51] and also recommend the recent survey paper by Peypouquet and Sorin [174] which features the approach of Kobayashi [119]. We will now be interested in extending Cauchy problem (16)  S t x := lim where the limit is uniform in t on bounded subintervals of (0, ∞).
Independently of Mayer and a bit earlier, gradient flows for convex functions on Hadamard spaces were studied by Jost [108]. Being interested in energy functionals, Jost formulates the statement of Theorem 4.1 only for nonnegative convex lsc functions [108, Theorem 1.3.13]. However, his proof, which is like Mayer's based on the Crandall-Liggett approach, is seriously flawed: at a crucial step, there is a limit operation involving a quantity l F (x n ) , which tends to infinity, as n → ∞, and does not give the desired conclusion in [108, (1.3.17)]. 9 We note that semigroups of operators in hyperbolic geometries were studied by Reich and Shafrir [182] and by Reich and Shoikhet [183]. Nowadays, gradient flow theory in metric spaces is a hot topic in analysis. We refer the interested reader to the authoritative book on the subject by Ambrosio, Gigli and Savaré [3]. A Hadamard space version of their proof of Theorem 4.1 appeared in [16, Theorem 5.1.6].
The following theorem summarizes the basic properties of the flow [108,146], its proof can be found for instance in [16, Proposition 5.1.8].
Theorem 4.3. The family (S t ) is a strongly continuous semigroup of nonexpansive mappings, that is, • the mapping S t : H → H is nonexpansive for each t > 0,   be a convex lsc function. Assume x 0 ∈ dom f and denote x t := S t x 0 for t ∈ (0, ∞). Then t → x t is absolutely continuous on (0, ∞) and satisfies for almost every t ∈ (0, ∞) and every y ∈ dom f. Conversely, if an absolutely continuous curve z : (0, ∞) → H with lim t→0+ z(t) = x 0 satisfies (18), then z t = S t x 0 for every t ∈ (0, ∞).
Next we would like to express the fact that gradient flows move in the direction of the steepest descent. To this end, we need the notion of a slope. Given a convex lsc function f : H → (−∞, ∞], its slope, denoted by |∂f |, is a mapping |∂f | : H → [0, ∞] given by x ∈ dom f, and by |∂f |(x) := ∞, for x ∈ H \ dom f. We can now state the promised results, they are all due to Mayer [146]. Proofs can be found also in [16, Theorem 5.1.13].
Note also that by applying Theorem 4.1 in Hilbert spaces, we recover classic solutions to Cauchy problem (16), as pointed out already by Mayer [146, Section 2.7].
We will now take a look at gradient flows for a sequence   Finally, we investigate the asymptotic behavior of gradient flows, which was in Hilbert spaces established by Bruck [58]. The following theorem was proved in [14, Theorem 1.5]. We know that the convergence in Theorem 4.9 is not strong in general even in ℓ 2 by an example of Baillon [25].
Before turning to applications, we note that gradient flows in Alexandrov spaces (with upper curvature bound) were studied by Perelman and Petrunin [172] and by Petrunin [173]. The theory was later improved by Lytchak [143]. In this connection we recommend a forthcoming book by Alexander, Kapovich and Petrunin [2].

4.2.
Application: Donaldson's conjecture. The asymptotic behavior of gradient flows in Hadamard spaces established in Theorem 4.9 has become an important tool for attacking a conjecture of Donaldson in Kähler geometry [71]. Let (M, ω) be a compact Kähler manifold. The set of Kähler potentials which corresponds to the set of smooth Kähler metric in the cohomology class [ω], can be equipped with an L 2 -metric and completed with respect to it. We then obtain a Hadamard space K ω . When we extend the Mabuchi energy functional from K ω onto K ω , we get a convex lsc functional on a Hadamard space and we can study its gradient flows. It is known that gradient flows for the Mabuchi energy are the solutions to the Calabi equation, that is, the Calabi flows. Donaldson's conjecture states (roughly speaking) that the Calabi flow exists for all times and converges to a constant scalar curvature metric, which is a minimizer of the Mabuchi energy. The Hadamard space approach to Donaldson's conjecture was initiated by Streets [195], who applied Theorem 4.9 to (the extension of) the Mabuchi energy on K ω and obtained a result on the asymptotic behavior of the Calabi flow. Subsequently, Berman, Darvas, and Lu [41] developed these ideas further by identifying concretely the new elements in K ω \ K ω , which "gives the first concrete result about the long time convergence of this flow on general Kähler manifolds, partially confirming a conjecture of Donaldson". 10 In a similar way, the convergence Theorem 4.9 impacted analogous results in Riemannian geometry; see the paper [95] by Gursky and Streets. Theorem 4.10. Under the above notation, we have Theorem 4.10 is due to Stojkovic [193,Theorem 4.4]. Its proof was later simplified in [17]. A linear space version of Theorem 4.10 is due to Kato and Masuda [111]. There have been however many other closely related results in functional analysis including seminal works by Brezis and Pazy [53,54], Chernoff [64], Kato [110], Miyadera andÔharu [151], Reich [176,177,178] and Trotter [200,201]. We would also like to mention the result of Clément and Maas [65]. Ohta and Pálfia later studied the Lie-Trotter-Kato formula in CAT(1) spaces [166].

Application: Retractions in Finite Subset
Space. We will now show an application of the Lie-Trotter-Kato formula into metric geometry. This application is somewhat unexpected because the original problem has nothing to do with gradient flows.
Let (X, d) be a metric space. Given n ∈ N, denote by X(n) the family of subsets of X which have cardinality at most n. When equipped with the Hausdorff distance d H , the metric space (X(n), d H ) is called a finite subset space. Unlike Cartesian products X n or the space of unordered n-tuples X n /S n , finite subset spaces admit canonical isometric embeddings e : X(n) → X(n + 1), which makes them an interesting object of study. In their 1931 paper [44], Borsuk and Ulam studied finite subset spaces 11 associated to the unit interval I := [0, 1], that is, sets I(n) for n ∈ N. They showed that if n = 1, 2, 3, then I(n) is homeomorphic to I n , whereas if n ≥ 4, then I(n) is not homeomorphic to any subset of ℓ n 2 , the n-dimensional Euclidean space. In the same paper they also raised the following question:   Also determining the optimal distortion seems to be entirely unexplored. . We also note that Kovalev [131] had earlier showed that, given a Hilbert space H and n ≥ 2, there exists a Lipschitz retraction r : H(n) → H(n − 1) with Lipschitz constant O n 1.5 . The following questions were asked already in [21]. We finish this Section by mentioning a very recent and interesting contribution to the theory of gradient flows in Hadamard space due to Ohta [162], who studied the self-contracted property of gradient flow trajectories in the sense of Daniilidis, Ley and Sabourau [70, Definition 1.2]. Recall that a curve c : for every t 1 , t 2 , t 3 ∈ I with t 1 ≤ t 2 ≤ t 3 . We can now state Ohta's result [162,Section 4.3] here. Let us also mention that Daniilidis et al. [69,Proposition 4.16] established the self-contracted property for discrete-time gradient flows in Euclidean spaces, which of course extends to continuous-time gradient flows. 11 Instead of finite subset space, Borsuk and Ulam use the term symmetric product.

Harmonic mappings
This section is devoted to harmonic mappings h : M → H, where M is a measure space and H is Hadamard. There are several ways to define harmonic mappings in this setting (energy minimization, Markov operators, martingales, composition with a function) and their mutual relations are not clear yet.
To our knowledge, the study of harmonic mappings into singular spaces was initiated by Gromov and Schoen in their celebrated paper [93]. Since then, numerous authors have contributed including Korevaar and Schoen [129,130], Jost [104,105,106], Sturm [196,197,198], Ohta [163] and Fuglede [83,84]. We also mention a paper by Mese [148], in which she disproves Jost's theorem on the uniqueness of harmonic mappings from [107,Chapter 4]; see [148,Remark 16]. Finally, a very interesting approach to harmonic mappings is due to Wang [203], which was later improved by Izeki and Nayatani [103]. In this connection we also mention the work of Izeki, Kondo and Nayatani [102] on harmonic mappings and random groups. One of the main motivations for the theory of Hadamard space harmonic mappings have been rigidity theorems; this goes back to the above mentioned paper by Gromov and Schoen [93].
We focus here on Sturm's approach from [197] and refer the interested reader to the original papers for information on the other theories.
Let (M, M, µ) be a space with measure µ. As common in analysis, we consider mappings which differ on a null set as identical. We will now follow [197,Definition 3.1]. Given a measurable mapping h : M → H, we define and equip this space with the L 2 -metric Then L 2 (M, H, h) with the metric d 2 becomes a Hadamard space; see [197,Proposition 3.3]. We assume that (M, M, µ) is equipped with a Markov kernel p(x, dy) which is symmetric with respect to µ, that is, p(x, dy)µ(dx) = p(y, dx)µ(dy). Given a measurable mapping f : M → H, its energy density is defined by If e f ∈ L 1 (M ), we say that f belongs to W 2 (M, H). Furthermore, we define the energy of f by Observe that E(f ) < ∞ if and only if f ∈ W 2 (M, H). It is not difficult to see that, given h ∈ W 2 (M, H), we have L 2 (M, H, h) ⊂ W 2 (M, H); see [197,Lemma 3.2].
Given measurable mappings f, g : M → H, we define a quadratic form Q by Observe that E(f ) = 1 2 Q(f, f ). Given h ∈ W 2 (M, H), the function Q(·, h) is strongly convex on L 2 (M, H, h) and therefore it has a unique minimizer P h ∈ L 2 (M, H, h). The mapping P : W 2 (M, H) → L 2 (M, H, h) is called a Markov operator. A direct consequence of (3) is the following variation inequality for each g ∈ L 2 (M, H, f ); see [197,Lemma 4.1]. Another important property of the Markov operator is nonexpansiveness [197,Theorem 5.2]. It would be interesting to answer the following question. If f has separable range, the Markov operator can be equivalently introduced by the following pointwise definition where f * p(x, ·) is the pushforward of the probability measure p(x, ·) under the mapping f. See [197,Corollary 4.6] and the subsequent discussion.
The following theorem, which characterizes the fixed points of the Markov operator as the minimizers of the energy functional, is due to Sturm; see [197,Theorem 6.6]. 12 We will now look at the gradient flow for the energy E, which was studied by Sturm in [197,Section 8]. Let f ∈ W 2 (M, H). Then E is convex and continuous on the Hadamard space L 2 (M, H, f ) and one can hence apply Theorem 4.1 to obtain the gradient flow (25) t → S t f, t ∈ (0, ∞).
An alternative approach to (heat) flows relying on the Markov operator instead of on the energy functional was introduced in [23]. We first need to recall some abstract theory; see [23,193] for the details.
Let (H, d) be a Hadamard space and F : H → H be nonexpansive. Given x ∈ H and λ ∈ (0, ∞), the mapping is a contraction with Lipschitz constant λ 1+λ and hence has a unique fixed point, which will be denoted by R λ x. The mapping x → R λ x will be called the resolvent of F.
The following important theorem is due to Stojkovic [193,Theorem 3.10]. x, x ∈ H, exists and is uniform with respect to t on each bounded subinterval of (0, ∞). Moreover, the family (T t ) t is a strongly continuous semigroup of nonexpansive mappings, that is, , y), for each t > 0, for every x, y ∈ H.
The following theorem was established in [23, Theorem 1.6]. Its Hilbert ball version is due to Reich [179]. Before returning to harmonic mappings, we make a comment.
Remark 5.6. One can easily notice the formal similarity between Theorems 4.1 and 5.4. As a matter of fact, these two cases are neatly unified in Hilbert spaces via maximal monotone operator theory. Indeed, let H be a Hilbert space, f : H → (−∞, ∞] be convex lsc and F : H → H be nonexpansive. Then the convex subdifferential ∂f and I − F are the most important instances of maximal monotone operators. For further reading we recommend the survey paper by Peypouquet and Sorin [174] as well as the authoritative monograph by Bauschke and Combettes [32]. Maximal monotone operators were in Hadamard manifolds studied in [139,140]. Next we apply the above abstract theory to the Markov operator. Given f ∈ W 2 (M, H), the Markov operator P : L 2 (M, H, f ) → L 2 (M, H, f ) is nonexpansive and Theorem 5.4 provides us with the heat flow semigroup (28) t → T t f, t > 0.
We remark that the exposition of this matter in [23, Section 6] refers-by mistake-the Markov operatorP (defined pointwise) instead of the Markov operator P. As we have noted above, the Markov operatorP would be appropriate only for mappings with separable ranges, but we do not want the make any such restriction.
We now arrive at the following question; see [ Note that one can choose a set D ∈ M and consider the Dirichlet problem on D in the above discussion; see [23,197]. However, we chose D = M here for simplicity.
We finish this Section by addressing the existence of harmonic mappings. Let us again first look at an abstract theory. If H is a Hilbert space, F : H → H is nonexpansive and x ∈ H, define for each k ∈ N 0 . Assume that the sequence (m k ) is bounded. Then each weak cluster point of (m k ) is a fixed point of F. In particular, the set of fixed points of F is nonempty. See [174,Lemma 4.7]. We now aim at extending this result into Hadamard spaces. To this end define where F : H → H is a nonexpansive mapping on a Hadamard space (H, d) and x ∈ H.
Problem 5.8. If the sequence (m k ) is bounded for some/every x ∈ H, is then its set of weak cluster points (which is nonempty) contained in Fix F ? In particular, has F a fixed point?
We could then apply the above claim to the Markov operator and get the existence of a harmonic mapping. However, we would also have to determine for which Markov kernels p(x, dy) is the boundedness assumption satisfied.

Discrete-time gradient flows
Continuous-time gradient flows studied in Section 4 are constructed from their discrete-time approximations. It turns out, however, that the discrete-time approximate solutions are of interest on their own and can be used for numerical computations. Since one defines the discrete-time approximations by applying the proximal mapping, this method is called the proximal point algorithm and abbreviated PPA. In linear spaces, it was introduced by Martinet [144] and extended further by Rockafellar [189] and Brézis and Lions [52]. From recent literature we recommend [66,72,170] which witness about the increasing popularity of this optimization method. On Hadamard manifolds, the PPA was studied by Ferreira and Oliveira [81], Papa Quiroz and Oliveira [169] and Li, López and Martín-Márquez [139]. The algorithm has been recently studied in metric spaces by a number of authors including Zaslavski [211], Ohta and Pálfia [165], Kimura and Kohsaka [113,114,115,116], Kohsaka [126] and Espínola and Nicolae [79].
Let us now formulate a convex optimization problem in Hadamard spaces and show how the PPA is used to find a minimizer of the objective function.
Let (H, d) be a Hadamard space and f : H → (−∞, ∞] be a convex lsc function attaining its minimum. We would like to find a minimizer of f. To this end, we choose a point x 0 ∈ H, and define (29) x n := prox λnf (x n−1 ) , for each n ∈ N. The proximal point algorithm in Hadamard spaces was first studied in [14]. The proof of the following convergence theorem can be found in [14,Theorem 1.4].
Theorem 6.1 (Basic PPA). Let (H, d) be a Hadamard space and f : H → (−∞, ∞] be a convex lsc function attaining its minimum. Then, for an arbitrary point x 0 ∈ H and a sequence of positive reals (λ n ) such that ∞ 1 λ n = ∞, the sequence (x n ) ⊂ H defined in (29) weakly converges to a minimizer of f. In general, one cannot replace weak convergence in the above theorem by strong convergence. The first counterexample in Hilbert spaces is due to Güler [94]. For further examples, see [31,33]. A convergence analysis of the PPA for uniformly convex functions was carried out by Leuştean and Sipoş [138]. An abstract version of the PPA has been recently introduced by Leuştean, Nicolae and Sipoş [137]. We would also like to mention recent related results of Reich and Salinas [180,181].
6.1. Splitting proximal point algorithms. In many optimization problems, the objective function is given as a sum of finitely many functions. It turns out that we can benefit from taking this structure of the objective function into account and design much more efficient algorithms for such optimization problems. To be now more concrete, we will consider objective functions of the form (2). While the "basic" PPA in (29) would use the proximal mapping of the function f, which is typically difficult to compute, the splitting PPA relies on the evaluation of the proximal mappings associated to the individual functions f n , for n = 1, . . . , N. We obtain two variants of the splitting PPA depending on whether we apply these proximal mappings in cyclic or random order. Sadly, in this Section we need to require our Hadamard space to be locally compact; see Problem 6.4. The splitting PPA in Euclidean spaces was introduced by Bertsekas in his seminal paper [42].
Let (λ k ) be a sequence of positive reals and let x 0 ∈ H be an arbitrary starting point. We now introduce the cyclic order version of the splitting PPA. For each k ∈ N 0 , we set The following convergence theorem was obtained in [15,Theorem 3.4]. Theorem 6.2 (Splitting PPA with cyclic order). Let (H, d) be a locally compact Hadamard space and let f : H → (−∞, ∞] be a function of the form (2) which attains its minimum. Let (λ k ) ∈ ℓ 2 \ ℓ 1 be a sequence of positive reals. Given x 0 ∈ H, let (x j ) be the sequence defined in (30). Assume there exists L > 0 such that for each k ∈ N 0 and n = 1, . . . , N. Then (x j ) converges to a minimizer of f.
One can observe immediately from the proof 14 of Theorem 6.2 that, given k ∈ N 0 , it is not necessary to insist on applying the proximal mappings prox λ k fn , where n = 1, . . . , N, in the prescribed order. Indeed, a popular approach in optimization is to shuffle randomly the indices 1, . . . , N at the beginning of each cycle and apply the proximal mappings in the newly obtained order.
We now turn to the random order version of the splitting PPA. Consider the probability space Ω := {1, . . . , N } N0 equipped with the product of the uniform probability measure on {1, . . . , N } and let (r k ) be the sequence of random variables Let again f : H → (−∞, ∞] be a function of the form (2) and let (λ k ) be a sequence of positive reals. Given a starting point x 0 ∈ H, we put The following theorem was obtained in [15,Theorem 3.7]. Its proof relies on the supermartingale convergence theorem of Robbins and Siegmund [185]. To simplify the notation, we denote by x n k+1 the result of the iteration (31) if r k (ω) = n. Theorem 6.3 (Splitting PPA with random order). Let (H, d) be a locally compact Hadamard space and let f be a function of the form (2) which attains its minimum. Let (λ k ) ∈ ℓ 2 \ ℓ 1 be a sequence of positive reals. Given a starting point x 0 ∈ H, let (x k ) be the sequence defined in (31). Assume there exists L > 0 such that f n (x k ) − f n x n k+1 ≤ Ld x k , x n k+1 , for every k ∈ N 0 and n = 1, . . . , N. Then (x k ) converges to a minimizer of f almost surely.
We raise the following natural questions. Problem 6.4. Can one extend Theorems 6.2 and 6.3 into separable Hadamard spaces without the local compactness assumption? In this case-of course-we can hope for weak convergence only. This problem is open even for separable Hilbert spaces.
The splitting PPA was later extended into the 1-dimensional sphere S 1 , which is only a locally Hadamard space, and applied successfully in image restoration problems by Bergmann, Steidl and Weinmann [37,39,40]; see also the follow-up paper [20] and Steidl's survey [192]. Ohta and Pálfia [165] then extended these minimization algorithms into domains of general Alexandrov spaces. In Hadamard manifolds, Bergmann, Persch and Steidl [38] used the Douglas-Rachford algorithm in convex minimization problems in image processing. Other interesting applications of convex optimization in Hadamard manifolds into image processing are due to Bergmann et al. [36] and due to Neumayer, Persch and Steidl [159]. The splitting PPA has been recently used in the manifold setting by Bredies et al. [49] and by Storath and Weinmann [194].
6.2. Application: Computing medians and means. Given a finite number of points a 1 , . . . , a N ∈ H and weights w 1 , . . . , w N ≥ 0 with w n = 1, consider the function where p ∈ [1, ∞). This function is obviously convex and continuous. In particular, we are concerned with two important cases: (i) If p = 1, then f becomes the objective function in the Fermat-Weber problem for optimal facility location. It has always a minimizer, which is however in general not unique. We call it a (weighted) median of the points a 1 , . . . , a N .
(ii) If p = 2, then f is strongly convex and has therefore a unique minimizer, which is called the (weighted) mean of the points a 1 , . . . , a N . Observe that the mean can be viewed as the barycenter of the probability measure µ := N n=1 w n δ an .
In Hilbert spaces, the mean coincides with the arithmetic mean.
We could in principle minimize the function f in (32) by the "basic" PPA, but there is no explicit formula for the proximal mapping. On the other hand it is easy to verify that the assumptions of Theorems 6.2 and 6.3 are satisfied for the function f in (32) and we can therefore minimize f by the splitting PPA. The main advantage of this approach is that the proximal mappings are very easy to evaluate, see [16,Section 8.3].
Computing means in Hadamard space is of great importance in applications. Indeed, in diffusion tensor imaging one needs to compute means of positive definite matrices (which form a Hadamard manifold as we noted above). However, since the underlying space in this case is a manifold, we can alternatively use explicit gradient-based minimization methods to compute the means [171]. Another important application, where we need to compute means in a Hadamard space, is computational phylogenetic. In this case the underlying Hadamard space has no differentiable structure and the only known possibility to compute means is the above method based on the splitting PPA. We will present more details in Section 6.3.
6.3. Application: Averaging phylogenetic trees. Given a finite number, say n, of entities (for instance genes, or species), biologists represent their evolutionary history by a phylogenetic tree. It is defined as a metric tree whose terminal vertices are labeled by 1, . . . , n. In their seminal paper [43], Billera, Holmes and Vogtmann equipped the set of such trees with the structure of a CAT(0) cubical complex and the resulting locally compact Hadamard space is now referred to as the BHV tree space. We denote it by T n , where n ≥ 3 stands for the number of terminal vertices.
In order to use the BHV tree space in practice, one needs an (efficient) algorithm for computing distances and geodesics. By "computing geodesics" we mean: given x, y ∈ T n and t ∈ (0, 1), compute the point (1 − t)x + ty. Indeed, the lack of such an algorithm hindered the use of the BHV tree space for about a decade. Based on an earlier attempt of Owen [167], who came up with an exponential time algorithm, Owen and Provan [168] finally provided the desired algorithm with polynomial runtime.
In this connection we note that algorithms for computing distances and geodesics in CAT(0) cubical complexes were studied by Chepoi and Maftuleac [63] in two dimensions and by Ardila, Owen and Sullivant [8] in arbitrary dimensions. These works were later improved by Hayashi [98] who introduced a polynomial time algorithm in arbitrary dimensions. Such algorithms in cubical CAT(0) complexes are of interest in, for instance, robotics; see the work of Ardila, Baker and Yatchak [6] and Ardila et al. [7] and the references therein.
Together with the Owen-Provan algorithm for computing distances and geodesics in the BHV tree space, the splitting PPA allows to compute medians and means of phylogenetic trees, which are important operations in computational phylogenetics. For more details, see [16,Chapter 8] and the references therein. A real statistical model for phylogenetic inference based on these techniques was introduced in [34]. We note that computing means in the BHV tree space was independently studied by Miller, Owen and Provan and we recommend their paper also for many other interesting results and observations.
Based on these first steps, statistical theory in the BHV tree space began to develop. The computation of variance was featured in the papers by Brown and Owen [57] and by Miller, Owen and Provan [150]. Barden, Le and Owen studied the central limit theorem in [28]. Further refined analyses of means are due to Skwerer, Provan, and Marron [191] and Barden, Le and Owen [29]. Nye et al. [161] used the algorithm for computing means as a building block for developing more sophisticated statistical methods, namely the principal component analysis.
For further information on recent developments in tree spaces, we refer the interested reader into [27,86,141,160,206,207]. We also recommend Miller's interesting overview [149]. 6.4. Stochastic proximal point algorithm. While we studied finite sums of convex lsc functions in the previous sections, now we turn to integrals. Such integral functionals were first considered in convex analysis by Rockafellar [186,187,188] and have become a classic object of study with many interesting properties and important applications, for instance, in financial mathematics [132]. Throughout this Section, the underlying space will again be a locally compact Hadamard space (H, d).
Let (S, µ) be a probability space and assume that a function f : H × S → (−∞, ∞] satisfies (i) f (·, ξ) is a convex lsc function for each ξ ∈ S, (ii) f (x, ·) is a measurable function for each x ∈ H. Then define We will assume that F (x) > −∞ for every x ∈ H and that F is lsc (which can be assured, for instance, by Fatou's lemma).
Following [19], we now define the stochastic version of the PPA. To this end, we denote by (ξ k ) the sequence of random variables where Ω := S N . Let (λ k ) be a sequence of positive reals. Given x 0 ∈ H, define random variables for each k ∈ N. The convergence of the proximal sequence (x k ) is guaranteed by Theorem 6.5 below. For the proof, see [19, Theorem 3.1].
Theorem 6.5 (Stochastic PPA). Assume that (i) a function F is of the form (33) and has a minimizer, (ii) there exists p ∈ H and an L 2 -function L : S → (0, ∞) such that for every x, y ∈ H and almost every ξ ∈ S, (iii) (λ k ) ∈ ℓ 2 \ ℓ 1 is a sequence of positive reals. Then there exists a random variable x : Ω → Min F such that for almost every ω ∈ Ω the sequence (x k (ω)) given by (34) converges x(ω).
An application of Theorem 6.5 will be given in Section 6.5 below. Like in the case of the splitting PPA, we raise the following question. Problem 6.6. Can one prove weak convergence of the stochastic PPA in (separable) Hadamard spaces without the local compactness assumption? This is unknown even for (separable) Hilbert spaces.
To finish this Section, we look at the (intuitively obvious) fact that finite sums of functions approximate integral functionals. The rigorous argument is however more involved. Artstein and Wets proved (a more general form of) the following theorem in [10, Theorem 2.3].
Theorem 6.7 (Consistency). Let again F be the functional from (33) and let (ξ k ) be an iid sequence with distribution µ. Then the sequence of functions almost surely Γ-converges to F. 6.5. Application: Medians and means of general probabilities. Consider now a probability measure µ ∈ P 2 (H). Then the assumptions of Theorem 6.5 are satisfied for the functionals d(·, z) dµ(z), and d(·, z) 2 dµ(z), and we can therefore employ the stochastic PPA to find their minimizers, which are called a median and mean, respectively. One can observe that the corresponding proximal mappings are easy to evaluate. We note that it was observed already by Miller, Owen and Provan [150] that means can be alternatively approximated via Sturm's law of large number [199,Theorem 4.7]. 15 With the stochastic PPA at hand, one can improve upon the statistical model from [34]. Indeed, we are to approximate the mean of a given probability distribution µ D of phylogenetic trees on the BHV tree space T n . The approach taken in [34] is first to generate a finite set of samples from µ D by a Markov Chain Monte Carlo (MCMC) simulation and then compute their mean. However, now we can simply generate samples by MCMC on-the-fly and average them on-the-fly by the stochastic PPA. This way we eliminate the error coming from the approximation of the integral by a finite sum. 6.6. Minimization of submodular functions on modular lattices. Now we start a completely new topic. It has turned out recently that the above Hadamard space algorithms can be used for minimizing submodular functions on modular lattices. This was discovered by Hamada and Hirai [97]. We first recall some algebra.
A partially ordered set (L, ≤) is called a lattice if, given x, y ∈ L, there exist their least upper bound (denoted by x ∨ y) and their greatest lower bound (denoted by x ∧ y). Given n ∈ N, we say that x 0 , . . . , x n ∈ L form a chain if x 0 < · · · < x n . The number n is called the length of this chain. Here we consider only lattices, in which each chain has finite length. Let 0 L and 1 L denote the minimum and maximum element in L, respectively. Given x ∈ L, the maximum length of a chain 0 L < · · · < x is called the rank of x and is denoted by rank (x) . The rank of L is defined as rank (L) := rank (1 L ) .
A lattice (L, ≤) is modular if x ∨ (y ∧ z) = (x ∨ y) ∧ z, whenever x, y, z ∈ L and x ≤ z. It is known that a lattice is modular if and only if rank (x ∧ y) + rank (x ∨ y) = rank (x) + rank (y) , for every x, y ∈ L.
The class of modular lattices comprises distributive lattices. Recall that a lattice L is distributive if for every x, y, z ∈ L.
A lattice L is complemented if, given x ∈ L, there exists y ∈ L such that x ∨ y = 1 L and x ∧ y = 0 L . A lattice is distributive and complemented if and only if it is isomorphic to a Boolean lattice.
Example 6.8. Let X be a finite-dimensional vector space. The set of its subspaces equipped with the inclusion order is a prime example of a modular lattice. Here, given subspaces Y, Z ⊂ X, we have The rank of a subspace is its dimension and since we see that this lattice is modular.
Other examples of modular lattices include the lattice of submodules of a modul over a ring (e.g. the lattice of subgroups of an abelian group), and the lattice of normal subgroups of a given group.
for every x, y ∈ L. 15 The law of large numbers has been recently extended into CAT(1) spaces by Yokota [210].
A key role in the further developments will be played by the orthoscheme complex introduced by Brady and McCammond [48]. We will now follow the presentation of Hamada and Hirai [97]. Given n ∈ N, the n-dimensional orthoscheme is the simplex in R n with vertices 0, e 1 , e 1 + e 2 , . . . , e 1 + · · · + e n , where e 1 , . . . , e n denote the canonical basis in R n . Let now L be a modular lattice of rank n and F (L) be the free R-module over L, that is, the set of formal linear combinations x = y∈L t y y, where t y ∈ R for each y ∈ L, and the set supp(x) := {y ∈ L : t y = 0} is finite. We call the above set the support of x. Let K(L) be a subset of F (L) consisting of elements x = y∈L t y y, with t y > 0 and y∈L t y = 1 and supp(x) being a chain in L. That is, K(L) is a geometric realization of the order complex of L. A simplex is a subset of K(L) consisting of all convex combinations of a given chain. Given a simplex σ ⊂ K(L) corresponding to a maximal chain y 0 < · · · < y n , we define a mapping φ σ from σ to the n-dimensional orthoscheme by φ σ (x) := n k=1 t k (e 1 + · · · + e k ) , x = n k=0 t k y k .
We then equip each simplex σ ⊂ K(L) with the metric d σ defined by for each x, y ∈ σ. Finally, we equip K(L) with the induced length metric. This results in a complete geodesic space by virtue of Bridson's theorem [55,Theorem 7.19]. The following result due to Chalopin, Chepoi, Hirai and Osajda [60] will be instrumental for us. Theorem 6.9. Let L be a modular lattice of finite rank. Then K(L) is a CAT(0) space.
The above theorem settles a conjecture of Brady and McCammond [48, Conjecture 6.10]. We remark that an important special case of this theorem was obtained in [96] by Haettel, Kielak and Schwer, assuming additionally that the lattice is complemented.
We also stress that the lattice L in the above construction can be infinite. Only its rank is assumed to be finite.
As a matter of fact, one can associate an orthoscheme complex to a more general structure than a lattice, namely to a graded poset of finite rank. This level of generality was used in [48,60]. It is therefore natural to ask the following question, which we reproduce here from [60, Conjecture 7.3]. Problem 6.10. Let L be a modular semilattice of finite rank. Is the orthoscheme complex K(L) a CAT(0) space?
We will proceed by showing that a submodular function on a modular lattice can be extended to a convex function on the orthoscheme complex. This was worked out by Hamada and Hirai in [97]. Let L be a modular lattice. The Lovász extension of a function f : L → R is a function f : where x = k t k x k ∈ K(L). For further information on submodular functions, we refer the interested reader to Fujishige's book [85]. The above theory was applied to the maximum vanishing subspace problem, shortly MVSP, by Hamada and Hirai [97]. The MVSP is an algebraic generalization of the stable-set problem for bipartite graphs in combinatorial optimization. By considering a Hadamard space relaxation of the MVSP, where the objective function is the Lovász extension of a dimension function defined on the modular lattice of subspaces of a finite dimensional vector space, the authors designed a polynomial time algorithm for the MVSP. Their algoritm relies on the splitting PPA in Hadamard spaces. We refer the interested reader to the original paper [97] for further details on this very interesting application.
Since this approach pioneered by Hamada and Hirai in [97] can be readily applied to other modular lattices and submodular functions, we believe that further applications will appear soon. In this connection we also recommend Hirai's paper [99]. 6.7. Splitting proximal point algorithm for relaxed problems. We will now look at yet another variant of the PPA. Let (H, d) be a Hadamard space 16 and let f 1 , f 2 : H → (−∞, ∞] be convex lsc functions. Instead of minimizing the function f 1 +f 2 on H, one may consider a relaxed problem: minimize the function (35) (x, y) → f 1 (x) + f 2 (y) + 1 2λ d(x, y) 2 on the space H × H, where λ > 0 is a fixed parameter. This problem was studied by Banert [26], who obtained the following convergence theorem.
Theorem 6.12. Given x 0 ∈ H, define y n := prox λf2 (x n ) and x n+1 := prox λf1 (y n ) , for every n ∈ N 0 . Then the sequence (x n , y n ) weakly converges to a minimizer of the function in (35) provided this function attains its minimum.
Banert's result was later obtained as a corollary of a more abstract fixed point theorem by Ariza-Ruiz, López-Acedo and Nicolae [9, Corollary 4.5].
6.8. Asymptotic regularity of the composition of projections. Our last topic is not directly related to discrete-time gradient flows, but it is an important part of convex optimization and we find the result (as well as its proof) so interesting that we decided to mention it in the present survey.
Let H be a Hilbert space and C 1 , . . . , C N ⊂ H be a finite family of convex closed sets. Given x 0 ∈ H, define x n := proj CN • · · · • proj C1 (x n−1 ) , for n ∈ N. The sequence (x n ) is used in optimization to solve convex feasibility problems, that is, to approximate a point x ∈ N n=1 C n . This approach is called the cyclic projection method, or, if N = 2, we use the expression alternating projection method. Bregman [50] proved that (x n ) weakly converges to a point x ∈ N n=1 C n , provided N n=1 C n = ∅. By Hundal's counterexample [100] we know that this cannot be improved to strong convergence even for N = 2.
A remarkable theorem of Bauschke [30] says that, even without the assumption N n=1 C n = ∅, the sequence (x n ) is asymptotically regular, that is, as n → ∞. Recall that asymptotic regularity was introduced by Browder and Petryshyn [56] and has become a basic analysis tool in optimization. For further information on this topic, we refer the interested reader to Bauschke's paper [30] and the references therein. Here we mention only Kohlenbach's recent paper [122] in which he obtained an explicit polynomial rate of asymptotic regularity of the above sequence by applying sophisticated methods from logic called proof mining to Bauschke's original proof. For further information on proof mining and its applications in Hadamard spaces, the interested reader is referred to Kohlenbach's authoritative monograph [120] and to the papers [121,123,124,125].
It is natural to ask whether one can extend the above results into Hadamard spaces.
Problem 6.13. If we consider a general Hadamard space, is the sequence (x n ) asymptotically regular? Can we obtain a polynomial rate of its asymptotic regularity?
We note that projection methods in Hadamard spaces were studied in [9,24].