Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces

28/08/2013
OAI : oai:www.see.asso.fr:2552:4872
DOI :

Résumé

Miklós Pálfia


Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces

Métriques

820
212
134.82 Ko
 application/pdf
bitcache://d61b8e40d96018bc364fa33bb0464c0b8c7d5e67

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4872</identifier><creators><creator><creatorName>Miklós Pálfia</creatorName></creator></creators><titles>
            <title>Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 16 Sep 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 20 Apr 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">d61b8e40d96018bc364fa33bb0464c0b8c7d5e67</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9603</version>
        <descriptions>
            <description descriptionType="Abstract">Miklós Pálfia
</description>
        </descriptions>
    </resource>
.

Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Mikl´os P´alfia Department of Mathematics Sungkyunkwan University Republic of Korea August 30, 2013 palfia.miklos@aut.bme.hu Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Introduction Introduction Let (M, δ) be a complete metric space. (M, δ) is called an Hadamard or NPC space if for each x, y ∈ M, there exists an m ∈ M satisfying δ2 (m, z) ≤ 1 2 δ2 (x, z) + 1 2 δ2 (y, z) − 1 4 δ2 (x, y) for all z ∈ M. ◮ m is the unique metric midpoint between x and y ◮ the midpoint operation gives rise to a unique minimal geodesic γa,b : [0, 1] → M connecting any a, b ∈ M ◮ simply denote a#tb := γa,b(t) Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Introduction Properties of NPC spaces Proposition Let (M, δ) be an NPC space. Then for all t ∈ [0, 1] and z, a, b ∈ M, δ2 (z, a#tb) ≤ (1 − t)δ2 (z, a) + tδ2 (z, b) − t(1 − t)δ(a, b)2 . ◮ the NPC inequality means nonpositive curvature, i.e. every M is equivalently a CAT(0)-space Theorem Let (M, δ) be a complete metric space, such that M is a Riemannian manifold with Riemannian metric distance d. Then M has nonpositive sectional curvature iff (M, δ) is an NPC space. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Introduction an NPC space is also an Alexandrov space with upper curvature bound, therefore: ◮ the set of all NPC spaces includes Riemannian manifolds, metric trees, tripods and also possibly other discrete and infinite dimensional metric spaces ◮ infinite dimensions are permitted, i.e. local compactness of (M, δ) is not necessary fulfilled ◮ however in all NPC spaces (M, δ) upper and lower Alexandrov angles coincide, this leads to well defined angles ◮ angles lead to a generalized inner product ·, · on the tangent cone of (M, δ) Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Introduction Some important examples of NPC spaces ◮ the cone P(r, C) of r-by-r complex positive definite matrices with Riemannian metric distance d2 (A, B) = Tr log2 A−1/2 BA−1/2 induced by the Riemannian metric X, Y p = Tr p−1 Xp−1 Y where X, Y ∈ H(r, C), the real vector space of r-by-r complex Hermitian matrices and p ∈ P(r, C). Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Introduction P(r, C) isometrically embeds into a larger NPC space: ◮ the cone of unitized Hilbert-Schmidt operators P over a Hilbert space E, with Riemann-Hilbert metric X, Y p = p−1 Xp−1 Y 2 , where X, Y ∈ HSR = {λ + a : λ ∈ R, a = a∗ Hilbert-Schmidt}, p ∈ P, and λI + A, µI + B 2 = λµ + Tr{b∗a} P is a symmetric space of noncompact type, every such space isometrically embeds into it Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Fr´echet or Karcher mean Let (M, δ) be an NPC space, ∆n denotes the simplex of positive probability n-vectors, i.e. ω = (w1, . . . , wn) ∈ ∆n iff wi > 0, n i=1 wi = 1. Definition (Fr´echet or Karcher mean) The Karcher mean Λ(ω; a) of the n-tuple a = (a1, . . . , an) ∈ Mn with the weight ω = (w1, . . . , wn) ∈ ∆n, is defined as Λ(ω; a) = arg minx∈M n i=1 wi δ2 (x, ai ). Theorem On NPC spaces the center of mass or Karcher mean of any n-tuple of points always exist and is unique. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Sturm’s result: Theorem (Variance inequality) Let (M, δ) be an NPC space. Then for any x ∈ M and n-tuple a = (a1, . . . , an) ∈ Mn with weight ω = (w1, . . . , wn) ∈ ∆n, we have δ2 (x, Λ(ω; a)) ≤ n i=1 wi δ2 (x, ai ) − δ2 (Λ(ω; a), ai ) . ◮ the above inequality characterizes Λ(ω; a) and also is equivalent to the NPC inequality Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Definition (Weighted inductive mean) For ω = (w1, . . . , wn) ∈ ∆n and a = (a1, . . . , an) ∈ Mn with n ≥ 1, define S1(1; a1) = a1 (n = 1) Sn(ω; a) = Sn−1(ˆω; ˆa)#wn an, (n ≥ 2) where ˆω = 1 1−wn (w1, . . . , wn−1) ∈ ∆n−1 and ˆa = (a1, . . . , an−1) ∈ Mn−1. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Approximations of Λ Sturm’s stochastic result: Theorem (Law of large numbers) Let ω = (w1, . . . , wn) ∈ ∆n and a = (a1, . . . , an) ∈ Mn arbitrary. Let Yi , i ∈ N be a sequence of independent identically distributed random variables on a probability space (Ω, A , µ) with values in M and with pushforward distribution µ(x) = n i=1 wi δai (x) in M, where δz (x) is the Dirac measure supported on {z}. Then the sequence Sk of inductive means S1 = Y1 Sk+1 = Sk# 1 k+1 Yk+1 converges to Λ(ω; a) almost surely. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Holbrook recently refined Sturm’s result in a special NPC space: Theorem (No dice theorem) Let A = (A1, . . . , An) ∈ P(r, C)n arbitrary. Then the sequence of inductive means S1 = A1 Sk+1 = Sk# 1 k+1 A(k+1) where k + 1 is computed modulo n (with the convention of identifying the residual 0 with n), converges to Λ((1 n , . . . , 1 n ); A). ◮ it means that the inductive means of the truncated, ”plausible” sequence (a1, a2, a3, a1, a2, a3, . . .) converges to Λ(1/3, 1/3, 1/3; a1, a2, a3) Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces A weighted deterministic walk for Λ Our result extends Holbrook’s and Sturm’s: Theorem Let a = (a1, . . . , an) ∈ Mn and ω = (w1, . . . , wn) ∈ ∆n. Then the sequence of weighted inductive means S1 = a1 Sk+1 = Sk#sk+1 ak+1, where sk = wk l(k) with l(k) = k i=1 wi satisfies the inequality δ2 (Λ(ω; a), Sk) ≤ 1 l(k) 3∆(a)2 + n i=1 wi δ2 (Λ(ω; a), ai ) for all k = 1, 2, . . .. I.e. the sequence Sk converges to Λ(ω; a). Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces Some properties of means ◮ a function G : ∆n × Mn → M is called a weighted mean if it is idempotent, i.e. G(ω; x, . . . , x) = x for all x ∈ M and ω ∈ ∆n ◮ a map G : ∆n × Mn → M is said to be contractive if for all ω = (w1, . . . , wn) ∈ ∆n, a = (a1, . . . , an), b = (b1, . . . , bn) ∈ Mn, δ(G(ω; a), G(ω; b)) ≤ n i=1 wi δ(ai , bi ) ◮ a map G : ∆n × Mn → M satisfies the extended metric inequality (EMI) if δ2 (x, G(ω; a)) ≤ n i=1 wi δ2 (x, ai ) for all x ∈ M, a = (a1, . . . , an) ∈ Mn and ω = (w1, . . . , wn) Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Means in NPC spaces En denotes the set of all f : Mn → M satisfying EMI and ˆEn ⊆ En by the set of all contractive functions satisfying EMI. ◮ if G satisfies EMI, then G is a weighted mean, also δ(ai , G(ω; a1, . . . , an)) ≤ ∆(a1, . . . , an) for all i = 1, . . . , n, where ∆(a1, . . . , an) = max1≤i,j≤n δ(ai , aj ). Lemma We have Sn, Λ ∈ ˆEn, and also many other means defined previously. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces Quasi-subgradient methods on NPC spaces Given a convex optimization problem on a Riemannian manifold: f ∗ = inf f (x) ◮ v is called a subgradient of f (x) at x if f (γ(t)) ≥ f (x) + ˙γ(0), v t for all geodesic γ(0) = x and t ∈ [0, b] a subgradient method is based on by obtaining an inequality of the form δ(xk+1, x∗ )2 ≤ δ(xk , x∗ )2 − tk+1(f (xk) − f (x∗ )) + 2t2 k+1C2 Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces xk is generated incrementally xk+1 = expxk (−tk+1vk) where vk is a subgradient with tk → 0 and k tk = +∞ Lemma Let G ∈ En, a = (a1, . . . , an) ∈ Mn and ω = (w1, . . . , wn) ∈ ∆n. Let {tk}∞ k=1 ≥ 0 be a sequence of real numbers. Let x0 ∈ M and xk+1 = G(ω; xk#tk+1 a1, . . . , xk#tk+1 an). Then δ(xk+1, Λ(ω; a))2 ≤ (1 − tk+1)δ(xk , Λ(ω; a))2 − tk+1 n i=1 wi [δ(xk , ai )2 − δ(Λ(ω; a), ai )2 ] + t2 k+1 n i=1 wi δ(xk , ai )2 . Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces Theorem (Diminishing step-size rule) If the real sequence {tk}∞ k=1 ≥ 0 in the previous Lemma satisfies tk → 0 and tk = +∞ then the sequence xk → Λ(ω; a). Theorem (Constant step-size rule) If G ∈ ˆEn and the real sequence {tk}∞ k=1 ≥ 0 in the previous Lemma satisfies tk = t ∈ (0, 1], then ∃ limk→∞ xk = x and δ(Λn(ω; a), x) ≤ t 2 ∆(a). Let Gt(ω; a1, . . . , an) denote the limit point of the sequence xk in the above Theorem Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces Geometric power means ◮ the map f (x) = G(ω; x#ta1, . . . , x#tan) is a strict contraction for t ∈ (0, 1] with contraction coefficient (1 − t) Lemma Gt(ω; a1, . . . , an) is the unique solution of the equation x = G(ω; x#ta1, . . . , x#tan). Furthermore, the solution varies continuously over t ∈ (0, 1]. Definition Gt(ω; a1, . . . , an) is called the ω-weighted geometric G-power mean of a1, . . . , an of order t. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces Proposition Gt ∈ ˆEn for all t ∈ (0, 1]. Moreover, δ2 (x, Gt(ω; a)) ≤ n i=1 wi δ2 (x, ai ) − (1 − t) n i=1 wi δ2 (Gt(ω; a), ai ) and δ2 (Gt(ω; a), Gt(ω; b)) ≤ δ(Gt(ω; a), Gt(ω; b)) n i=1 wi δ(ai , bi ) +t ∆(a)2+∆(b)2 2 , δ2 (Gt(ω; a), Gs (µ; a)) ≤ δ(Gt(ω; a), Gs (µ; a))∆(a) n i=1 |wi − ui | +s+t 2 ∆(a)2 for all ω = (w1, . . . , wn), µ = (u1, . . . , un) ∈ ∆n, a = (a1, . . . , an), b = (b1, . . . , bn) ∈ Mn and x ∈ M. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Quasi-subgradient methods on NPC spaces Theorem We have limt→0+ Gt(ω; a) = Λ(ω; a). We have a semigroup property: Proposition Let G ∈ En. Then [Gt]s = Gts for all t, s ∈ (0, 1]. The following result provides a characteristic property of the Karcher mean among members in ˆEn : Theorem For all t ∈ [0, 1], [Λn]t = Λn. Moreover for G ∈ ˆEn, Λn = G iff Gt = G for some t ∈ [0, 1] iff Gt = G for all t ∈ [0, 1]. ◮ The Karcher mean is the ”center” of ˆEn. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P Applications on the NPC space P Many properties of the Karcher mean Λ(ω; A) were unknown on P only very recently. On P one has the partial positive definite order: A ≤ B iff B − A ∈ P. ◮ Question: Is Λ(ω; A) monotone, i.e. Ai ≤ Bi → Λ(ω; A) ≤ Λ(ω; B)? The following properties for A#tB = A1/2(A−1/2BA−1/2)tA1/2 are well known: Proposition The map #t satisfies the following properties for any t ∈ (0, 1) on P: (P1) A#tB = A1−tBt if A, B commute; (P2) (aA)#t(bB) = a1−tbtA#tB for a, b > 0 real numbers; Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P (P3) A#tB = B#(1−t)A; (P4) If Bi ≤ Ai for all 1 ≤ i ≤ 2, then B1#tB2 ≤ A1#tA2; (P5) δ(A1#tA2, B1#tB2) ≤ (1 − t)δ(A1, B1) + tδ(A1, B1); (P6) (M∗AM)#t(M∗BM) = M∗A#tBM for any invertible M; (P7) ((1 − u)A1 + uB1)#t((1 − u)A2 + uB2) ≥ (1 − u)A1#tB1 + uA2#tB2 for 0 ≤ u ≤ 1; (P8) (A−1)#t(B−1) = (A#tB)−1; (P9) DetA#tB = (DetA)1−t(DetB)t; (P10) [(1 − t)A−1 + tB−1]−1 ≤ A#tB ≤ (1 − t)A + tB; (P11) Φ(A#tB) ≤ Φ(A)#tΦ(B) for any positive unital linear map Φ. If Φ is strictly positive, then Φ(A#tB) = Φ(A)#tΦ(B). By induction one can show the following properties of the inductive mean: Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P Corollary The weighted inductive mean satisfies the following properties on P: (P1) (Consistency with scalars) Sn(ω; A) = Aw1 1 · · · Awn n if the Ai ’s commute; (P2) (Joint homogeneity) Sn(ω; a1A1, . . . , anAn) = aw1 1 · · · awn n Sn(ω; A) for ai > 0 real numbers; (P3) (Monotonicity) If Bi ≤ Ai for all 1 ≤ i ≤ n, then Sn(ω; B) ≤ Sn(ω; A); (P4) (Contractivity) δ(Sn(ω; A), Sn(ω; B)) ≤ n i=1 wi δ(Ai , Bi ); (P5) (Invariancy) Sn(ω; M∗AM) = M∗Sn(ω; A)M for any invertible M; Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P (P6) (Joint concavity) Sn(ω; (1 − u)A + uB) ≥ (1 − u)Sn(ω; A) + uSn(ω; B) for 0 ≤ u ≤ 1; (P7) (Self-duality) Sn(ω; A−1 1 , . . . , A−1 n )−1 = Sn(ω; A1, . . . , An); (P8) (Determinant identity) DetSn(ω; A) = n i=1(DetAi )wi ; (P9) (AGH weighted mean inequalities) ( n i=1 wi A−1 i )−1 ≤ Sn(ω; A) ≤ n i=1 wi Ai ; (P10) Φ(Sn(ω; A)) ≤ Sn(ω; Φ(A)) for any positive unital linear map Φ. If Φ is strictly positive, then Φ(Sn(ω; A)) = Sn(ω; Φ(A)). Then using our approximation Theorem we get: Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P Theorem The Karcher mean Λ(ω; A) satisfies the following properties on P: (P1) (Consistency with scalars) Λ(ω; A) = Aw1 1 · · · Awn n if the Ai ’s commute; (P2) (Joint homogeneity) Λ(ω; a1A1, . . . , anAn) = aw1 1 · · · awn n Λ(ω; A) for ai > 0 real numbers; (P3) (Permutation invariance) Λ(ωσ; Aσ) = Λ(ω; A), where ωσ = (wσ(1), . . . , wσ(n)); (P4) (Monotonicity) If Bi ≤ Ai for all 1 ≤ i ≤ n, then Λ(ω; B) ≤ Λ(ω; A); (P5) (Contractivity) δ(Λ(ω; A), Λ(ω; B)) ≤ n i=1 wi δ(Ai , Bi ); Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces Applications on the NPC space P (P6) (Invariancy) Λ(ω; M∗AM) = M∗Λ(ω; A)M for any invertible M; (P7) (Joint concavity) Λ(ω; (1 − u)A + uB) ≥ (1 − u)Λ(ω; A) + uΛ(ω; B) for 0 ≤ u ≤ 1; (P8) (Self-duality) Λ(ω; A−1 1 , . . . , A−1 n )−1 = Λ(ω; A1, . . . , An); (P9) (Determinant identity) DetΛ(ω; A) = n i=1(DetAi )wi ; (P10) (AGH weighted mean inequalities) ( n i=1 wi A−1 i )−1 ≤ Λ(ω; A) ≤ n i=1 wi Ai ; (P11) Φ(Λ(ω; A)) ≤ Λ(ω; Φ(A)) for any positive unital linear map Φ. If Φ is strictly positive, then Φ(Λ(ω; A)) = Λ(ω; Φ(A)). Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces The case of general lsc convex functions The case of general lsc convex functions Let f := n i=1 fi be a geodesically convex function with fi : M → (−∞, ∞] geodesically convex lower semicontinuous (lsc) functions Definition A resolvent of f is defined by Jf λ(x) := arg miny∈M f (y) + 1 2λ δ(x, y)2 , for any x ∈ M and λ > 0. ◮ if f is lsc convex, then Jf λ : M → M is well-defined, non-expansive Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces The case of general lsc convex functions let x∗ denote the unique minimizer of f Lemma Let G ∈ En and {tk}∞ k=1 ≥ 0 be a sequence of real numbers. Let x0 ∈ M and xk+1 = G(ω; Jf1 tk+1 (xk), . . . , Jfn tk+1 (xk)). Suppose there exists L > 0 s.t. fi (xk ) − fi (xk+1) ≤ Lδ(xk , xk+1). Then δ(xk+1, x∗ )2 ≤ δ(xk , x∗ )2 − 2tk+1[f (xk) − f (x∗ )] + 4t2 k+1nL2 . Suppose that M is locally compact. Then: Theorem (Diminishing step-size rule) If the real sequence {tk}∞ k=1 ≥ 0 in the previous Lemma satisfies tk → 0, tk = +∞ and t2 k < +∞ then the sequence xk → x∗. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces The case of general lsc convex functions Some open problems: ◮ Is the law of large numbers true in CAT(k) spaces? ◮ Is the nodice Theorem true in CAT(k) spaces? ◮ How about for general lsc convex functions? ◮ CLT in NPC spaces? Do we have new attractor distributions? Note: we already have the law of large numbers. Deterministic walks and quasi-subgradient methods for the Karcher mean on NPC spaces The case of general lsc convex functions Thank you for your kind attention!