{'fraction_non_alphanumeric': 0.040274290129418584, 'fraction_numerical': 0.01583928916360827, 'mean_word_length': 4.1775, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximated logarithmic maps on Riemannian manifolds and their applications

Recently, optimization problems on Riemannian manifolds involving geodesic distances have been attracting considerable research interest. To compute geodesic distances and their Riemannian gradients, we can use logarithmic maps. However, the computational cost of logarithmic maps on Riemannian manifolds is generally higher than that on the Euclidean space. To overcome this computational issue, we propose approximated logarithmic maps. We prove that the deﬁnition is closely related to the inverse retractions. Numerical experiments for computing the Riemannian center of mass show that the proposed approximation signiﬁcantly reduces the computational time while maintaining appropriate precision if the data diameter is suﬃciently small.


Introduction
In recent years, optimization problems on Riemannian manifolds, especially on matrix manifolds, such as the manifold of symmetric positive definite matrices (SPD manifold) and Grassmann manifold, have gained attention in applications to machine learning. Among them, algorithms using the geodesic distance have been proposed in the studies of clustering on Riemannian manifolds [1], dictionary learning and sparse coding [2], and kernel methods [3].
If a Riemannian manifold M is geodesically complete, then the geodesic distance between any two points X, Y ∈ M can be computed as dist(X, Y ) = log X Y X , where log X denotes the Riemannian logarithmic map at X, and · X denotes a norm at X derived from the Riemannian metric [4]. Let dist 2 Y (·) := dist 2 (·, Y ) be the squared distance function from a fixed point Y . Then, we can compute the Riemannian gradient of dist 2 Y as grad dist 2 Y (X) = −2 log X Y using the logarithmic map. However, the computational cost of the logarithmic map on M is generally high. For instance, the logarithmic map on the SPD manifold is given as log X Y = X 1/2 Log X −1/2 Y X −1/2 X 1/2 , where Log is the matrix logarithmic function, which is more complex than the map on R n , i.e., log x y = y − x.
In this study, we newly define the concept of an approximated logarithmic map on Riemannian manifolds. We attempt to reduce the computational time required to solve optimization problems involving the logarithmic map. In addition, we verify the usefulness of the approximation by numerical experiments on the computation of the Riemannian center of mass [5].
The outline of this paper is as follows. Section 2 pro-vides preliminaries of Riemannian manifolds. In Section 3, we present the approximated logarithmic map and some examples. Applications of logarithmic maps to the computation of geodesic mean are proposed in Section 4. Numerical experiments are described in Section 5. Finally, Section 6 concludes this paper.

Preliminaries
In this section, we introduce the fundamental concepts of Riemannian manifolds and optimization before defining and discussing the approximated logarithmic map. For more details, one can refer to [4,6].
A Riemannian manifold is a couple (M, g), where M is a C ∞ manifold and g is a Riemannian metric. This metric induces an inner product in each tangent space T X M at every X ∈ M. We denote the inner product of U, V ∈ T X M by g X (U, V ), and the norm of U ∈ T X M is defined by U X := g X (U, U ) 1/2 .
For every U ∈ T X M, there exists an interval I around 0 and a unique geodesic γ(t; X, U ) : I → M that satisfies γ(0; X, U ) = X andγ(0) = U . The exponential map at X ∈ M is defined through this geodesic as The inverse of the exponential map is called a logarithmic map, which is denoted by log X at X ∈ M. If a manifold M is geodesically complete, i.e., the exponential map exp X is defined at any point X ∈ M for any tangent vector in T X M, the geodesic distance between X, Y ∈ M can be computed as dist(X, Y ) = log X Y X .
The update formula of line-search methods on R n is written as x t+1 = x t + c t u t , where u t is in R n and c t is a positive step size. However, on Riemannian manifold M, this formula cannot be applied due to the nonlinearity of M. Instead, the update is formulated as where U t ∈ T Xt M is a search direction, c t is a positive step size, and R X is a mapping called retraction defined as follows [6, Definition 4.1.1].

Definition 1 (Retraction) A retraction on a manifold
M is a smooth mapping R from the tangent bundle T M to M with the following properties. Let R X denote the restriction of R to T X M.

Approximated logarithmic map
In this section, we define the approximated logarithmic map following the definition of a retraction, and we introduce its properties and examples.

Definition 2 (Approximated logarithmic map) Let X be an arbitrary point on a Riemannian manifold M. An approximated logarithmic map at X is a smooth mapping R †
X from M onto the tangent space T X M with the following properties: We originally proposed the concept of an approximated logarithmic map in a domestic conference [7]. In [8], Schiela and Ortiz independently proposed a similar concept, which they call stratification. Note that we require an approximated logarithmic map to be a smooth mappings following the definition of a retraction in [6] while Schiela and Ortiz defined a stratification as a C 2 -mapping.
Using Definitions 1 and 2 and the inverse function theorem [9], we can prove that the inverse retraction is locally equivalent to the approximated logarithmic map and vice versa, as the following theorems imply. ( (

(QED)
In particular, since the exponential map is a kind of retraction, the logarithmic map satisfies Definition 2 from Theorem 3.
We show examples of geodesic distances, logarithmic maps, and their approximations on the SPD manifold: Sym + d := X ∈ R d×d | X = X ⊤ , X O , and the Grassmann manifold: G r n := span(X) | X ∈ R n×r , X ⊤ X = I r . To compare the computational costs of the logarithmic map and its approximation, we count floating point operations (flops) used in [10].

Example 5 (Logarithmic map and its approximation on
The logarithmic map on Sym + d is given as follows [11]: . From the Riemannian metric on X ∈ Sym + d that is defined by g X (U, V ) = tr X −1 U X −1 V , we can compute the geodesic distance between X and Y as

Whereas we define
which satisfies the two conditions of Definition 2 and is thus an approximated logarithmic map on Sym + d . This follows from its directional derivative: . Example 6 (Logarithmic map and its approximation on G r n ) We use an orthonormal matrix X ∈ R n×r to represent a point on G r n , which is the equivalence class of X. Let X, Y be representations of points on G r n . The logarithmic map on G r n is given as where (U, Σ, V ) is the solution of the following equation [12]: The solution is obtained by the singular value decomposition (SVD): From the Riemannian metric on X ∈ G r n that is defined by g X (U, V ) = tr U ⊤ V , we can compute the geodesic distance between X and Y as dist(X, Y ) = arccos (diag Σ) 2 .

Whereas we define
which is an inverse map of the retraction: where qf(·) denotes the map which returns the Q factor of its QR decomposition [6,Example 4.1.2]. From Theorem 3, R † X is an approximated logarithmic map on G r n . Compared with the logarithmic map, we can avoid the SVD computation by this approximation.

Application to geodesic mean
This section introduces the optimization problem to compute the Riemannian center of mass as an application of approximated logarithmic maps. The geodesic mean of N points A 1 , A 2 , . . . , A N ∈ M is computed as the solution to the following optimization problem: Calculate c t > 0.
4: The gradient grad f (X) of the objective function f at X ∈ M is computed by the following formula [5]: Adapting − grad f (X) as the search direction leads to the gradient descent algorithm (Algorithm 1). By replacing the logarithmic map with its approximation, we approximate the gradient as and we obtain Algorithm 2.

Numerical Experiments
In this section, we address the Riemannian mean problem on Sym + 10 and G 20 1000 using Algorithms 1 and 2, i.e., the gradient descent (GD) and approximated gradient descent (AGD) algorithms introduced in the previous section. All the experiments were implemented in Python 3.7.3 and run on 2.3 GHz dual-core Intel Core i5.

Parameters and datasets
The step size c t is set to a constant, selected from {1, 0.1}. Both algorithms are terminated when the number of iterations reaches 300. Datasets are generated using random values according to Algorithms 3 and 4. The number of data points is set to 30. Table 1 shows the 10-time average of the computational time to compute the Riemannian center when

Algorithm 3 Random-valued data on Sym
where Exp is the matrix exponential function. 4: return X.
the step size is selected as c t = 0.1 and the parameter σ in Algorithms 3 and 4 is set to 1. We can observe that the computational time is significantly reduced by the approximation in both Sym + 10 and G 20 1000 . Especially on Sym + 10 , the ratio of the computational time is 1.02435/0.34560 ≈ 2.96398, which is close to the theoretical ratio (31/3)/(10/3) = 3.1 described in Section 3.

Precision of approximation
We conducted several experiments while changing the data diameter (maximum distance between points) by selecting σ > 0 from [0.01, 1] in Algorithms 3 and 4. Fig. 1 shows the results of objective function values. We can observe that the approximation works well if the data diameter is sufficiently small. However, when the diameter exceeds 3 in Sym + 10 or exceeds 6.3 in G 20 1000 , the objective function values of AGD are higher than those of GD because of the approximation error.

Conclusion
In this paper, we newly proposed the approximated logarithmic maps on Riemannian manifolds and proved their relation with retractions, which are approximations of the exponential maps. Our approach allows algorithms that require inverse retractions (such as [13]) to use approximated logarithmic maps instead even without knowing the retraction itself.
In addition, the Riemannian center of mass is appropriately computed using the approximation if the data diameter is sufficiently small. In future works, convergence and error bounds should be analyzed to confirm the results. Performing numerical experiments with realworld data (instead of random-valued data) is also a future task.