Upgrade to PRO for Only $50/Year—Limited-Time Offer! 🔥

Xue-Mei Li (École Polytechnique Fédérale de Lau...

Jia-Jie Zhu
March 27, 2024
140

Xue-Mei Li (École Polytechnique Fédérale de Lausanne, Switzerland) Coarse Extrinsic Curvature

WORKSHOP ON OPTIMAL TRANSPORT
FROM THEORY TO APPLICATIONS
INTERFACING DYNAMICAL SYSTEMS, OPTIMIZATION, AND MACHINE LEARNING
Venue: Humboldt University of Berlin, Dorotheenstraße 24

Berlin, Germany. March 11th - 15th, 2024

Jia-Jie Zhu

March 27, 2024
Tweet

More Decks by Jia-Jie Zhu

Transcript

  1. Coarse Extrinsic Curvature Xue-Mei Li EPFL & Imperial College London

    Workshop on Optimal Transport 13 March 2024
  2. Curvature There are two types of curvatures in Riemannian geometry:

    intrinsic and extrinsic. Intrinsic curvature is determined entirely by the manifold itself, independent of any surrounding space. The curvature operator R is a funda- mental intrinsic object. It measures how the sequence of differentiation in two directions fails to commute: R(X, Y )Z := ∇X (∇Y Z) − ∇Y (∇X Z), This operation involves the covariant derivative ∇, allowing to differentiate vector fields.
  3. Covariant Derivative and parallel transport For a geodesic γ(t) =

    exp(tv), the covariant derivative of a vector field U along γ is defined as: ∇v U := lim t→0 / /−1 t (γ)U(γt ) − U(x) t . / /t denotes “parallel transporting” a vector along the curve γ. Transporting map uses also parallel transport: w ∈ Tx0 M → / /1 (γ)(w) ∈ Ty M, where γ(t) = exp(tδv) and y = γ(1).
  4. Ricci Curvature The Ricci curvature of a Riemannian manifold measures

    how the volume of geodesic balls changes, which underpins Ollivier’s formulation of the ’Coarse Ricci curvature’: Consider the measures: dµε x (z) = 1Bε(x) (z) vol(Bε (x)) dvol(z). The transport cost would be measured by the Ricci curvature. Ollivier’s Claim: For any point x0 ∈ M, y := expx0 (δv) ( v ∈ Tx0 M is a unit vector, δ, ε > 0 sufficiently small): . W1 (µε x0 , µε y ) = δ 1 − ε2 2(n + 2) Ricx0 (v, v) + O(δ2ε2) + O(δε3)
  5. Ollivier’s coarse Ricci Curvature W1 (µε x0 , µε y

    ) = δ 1 − ε2 2(n + 2) Ricx0 (v, v) + O(δ2ε2) + O(δε3) Ollivier’ has essentially proved his claim in an article, JFA 2009, he defines the coarse curvature at scale ε as κε (x0 , y) := 1 − W1 (νε x0 , νε y ) d(x0 , y) lim ε,δ→0 2(n + 2) ε2 κε (x0 , y) = Ricx0 (v, v).
  6. Why define another notion of Ricci curvature? 1 In spaces

    lacking a smooth manifold structure, the conventional notion of Ricci curvature cannot be applied. For metric spaces where we can define coarse curvature, demonstrating consistency in the limit would be advantageous. This approach extends the applicability of curvature concepts beyond smooth manifolds. 2 This framework provides a method for estimating Ricci curvature from empirical data. An article by P. van der Hoorn, G. Lippner, C. Trugenberger, and D. Krioukov has reasonable success. They showed that the coarse curvature of the random geometric graph sampled from a uniform Poisson point process on a Riemannian manifold converges in expectation to the smooth Ricci curvature as the intensity of the process increases.
  7. Extrinsic Curvature Extrinsic Curvature is a concept we often aim

    to bypass when examining Riemannian manifolds due to its dependency on the embedding space. However, in imaging science, one wants to learn the ’shape of the ob- ject’ based on the data, essentially tackling an inverse problem. The Second Fundamental Form serves as a pivotal tool in this regard. For example, a surface in R3 can be locally isometric to a plane if, and only if, its Second Fundamental Form is null.
  8. The second fundamental form Let M be embedded in a

    manifold N, x ∈ M. Then I Ix (w, w) := ∇N w W(x) − ∇M w W(x) where W is an arbitrary vector field on M, W(x) = w. A more familiar object is the mean curvature. Let (ei )m i=1 is a local orthonor- mal frame around x. Hx := m i=1 ∇N ei ei (x) − ∇M ei ei (x).
  9. Introducing Collaborators Ooups... That Gaussian curve. This is the only

    randomness I will manage to squeeze in, in this talk. No stochastic analysis.
  10. Joint work with Figure: Marc Arnaudon Figure: Ben Petico Preprint:

    Coarse Ricci Curvature of Weighted Riemannian Manifolds; Coarse Extrinsic Curvature of Riemannian Manifolds; (In preparation)
  11. Extending coarse ricci curvature dνε x (z) := 1Bε(x) (z)

    e−V (z) Bε(x) e−V (z′)dvol(z′) dvol(z). Theorem [Arnaudon-Li-Petico-1]: x0 ∈ M, y := expx0 (δv), v ∈ Tx0 M, ∥v∥ = 1 and δ, ε > 0 sufficiently small, W1 (νε x0 , νε y ) =δ 1 − ε2 2(n + 2) (Ricx0 (v, v) + 2Hessx0 V (v, v)) + O(δ2ε2) + O(δε3)
  12. Approximate transport map ¯ νε x0 x0 ∇V (x0 )

    T∗ ¯ νε x0 ∼ ¯ νε y y ∇V (y) T∗ M ˜ T(w) := / /1 w − 1 2 (ε2 − ∥w∥2)(∇V (y)− / /1 ∇V (x0 )).
  13. A visual sketch proof 0 Tx0 M (expx0 )∗ ˜

    νε x0 ε 0 Ty M (expy )∗ ˜ νε y ε M x0 ¯ νε x0 T∗ M y T∗ ¯ νε x0 ∼ ¯ νε y
  14. Random geometric graphs Following Hoorn et al : Starting from

    a random measure (with a weight which we do not write here): P : Ω × B → [0, ∞]. Construct a Poisson point process: Nk Poisson random variable distributed as Poisson (µ(Wk )), Wk a partition of manifold of finite measure. X(k) i distributed as normalized µ restricted to Wk , all independent. P(k) : Ω → M(X), ω → Nk(ω) i=1 δ X(k) i (ω) . P := ∞ k=1 P(k) A random geometric graph sampled from P with roots x0 , y and connectivity radius ε > 0 is the weighted graph denoted by G(x0 , y, ε) with nodes given by V(ω) = {X(k) i (ω) : 1 ≤ i ≤ Nk (ω), k ∈ N} ∪ {x0 , y} Increase intensity.
  15. Poisson Cloud – Random Graph Theorem [Arnaudon-Li-Petico-1]: Let κn (x0

    , y) be the graph curvatures corresponding to the rooted random graphs Gn (x0 , yn , εn ) with yn = expx0 (δn v) generated by the sequence of Poisson processes with intensity measures ne−V (z)+V (x0)vol(dz) under suitable assumptions, there exists (cn )n∈N such that limn→∞ cn = 0 and E WGn 1 (ηδn x0 , ηδn yn ) − W1 (νδn x0 , νδn yn ) ≤ cn δ3 n (1) which implies lim n→∞ E 2(N + 2) δ2 n κn − (Ricx0 (v, v) + 2Hessx0 V (v, v)) = 0. (2)
  16. Test Measures for extrinsic curvature The remaining of the slides

    are based on Arnaudon-Li-Petico-2. Consider γ : (−δ0 , δ0 ) → R2 – a smooth, unit speed planar curve; n : (−δ0 , δ0 ) → R2– a unit normal vector field along γ. R(α) := 1 ∥¨ γ(α)∥ – the radius of the osculating circle at the point γ(α). M := γ((−δ0 , δ0 )); Mσ0 - a tubular neighbourhood of M, or- thogonal projection π : Mσ0 → M ; dγ – the distance along γ; σ ∨ ε ≤ δ 4 Bσ,ε (y) := {z ∈ R2 : ∥z − π(z)∥ < σ, dγ (y, π(z)) < ε}. µσ,ε y (A) := Leb(A ∩ Bσ,ε (y)) Leb(Bσ,ε (y)) , A ∈ B(R2)
  17. Test Measures for extrinsic curvature M is embedded isometrically in

    a Euclidean space Rd; Mσ is the σ-tubular neighbourhood of M in Rd. Bε (x) is the ε-geodesic ball in M. µσ,ε x (A) = µ(π−1(Bε (x)) ∩ A ∩ Mσ ), A ∈ B(Rd). (The constants are chosen so that these measures are supported on compact slices of Mσ .)
  18. Examples: Plane curve, curve on surfaces Let γ be a

    smooth unit speed curve in R2, γ(0) = x0 , γ(δ) = y. Then, for all δ, ε, σ > 0 sufficiently small with σ ∨ ε ≤ δ 4 : W1 (µσ,ε x0 , µσ,ε y ) = ∥x0 − y∥ 1 − ε2 6R2 + σ2 3R2 + O(δ4) where R is the radius of the osculating circle of the curve at x0 .
  19. Coarse Second Fundamental Form Let (ej )m j=1 be an

    orthonormal basis of Tx0 M with e1 = ˙ γ(0). Let γ be a unit speed geodesic in M such that γ(0) = x0 and γ(δ) = y. For every σ, ε, δ > 0 sufficiently small with σ ∨ ε ≤ δ 4 it holds that W1(µσ,ε x0 , µσ,ε y ) = ∥y − x0∥  1 − ε2 2(m + 2)  ⟨I Ix0 (e1, e1), Hx0 ⟩ − m j=2 ∥I Ix0 (e1, ej)∥2   + σ2 k + 2  ⟨I Ix0 (e1, e1), Hx0 ⟩ + 1 2 m j=2 ∥I Ix0 (e1, ej)∥2     + O(δ4).
  20. A mean curvature version Let (ej )m j=1 be an

    orthonormal basis of Tx0 M, and for j = 1, . . . , m. yj = expM,x0 (δej ). For all σ, ε, δ > 0 sufficiently small with σ ∨ ε ≤ δ 4 it holds that m j=1 1 − W1 (µσ,ε x0 , µσ,ε yj ) ∥x0 − yj ∥ = − σ2 2(k + 2) (∥Hx0 ∥2 + ∥I Ix0 ∥2) + ε2 2(m + 2) 2∥Hx0 ∥2 − ∥I Ix0 ∥2 + O(δ3).
  21. On the circle For all δ, ε, σ > 0

    sufficiently small with σ ∨ ε ≤ δ 2 , it holds that W1 (µσ,ε x0 , µσ,ε y ) = 2R2 sin δ 2R 1 ε sin ε R 1 + σ2 3R2 = ∥x0 − y∥ R ε sin ε R 1 + σ2 3R2 . x0 y
  22. Work with polar coordinates Take a circle S1 of radius

    R. The polar coordinates: φ(α, β) := (R − β) cos(α/R) (R − β) sin(α/R)) , α ∈ (−πR, πR) x0 y φ(40, 0.5) R − 0.5 55 α parametrizes arc-length distance from the point (R, 0) along the circle and β ∈ (−σ, σ) parametrizes the direction normal to the circle.
  23. The text measure in polar coordinates Denote x0 := φ(0,

    0) = (R, 0), denote y := R cos(δ/R) R sin(δ/R)) . The test measures in polar coordinates take the form (φ−1 ∗ µσ,ε y )(dα, dβ) = 1 4σε 1(δ−ε,δ+ε)×(−σ,σ) (α, β) 1 − β R dαdβ. x0 y z Tz Define a transport map: T(φ(α, β)) = φ(δ−α, β).
  24. The proposed map is a transport map T(φ(α, β)) =

    φ(δ − α, β) = (R − β) cos((δ − α)/R) (R − β) sin((δ − α)/R) , Note y = Tx0 , T∗ µσ,ε x0 = µσ,ε y . f(z)d(T∗ µσ,ε x0 )(z) = f(Tz)dµσ,ε x0 (z) = f(T(φ(α, β)))d(φ−1 ∗ µσ,ε x0 )(dα, dβ) = 1 4σε f(T(φ(α, β)))1(−ε,ε)×(−σ,σ) (α, β) 1 − β R dαdβ = 1 4σε f(φ(α, β))1(δ−ε,δ+ε)×(−σ,σ) (α, β) 1 − β R dαdβ = f(z)dµσ,ε y (z).
  25. upper bound Proof: If z = φ(α, β), ∥Tz −

    z∥ = 2(R − β) sin δ − 2α 2R . W1 (µσ,ε x0 , µσ,ε y ) ≤ ∥Tz − z∥dµσ,ε x0 (z) ≤ 2R2 sin δ 2R 1 ε sin ε R 1 + σ2 3R2 .
  26. lower bound For the lower bound, we test against the

    1-Lipschitz function f(z) := ⟨z − x0 , y − x0 ∥y − x0 ∥ ⟩. W1 (µσ,ε x0 , µσ,ε y ) ≥ f(z)(dµσ,ε y (z) − dµσ,ε x0 (z)) = (f(Tz) − f(z))dµσ,ε x0 (z) = ∥Tz − z∥dµσ,ε x0 (z),
  27. Main References (1) Yann Ollivier. Ricci curvature of Markov chains

    on metric spaces. J. Funct. Anal., 256(3):810–864, 2009. (2) Pim van der Hoorn, Gabor Lippner, Carlo Trugenberger, and Dmitri Krioukov. Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds. Discrete Comput. Geom., 70(3):671–712, 2023.