remresetThe remreset package

# Trivializations for Gradient-Based
Optimization on Manifolds

Mario Lezcano-Casado
Department of Mathematics
University of Oxford
Oxford,
<EMAIL_ADDRESS>

###### Abstract

We introduce a framework to study the transformation of problems with manifold
constraints into unconstrained problems through parametrizations in terms of a
Euclidean space. We call these parametrizations _trivializations_. We prove
conditions under which a trivialization is sound in the context of gradient-
based optimization and we show how two large families of trivializations have
overall favorable properties, but also suffer from a performance issue. We
then introduce _dynamic trivializations_ , which solve this problem, and we
show how these form a family of optimization methods that lie between
trivializations and Riemannian gradient descent, and combine the benefits of
both of them. We then show how to implement these two families of
trivializations in practice for different matrix manifolds. To this end, we
prove a formula for the gradient of the exponential of matrices, which can be
of practical interest on its own. Finally, we show how dynamic trivializations
improve the performance of existing methods on standard tasks designed to test
long-term memory within neural networks.111An implementation can be found at:
https://github.com/Lezcano/expRNN

##  1 Introduction

Constrained optimization allows to put restrictions on the family of objects
being optimized. When the restrictions are simple, for example, having a
vector with entries in $[0,1]$ or $[-1,1]$, simple element-wise
parametrizations using sigmoid functions or $\tanh$ allow the design of
powerful models such as lstm [Hochreiter and Schmidhuber, 1997] and gru [Cho
et al., 2014] through the method of _gating_. This kind of vector-
regularization is now standard, and most of the advanced neural network
architectures use it as a basic building block [Bahdanau et al., 2014].
Constraints on matrices, on the other hand, are much more challenging.

Most of the interesting sets of matrices turn out to have a manifold
structure. Optimization on manifolds is both theoretically and practically
challenging due to the inherent complexity of the objects involved. Even then,
optimization on matrix manifolds has proven to be rather useful in many
different subfields of machine learning and neural networks (nn). Examples of
interesting matrix manifolds in the context of gradient-based optimization are
the set of positive definite matrices in Bayesian statistics [Rasmussen and
Williams, 2005], orthogonal matrices within rnns [Arjovsky et al., 2016,
Helfrich et al., 2018, Lezcano-Casado and Martínez-Rubio, 2019], nns with
structured linear layers via the qr or the svd decomposition [Berg et al.,
2018, Zhang et al., 2018, Kingma and Dhariwal, 2018], or invertible matrices
in normalizing flows [Berg et al., 2018] and vaes [Tomczak and Welling, 2016].

In this paper we aim to provide a theoretically sound but also efficiently
implementable framework to perform optimization on these and other matrix
manifolds in the context of gradient-based optimization.

##### Outline of the paper and summary of the main contributions

In this paper, we study parametrizations of the form
$\phi\colon\mathbb{R}^{n}\to\mathcal{M}$.

We consider the transformation of a constrained optimization problem into an
unconstrained one.

$\text{Initial problem:
}\min_{x\in\mathcal{M}}f(x)\qquad\quad\text{Unconstrained problem:
}\min_{y\in\mathbb{R}^{n}}f(\phi(y)).$

We call this process _trivialization_ and we say that $\phi$ is a
trivialization map. In Section 4, we show that whenever $\phi$ is regular
enough— a diffeomorphism—these parametrizations act as a change of metric on
$\mathcal{M}$, and thus, applying gradient descent to this new problem is
equivalent to performing rgd on the original problem with this new metric, for
which standard convergence results hold.

After this, we look at two large families of parametrizations, the Riemannian
exponential, and the Lie exponential. We analyze these from the point of view
of the framework presented before, and we point out a problem that they
present: they may create saddle points or local minima when near certain
region in the manifold.

In Section 5, we introduce _dynamic trivializations_. They can be described as
follows:

##### Main idea:

Lift the function $f$ to the current tangent space $T_{x_{i}}\mathcal{M}$
using a map $\phi_{x_{i}}\colon T_{x_{i}}\mathcal{M}\to\mathcal{M}$ by
considering the trivialization $f\circ\phi_{x_{i}}$ (think
$\phi_{x_{i}}=\exp_{x_{i}}$, or, for efficiency, any retraction). Optimize
$f\circ\phi_{x_{i}}$ on $T_{x_{i}}\mathcal{M}$ for a while using any standard
optimization methods like adam, rmsprop, or adagrad, since
$T_{x_{i}}\mathcal{M}$ is a linear space. When we are at a point $y_{k}\in
T_{x_{i}}\mathcal{M}$ on which $\phi_{x_{i}}$ might create saddle-points or
local minima, then we consider the current point in the manifold
$x_{i+1}\coloneqq\phi_{x_{i}}(y_{k})$ and we start optimizing the function
$f\circ\phi_{x_{i+1}}$, , lift the problem to $T_{x_{i+1}}\mathcal{M}$.

This family of methods has Riemannian gradient descent and classic
trivializations as limit cases, and in particular, they combine the strengths
of the two. Furthermore, we show that these methods give a natural
generalization of Euclidean optimizers to manifolds.

In Section 6 we show how to compute the gradients associated to the Lie
exponential and some cases of the Riemannian exponential for matrix manifolds.
To this end, we compute a formula that allows for the approximation of the
gradient of the exponential of matrices to machine-precision. We also show
some examples of for how to use this theory to perform optimization on some
matrix manifolds. In Appendix E we compile an extended list of examples that
we hope might be helpful to the reader.

Finally, in Section 7 we show how dynamic trivializations improve previously
developed optimization techniques in the context of optimization with
orthogonal constraints.

##  2 Related Work

##### Optimization on manifolds.

Most of the results on optimization on manifolds have found analogues in the
Riemannian setting [Udriste, 1994, Absil et al., 2009]. Algorithms like
conjugate gradient descent or the Newton method were first devised for
specific families of manifolds [Smith, 1993, Edelman et al., 1998], and then
they were derived for general Riemannian manifolds [Bonnabel, 2013, Sato and
Iwai, 2015, Boumal et al., 2016].

Optimization methods on manifolds can be classified in two families: Those
that follow geodesics, and those that follow retractions—, first order
approximations to geodesics. In the first family, convergence rates have been
proven for most first order methods, both stochastic and non-stochastic [Zhang
and Sra, 2016], and even purely first-order accelerated methods [Zhang and
Sra, 2018]. When it comes to retractions, rates of convergence have been
proved in the Lipschitz setting for first and second-order methods [Boumal et
al., 2016].

##### Trivialization.

The trick of parametrizing a Lie group with elements in the Lie algebra
through the Lie exponential map has been commonly used under the name of
_trivialization_ in the area of differential equations on manifolds [Magnus,
1954, Iserles and Nørsett, 1999, Iserles et al., 2000]. We borrow the term, as
the general idea behind these methods and ours is rather similar.

##### Optimization through parametrizations.

Parametrizing a manifold in terms of a Euclidean space is a common technique
in optimization and machine learning. For example when doing computations on
symmetric positive definite matrices [Arsigny et al., 2006, 2007], compact Lie
groups [Lezcano-Casado and Martínez-Rubio, 2019], the special orthogonal group
[Helfrich et al., 2018] or the unitary group [Jing et al., 2017, Maduranga et
al., 2018]. In [Dreisigmeyer, 2018], it is used through the Riemannian
exponential to adapt 0th order methods to naturally reductive homogeneous
manifolds.

Our work finds the closest connections in the papers [Lezcano-Casado and
Martínez-Rubio, 2019, Helfrich et al., 2018, Maduranga et al., 2018] These
papers present the use of the Lie exponential and the Cayley map for
optimization on $\operatorname{SO}\lparen n\rparen$. Our framework can be seen
as an extension that can be implemented on top of them at a negligible
execution cost. We also show that this theoretical improvement translates into
a better convergence in practice in Section 7.

##  3 Problem Set-Up

We include a short introduction to the concepts used from differential and
Riemannian geometry in Appendix A.

We are interested in approximating the following problem over a connected
manifold $\mathcal{M}$

$\min_{x\in\mathcal{M}}f(x).$

A differentiable manifold does not carry intrinsically any metric information.
As such, if one is interested in talking about concepts like the distance to
the optimum, or the steepest descent direction, it is necessary to put
additional structure on the problem. One way to do this is to consider a
Riemannian metric g on $\mathcal{M}$, turning $\mathcal{M}$ into a Riemannian
manifold.

###  3.1 The classic approach: Riemannian gradient descent

Given a complete metric on $\mathcal{M}$, we can define geodesics
$\gamma_{p,v}\colon[0,\infty)\to\mathcal{M}$ such that $\gamma_{p,v}(0)=p$,
$\gamma^{\prime}_{p,v}(0)=v$ for $v\in T_{p}\mathcal{M}$. Then, the Riemannian
exponential map is defined simply as the map that maps rays starting at the
origin in the tangent space to geodesics on $\mathcal{M}$. In symbols,
$\exp_{p}(tv)\coloneqq\gamma_{p,v}(t)$ for $t\geq 0$.

Using the Riemannian exponential, one can define Riemannian gradient descent
in an analogous way to the Euclidean case:

$x_{t+1}=\exp_{x_{t}}(-\eta\nabla f(x_{t})).$

In plain words, the algorithm follows the geodesic defined by the direction of
steepest descent $-\nabla f(x_{t})$ for a time $\eta>0$. This approach has
been extensively studied in the literature and it has been proven to enjoy
similar convergence properties to its Euclidean counterpart [Absil et al.,
2009, Bonnabel, 2013, Boumal et al., 2016, Zhang et al., 2016].

Sometimes it is convenient, due to computational constraints, to use a first
order approximation to the exponential rather than the exponential map. This
idea is encapsulated in the concept of a retraction.

######  Definition 3.1 (Retraction).

A differentiable map $r\colon T\mathcal{M}\to\mathcal{M}$ is called a
retraction if for every $p\in\mathcal{M}$, the map $r_{p}\colon
T_{p}\mathcal{M}\to\mathcal{M}$ satisfies $r_{p}(0)=p$ and
$\lparen\mathrm{d}r_{p}\rparen_{0}=\mathrm{Id}$.

The update rule of Riemannian gradient descent along a retraction $r$ is then
given by

$x_{t+1}=r_{x_{t}}(-\eta\nabla f(x_{t})).$

In many cases, this update rule is enough to have the same convergence
properties as in Riemannian gradient descent along the exponential map [Boumal
et al., 2016].

The main problem of Riemannian gradient descent comes from a practical point
of view. On many practical problems, it has been empirically proved that
algorithms like adam [Kingma and Ba, 2014], adagrad [Duchi et al., 2011] or
rmsprop [Tieleman and Hinton, 2012] outperform vanilla sgd. These algorithms
were designed to work on $\mathbb{R}^{n}$, and although generalizations for
product manifolds are in order [, Becigneul and Ganea, 2019], it is not clear
how to generalize them to most manifolds used in practice, and thus take
advantage of them in the Riemannian setting.

##  4 Trivializations

We now introduce trivializations. Trivializations are functions that allow us
to transform a constrained problem on a manifold to an unconstrained one.

######  Definition 4.1 (Trivialization).

Given a manifold $\mathcal{M}$, we define a trivialization as a surjective map

$\phi\colon\mathbb{R}^{n}\to\mathcal{M}.$

######  Example 4.2.

The most simple examples are found when $\mathcal{M}$ has a product structure,
, for vectors. For example, for a fixed $n>0$, consider component-wise
functions like rectified linear units, parametrizing non-negative vectors
$\operatorname{relu}\colon\mathbb{R}^{n}\to\lparen\mathbb{R}^{+}\rparen^{n}$
or the sigmoid function $\sigma\colon\mathbb{R}^{n}\to[0,1]^{n}$.

Having a trivialization in hand, we can transform a constrained optimization
problem into an unconstrained one by composing $f$ with $\phi$.

$\min_{y\in\mathbb{R}^{n}}f(\phi(y)).$

######  Remark.

When considering a parametrization $\phi$, the gradient $\nabla f(x)$ changes
into the gradient $\nabla\lparen f\circ\phi\rparen(y)$ for $x=\phi(y)$. For a
$1$-dimensional trivialization, by the chain rule, if $\phi^{\prime}(y)=0$ for
many $y\in\mathbb{R}$, $\phi$ will not be a good parametrization, because then
$\nabla\lparen f\circ\phi\rparen(y)=\nabla f(\phi(y))\phi^{\prime}(y)=0$, even
though $\nabla f(x)$ might not be zero. As such, not all trivializations are
equally good.

We formalize this intuition for general trivializations in the following
theorem.

######  Theorem 4.3.

Let $\phi\colon\mathbb{R}^{n}\to\mathcal{M}$ be a diffeomorphism. Then,
solving the problem $\min_{y\in\mathbb{R}^{n}}f(\phi(y))$ through gradient
descent accounts for solving the problem $\min_{x\in\mathcal{M}}f(x)$ using
Riemannian gradient descent for a certain metric on $\mathcal{M}$ induced by
$\phi$.

###### Proof.

See Appendix B. ∎

This result tells us that, if $\phi$ is a diffeomorphism, $\phi$ will not add
local minima or saddle points. It will simply act as a change of metric on the
manifold. This already explains the good behavior of the $\tanh$ and sigmoid
functions present in an lstm or gru in the context of gating.

At first sight, the situation of $\phi$ being a diffeomorphism seems too
restrictive for general manifolds. We now introduce two parametrizations that
are diffeomorphisms in _almost all_ the manifold.222This is taken with respect
to the canonical Borel measure on the manifold induced by the metric.

###  4.1 The Riemannian trivialization

Consider now the Riemannian exponential map. By the Hopf-Rinow theorem, it is
surjective whenever $(\mathcal{M},\textsl{g})$ is connected and complete. As
such, in these cases, for any point $p\in\mathcal{M}$, the Riemannian
exponential map $\exp_{\mathcal{M},p}\colon
T_{p}\mathcal{M}\lparen\cong\mathbb{R}^{n}\rparen\to\mathcal{M}$ is an example
of a trivialization.

##### Geometric intuition about the Riemannian trivialization.

A direct corollary of Gauss’ lemma says that the metric induced by the
exponential parametrization $\exp_{\mathcal{M},p}$ is a first order
approximation to the metric on the manifold around the point $p$ [ Petersen,
2016, Lemma $5.5.7$]. In other words, the Riemannian trivialization changes
the metric into a new one with the square of the distance to $p$ for points
near $p$.

Let us now look at the behavior of the Riemannian trivialization in global
terms.

######  Theorem 4.4 (Properties of the Riemannian trivialization).

Let $(\mathcal{M},g)$ be a connected, complete Riemannian manifold. Fix a
point $p\in\mathcal{M}$. Let $U_{p}\subseteq T_{p}\mathcal{M}$ be the largest
radially convex open neighborhood of zero on which $\exp_{\mathcal{M},p}$ is a
diffeomorphism333A more formal way to define it would be
$\overline{U}_{p}\coloneqq\\{v\in T_{p}\mathcal{M}\>|\>\exp_{p}(tv)\text{ is
length minimizing for }t\in[0,1]\\}$. then,
$\exp_{\mathcal{M},p}(\overline{U}_{p})=\mathcal{M}$.

Furthermore, define the _cut locus in $T_{p}\mathcal{M}$_ as
$\tilde{C}_{p}\coloneqq\overline{U}_{p}\backslash U_{p}$. If $V\in
T_{p}\mathcal{M}$ is another open neighborhood of the origin that contains a
point in $\tilde{C}_{p}$, then $\exp_{\mathcal{M},p}$ is not a diffeomorphism
on $V$.

###### Proof.

See Section $5.7.3$ in [Petersen, 2016]. ∎

Theorem 4.4 combined with Theorem 4.3 tell us that there exists a radially
convex neighborhood of zero on which $\exp_{\mathcal{M},p}$ acts as a change
of metric, and that $\exp_{\mathcal{M},p}$ stops being a diffeomorphism in the
boundary—and hence, can add minima or saddle points at these points. As the
image of $\overline{U}_{p}$ is the whole $\mathcal{M}$, if we write
$C_{p}\coloneqq\exp_{\mathcal{M},p}\lparen\tilde{C}_{p}\rparen$, we have that
$\mathcal{M}$ decomposes in the disjoint union of
$\exp_{\mathcal{M},p}(U_{p})$ and $C_{p}$. The set $C_{p}$ is called the _cut
locus of $p$_.

The cut locus is a remarkably slippery object of study given that, in general,
it is not differentiable. Nonetheless, we can still measure the relative size
of this set in a topological sense, by means of the Hausdorff dimension.

######  Theorem 4.5 (Itoh and Tanaka [1998]).

Let $\mathcal{M}$ be a connected and complete Riemannian manifold of dimension
$n$. For a point $p\in\mathcal{M}$ the Hausdorff dimension of $\tilde{C}_{p}$
is either $0$ or $n-1$, and the Hausdorff dimension of $C_{p}$ is an integer
less than $n$.

Putting this result in the more familiar language of measures, we can argue
that, although the cut locus can introduce problems in practice, the
problematic set is not too large.444The analogous result for $C_{p}$ with
respect to the Borel measure induced by the volume form is also true.

######  Corollary 4.6.

$\tilde{C}_{p}$ has Lebesgue measure zero on $T_{p}\mathcal{M}$.

###### Proof.

By the definition of Hausdorff dimension, a set of dimension $n-1$ has
$n$-Hausdorff measure $0$. Finally, just note that the $n$-Hausdorff measure
is a multiple of the Lebesgue measure. ∎

###  4.2 The Lie trivialization

We now introduce a useful trivialization for Lie groups and other matrix
manifolds. Recall that for a Lie group $G$ we define its _Lie algebra_ as the
tangent space to the identity element $\mathfrak{g}\coloneqq T_{e}G$. In Lie
group theory there is a canonical trivialization given by the _Lie
exponential_. For matrix Lie groups, which are the groups that we are
interested in, the Lie exponential is exactly the exponential of matrices. We
will denote the exponential of a matrix $A$ as $\exp(A)$ or $e^{A}$ for short.

For connected and compact Lie groups—, $\operatorname{SO}\lparen
n\rparen,\operatorname{U}\lparen n\rparen,\operatorname{SU}\lparen
n\rparen,\operatorname{Sp}\lparen n\rparen$—this map is surjective and it
coincides with the Riemannian trivialization at the identity for a suitable
metric. If it is not surjective, we can still use it as a trivialization of
the image of $\mathfrak{g}$ under $\exp$. In Section 6.2 we explain how to use
the exponential parametrization in the whole Lie group, even when it is not
surjective. Trivializations of this form for compact Lie groups were already
studied in [Lezcano-Casado and Martínez-Rubio, 2019].

The following theorem is a generalization for matrix Lie groups of a classic
result.

######  Theorem 4.7 (Properties of the Lie exponential).

Let $G$ be a matrix Lie group, the Lie exponential is a diffeomorphism on the
set
$U=\\{A\in\mathfrak{g}\>|\>\lvert\mathrm{Im}\lparen\lambda_{i}(A)\rparen\rvert<\pi\\}$
with $\lambda_{i}(A)$ the eigenvalues.

###### Proof.

See Appendix C. ∎

This result is the counterpart of Theorem 4.4 for the Lie trivialization on
general matrix Lie groups. The boundary of this set has similar properties as
those of the cut locus for the Riemannian trivialization for groups like
$\operatorname{GL}\lparen n\rparen$ or $\operatorname{SO}\lparen
n\rparen$.555The constant $\pi$ is tight for matrix manifolds that contain
matrices with eigenvalues that are $2\pi i$ apart. For these manifolds, the
matrix exponential fails to be a diffeomorphism on some points of the boundary
of $U$. As such, this trivialization presents the same problem as the
Riemannian trivialization: It works as a change of metric for points that are
close to the identity matrix, but it creates local minima and saddle points on
some points of the manifold, which we might encounter as the optimization
method progresses.

##  5 Dynamic Trivializations

In the last section, we have seen rather general families of trivializations
that cover most of the manifolds used in practice. We have seen how these
trivializations act as a change of metric around the initial point—$p$ in the
case of the Riemannian trivialization and the identity matrix in the case of
the Lie trivialization—but we have also shown that the optimization process
can be affected as it deviates from the initial point.

Note that, in the case of the exponential trivialization, we have a map from
any tangent space of $\mathcal{M}$ onto $\mathcal{M}$, but we are just using
one of them as a trivialization. We can leverage the structure of
$T\mathcal{M}$ in order to solve the problem that the trivializations
introduced above. Instead of always using $\exp_{\mathcal{M},p}$, we can use
it just for $K$ optimization steps and then change $p$ to the point on which
we find ourselves on the manifold after those $K$ steps. This idea is
formalized in the following algorithm.

######  Algorithm 5.1 (Dynamic trivialization through retractions).

Given a retraction $\phi$, an integer $K>0$ or $K=\infty$, and a starting
point $p_{0}$, the dynamic trivialization induced by $\phi$ is defined as the
sequence of problems indexed by $i=0,1,\dots$

$\min_{y\in T_{p_{i}}\mathcal{M}}f(\phi_{p_{i}}(y))$

where $p_{i+1}\coloneqq\phi_{p_{i}}(y_{i,K})\in\mathcal{M}$, and $y_{i,k}\in
T_{p_{i}}\mathcal{M}$ for $k=1,\dots,K$, is a sequence of approximations given
by a Euclidean optimization algorithm—, sgd, adam, adagrad, rmsprop, …—applied
to the $i$-th problem with starting point $y_{i,0}=0$. We say that $p_{i}$ is
the _basis_ at step $i$.

######  Remark.

Note that in this case we have dropped the condition of $\phi_{p}\colon
T_{p}\mathcal{M}\to\mathcal{M}$ being surjective. This is because, as long as
$\mathcal{M}$ is connected, we can still reach any point in $\mathcal{M}$ in
the optimization process by changing the basis of the dynamic trivialization
whenever $K<\infty$.

Figure 1: Example of the trivialization and dynamic trivialization procedure.
The dynamic trivialization in this example has $K=4$.

This procedure has two interesting limit cases.

##### Generalization of trivializations.

For $K=\infty$, , no change of basis, it reduces to the trivialization
algorithms described in Section 4 with the trivialization $\phi_{p_{0}}$,
provided that $\phi_{p_{0}}$ is surjective.

##### Generalization of Riemannian gradient descent.

In the case $K=1$, we are changing the basis of the trivialization on every
step. When the optimization process used to generate the iterates $y_{i,k}$ is
regular sgd, this method recovers exactly stochastic Riemannian gradient
descent using $\phi$ as a retraction. For this, just note that by the chain
rule and the definition of a retraction

$\mathrm{d}\lparen
f\circ\phi_{p_{i}}\rparen_{0}=\lparen\mathrm{d}f\rparen_{\phi_{p_{i}}(0)}\circ\lparen\mathrm{d}\phi_{p_{i}}\rparen_{0}=\lparen\mathrm{d}f\rparen_{\phi_{p_{i}}(0)}=\lparen\mathrm{d}f\rparen_{p_{i}}.$

From this it follows that

$\nabla\lparen f\circ\phi_{p_{i}}\rparen(0)=\nabla f\lparen p_{i}\rparen$

so the update rule simplifies for a learning rate $\eta>0$ can be rewritten as

$y_{i,1}=-\eta\nabla f(p_{i})\qquad p_{i+1}=\phi_{p_{i}}(-\eta\nabla
f(p_{i}))$

and $p_{i+1}$ are exactly the iterates given by doing Riemannian sgd using the
retraction $\phi$.

In particular, we have proved that for $\phi=\exp_{\mathcal{M}}$, we recover
stochastic Riemannian gradient descent. As such, we can see dynamic
trivializations as an interpolation between the trivialization method using
$\exp_{\mathcal{M}}$ and stochastic Riemannian gradient descent.

More interesting is perhaps the case when we use a different optimizer to
generate the iterates $y_{i,k}$. In this case, dynamic trivializations yield a
natural generalization to manifolds of the algorithm used to generate the
iterates, , adam, adagrad, rmsprop, .

##  6 Gradient Computations and Examples

The last missing piece needed to implement dynamic trivializations is the
explicit computation of their gradients. We will do so for the two families
presented above.

###  6.1 The matrix exponential

We first look at the matrix exponential. This function not only defines the
Lie trivialization, but it is also essential to compute the Riemannian
exponential in many matrix manifolds (, Appendix E). In order to implement the
dynamic trivialization algorithm within the context of first-order methods we
need an approximation of the trivialization map and its gradient.

The current fastest machine-precision approximation to the matrix exponential
was formulated in [Al-Mohy and Higham, 2009b]. On the other hand, it is not
clear how to compute the gradient of this parametrization. The following
proposition settles this problem.

######  Proposition 6.1 (Gradient of the exponential parametrization).

Let $f\colon\mathbb{R}^{n\times n}\to\mathbb{R}$ be a function defined on
matrices, and let $\exp$ be the matrix exponential, we have

$\nabla\lparen
f\circ\exp\rparen(A)=\lparen\mathrm{d}\exp\rparen_{A^{\intercal}}\lparen\nabla
f(e^{A})\rparen.$

###### Proof.

See Appendix D. ∎

This proposition together with the approximation algorithm for
$\mathrm{d}\exp$ presented in [Al-Mohy and Higham, 2009a] allows us to
approximate to machine-precision this gradient.

This formula readily allows for the implementation of the Riemannian dynamic
trivialization on many matrix manifolds. We give examples of some of these in
Appendix E.

###  6.2 Lie exponential for matrix Lie groups

The Lie exponential on a Lie group $G$ is just defined on the Lie algebra
$\mathfrak{g}=T_{e}G$. On matrix Lie groups, we can identify any tangent space
of $G$ with $\mathfrak{g}$. Explicitly, if $\tilde{A}\in T_{B}G$, then
$B^{-1}\tilde{A}\in\mathfrak{g}$. Furthermore, if we choose a left-invariant
metric on the Lie group, we can then use left multiplication to map the result
$\exp(B^{-1}\tilde{A})$ to a neighborhood of $B$. In symbols, we can define

$\\!\begin{aligned} \exp_{B}\colon T_{B}G&\to G\\\ \tilde{A}&\mapsto
B\exp\lparen B^{-1}\tilde{A}\rparen\end{aligned}$

We give the gradient of this parametrization in Corollary D.3. This function
constitutes a dynamic trivialization on any connected matrix Lie group, like,
for example, $\operatorname{SO}\lparen n\rparen$, $\operatorname{U}\lparen
n\rparen$, $\operatorname{SL}\lparen n\rparen$, or
$\operatorname{GL^{+}}\lparen n\rparen$.

###  6.3 Other retractions

Sometimes one cannot afford to approximate the exponential exactly, as it can
be very costly. In this case, the standard alternative are retractions Boumal
et al. [2016].

##### Cayley map.

This is one of the most well known retractions to optimize over
$\operatorname{SO}\lparen n\rparen$ (, Absil et al. [2009], Helfrich et al.
[2018])

$\\!\begin{aligned} \operatorname*{cay}\colon\operatorname{Skew}\lparen
n\rparen&\to\operatorname{SO}\lparen n\rparen\\\
A&\mapsto(\mathrm{I}+A)(\mathrm{I}-A)^{-1}\end{aligned}$

This can be made into a dynamic retraction using the same trick as we did with
the exponential, considering
$\operatorname*{cay}_{B}(A)=B\operatorname*{cay}(B^{-1}\tilde{A})$, for
$B\in\operatorname{SO}\lparen n\rparen$, $\tilde{A}\in
T_{B}\operatorname{SO}\lparen n\rparen$.

##### Projectors.

Another common retraction used in matrix manifolds
$\mathcal{M}\subseteq\mathbb{R}^{n\times n}$ is the one given by
$\pi_{\mathcal{M}}(x+v)$ for $x\in\mathcal{M}$, $v\in T_{x}\mathcal{M}$ and
$\pi_{\mathcal{M}}$ the projection from $\mathbb{R}^{n\times n}$ onto
$\mathcal{M}$. For example, for $\mathcal{M}=\operatorname{SO}\lparen
n\rparen$, we have that for a matrix $B\in\mathbb{R}^{n\times n}$ with SVD
decomposition $B=U\Sigma V^{\intercal}$, its projection onto
$\operatorname{SO}\lparen n\rparen$ is given by $\pi_{\operatorname{SO}\lparen
n\rparen}(B)=UV^{\intercal}$.666Formally, $\pi_{\operatorname{SO}\lparen
n\rparen}$ is well-defined for matrices such that $\det B>0$, that is,
$\pi_{\operatorname{SO}\lparen n\rparen}\colon\operatorname{GL^{+}}\lparen
n\rparen\to\operatorname{SO}\lparen n\rparen$. Note that this function is not
a diffeomorphism but a submersion. Theorem 4.3 can be extended to this case.
with gradient computed in [ Kenney and Laub, 1991, Eq. $2.18$].

We workout more useful examples for common manifolds in Appendix E.

##  7 Experiments

In this section, we assess the effectiveness of dynamic trivializations
(dtriv) in the context of orthogonal optimization. We test the framework with
the basis changed every $K=1,100,\infty$ steps.

We compare it against the most performant previous approaches presented for
this task in the context of orthogonal optimization and a vanilla lstm. These
approaches are orthogonal exponential trivialization [exprnn Lezcano-Casado
and Martínez-Rubio, 2019], orthogonal and unitary Cayley trivializations
[scornn / scurnn Helfrich et al., 2018, Maduranga et al., 2018], and
Riemannian gradient descent [rgd Wisdom et al., 2016].

The architecture on which we are testing the dynamic trivialization is the
same as in the papers above: A vanilla rnn with an orthogonal layer
parametrized using the Lie trivialization (, Section 6.2)

$h_{t+1}=\sigma\lparen\exp_{B}(A)h_{t}+Tx_{t+1}\rparen.$

The update procedure for $B$ was described in 5.1 ($K=1,100,\infty$).

######  Remark.

Note that rgd is equivalent to dtriv$1$ together with the optimizer sgd.
Furthermore, exprnn is equivalent dtriv$\infty$ only that exprnn has the basis
on the identity matrix and dtriv$\infty$ has the basis on the matrix to which
it is initialized.

We test this architecture on two different tasks that have become the standard
to test the performance of rnns in the context of long-term recall and long-
term memory, namely the pixel-by-pixel mnist and the timit dataset [Arjovsky
et al., 2016, Henaff et al., 2016, Mhammedi et al., 2017, Helfrich et al.,
2018, Maduranga et al., 2018, Lezcano-Casado and Martínez-Rubio, 2019]. We do
not present results for the copying problem, as task is too simple to draw any
meaningful conclusions, as explained in Henaff et al. [2016]. 777For
reference, dynamic trivializations are also able to converge to the correct
answer stably, as exprnn.

We detail all the hyperparameters and set-up in Appendix F. The code and
instructions to replicate these experiments can be found in

Table 1: Best test accuracy at mnist and p-mnist. Model | n | mnist | p-mnist
---|---|---|---
dtriv$1$ | $170$ | $\mathbf{98.3}$ | $\mathbf{95.2}$
dtriv$100$ | $170$ | $98.2$ | $95.1$
dtriv$\infty$ | $170$ | $98.1$ | $95.0$
exprnn | $170$ | $98.0$ | $94.9$
scornn | $170$ | $97.2$ | $94.8$
scurnn | $116$ | $97.6$ | $94.9$
lstm | $128$ | $81.9$ | $79.5$
rgd | $116$ | $94.7$ | $92.5$
dtriv$1$ | $360$ | $98.4$ | $96.3$
dtriv$100$ | $360$ | $98.8$ | $96.4$
dtriv$\infty$ | $360$ | $\mathbf{98.9}$ | $\mathbf{96.5}$
exprnn | $360$ | $98.4$ | $96.2$
scornn | $360$ | $98.1$ | $95.9$
scurnn | $250$ | $98.3$ | $96.2$
lstm | $256$ | $88.8$ | $88.8$
rgd | $256$ | $96.1$ | $93.9$
dtriv$1$ | $512$ | $98.7$ | $96.7$
dtriv$100$ | $512$ | $\mathbf{99.1}$ | $96.7$
dtriv$\infty$ | $512$ | $99.0$ | $\mathbf{96.8}$
exprnn | $512$ | $98.7$ | $96.6$
scornn | $512$ | $98.2$ | $96.5$
lstm | $512$ | $91.9$ | $91.8$
rgd | $512$ | $97.3$ | $94.7$

Table 2: Test mse at the end of the epoch with the lowest validation mse for the timit task. Model | n | Val. mse | Test mse
---|---|---|---
dtriv$1$ | $224$ | $6.55$ | $6.54$
dtriv$100$ | $224$ | $4.80$ | $4.77$
dtriv$\infty$ | $224$ | $\mathbf{4.75}$ | $\mathbf{4.71}$
exprnn | $224$ | $5.34$ | $5.30$
scornn | $224$ | $9.26$ | $8.50$
scurnn | $128$ | $9.42$ | $7.23$
lstm | $84$ | $15.42$ | $14.30$
rgd | $128$ | $15.07$ | $14.58$
dtriv$1$ | $322$ | $4.56$ | $4.55$
dtriv$100$ | $322$ | $3.80$ | $3.76$
dtriv$\infty$ | $322$ | $\mathbf{3.39}$ | $\mathbf{3.76}$
exprnn | $322$ | $4.42$ | $4.38$
scornn | $322$ | $8.48$ | $7.82$
lstm | $120$ | $13.93$ | $12.95$
rgd | $192$ | $15.10$ | $14.50$
dtriv$1$ | $425$ | $4.21$ | $4.17$
dtriv$100$ | $425$ | $2.02$ | $1.99$
dtriv$\infty$ | $425$ | $\mathbf{2.00}$ | $\mathbf{1.97}$
exprnn | $425$ | $5.52$ | $5.48$
scornn | $425$ | $7.97$ | $7.36$
scurnn | $258$ | $4.40$ | $3.39$
lstm | $158$ | $13.66$ | $12.62$
rgd | $256$ | $14.96$ | $14.69$

https://github.com/Lezcano/expRNN

###  7.1 Pixel-by-pixel mnist

This task consists of classifying the hand-written images of numbers in the
mnist dataset [LeCun and Cortes, 2010] by processing them as a sequence pixel-
by-pixel. Each image has $28\times 28$ pixels, so the sequences are of length
$784$. The _unpermuted task_ (mnist) processes the row-by-row flattened image,
the _permuted task_ (p-mnist) samples a permutation of size $784$ at the
beginning and then uses it to permute all the images after flattening them.
This task was introduced in Le et al. [2015].

Table 2 is structured so that architectures with the same number of parameters
are compared together. As we can see, the addition of any dynamic
trivialization to the Lie parametrization improves the results on this
experiment by $0.4\%$ out of the $1.3\%$ possible in the largest size.
Moreover, it always improves the previous results, suggesting that it is
always a better option to use dynamic trivializations rather than just plain
trivializations. In general, we saw that $\textsc{dtriv}{}100$ and
$\textsc{dtriv}{}\infty$ gave the highest stability and the best results
across the experiments.

###  7.2 timit speech dataset

The timit dataset [S Garofolo et al., 1992] is a set of variable-length real-
world speech recordings. These recordings are first downsampled to $8$kHz and
then transformed into log-magnitudes via a short-time Fourier transform,
giving sequences of $129$ complex numbers per step, and a variable length
between $61$ and $490$. The task consists of predicting the next log-magnitude
given the previous ones. This experiment was introduced in Wisdom et al.
[2016].

In this experiment we see a similar behavior of the dynamic trivializations as
the one already seen in the mnist and p-mnist experiments. It also happens in
this experiment that dtriv$100$ and dtriv$\infty$ always improve the
performance of their static counterparts with base at the identity and of rgd.

In the experiments in scurnn they explicitly mention that they are computing
the mse without discarding the zeros used to pad the variable-length sequences
[Maduranga et al., 2018]. As such, when computing the mse, they are dividing
by an incorrect number—the longest element in the batch times the elements in
the batch—rather than by the correct one—the sum of the lengths of all the
elements in the batch. We computed the correct validation and test loss in
Table 2.

##  8 Conclusion and Future Work

In this paper we have presented a novel way to perform optimization on
manifolds that combines the strengths of the two most popular optimization
techniques used in machine learning and neural networks—parametrizations and
Riemannian gradient descent. We have shown that, by moving the initial point
of the parametrization, as the metric is distorted less from the Euclidean
one, we can achieve an improvement on the convergence of the neural network.

We leave open an interesting line of research based on applying dynamic
trivializations to allow optimization on other interesting manifolds. As a
first step in this direction, we detail examples of some computations for the
most common manifolds used in optimization in Appendix E.

## Acknowledgements

We would like to thank the help of Jaime Mendizabal and Momchil Konstantinov
for the very useful feedback and suggestions and Prof. Andras Juhasz for the
computing power.

The work of MLC was supported by the Oxford-James Martin Graduate Scholarship
and the “la Caixa” Banking Foundation (LCF/BQ/EU17/11590067).

## References

  * Absil et al. [2009] P.-A. Absil, R. Mahony, and R. Sepulchre.  _Optimization algorithms on matrix manifolds_.  Princeton University Press, 2009.
  * Al-Mohy and Higham [2009a] A. H. Al-Mohy and N. J. Higham.  Computing the fréchet derivative of the matrix exponential, with an application to condition number estimation.  _SIAM Journal on Matrix Analysis and Applications_ , 30(4):1639–1657, 2009a.
  * Al-Mohy and Higham [2009b] A. H. Al-Mohy and N. J. Higham.  A new scaling and squaring algorithm for the matrix exponential.  _SIAM Journal on Matrix Analysis and Applications_ , 31(3):970–989, 2009b.
  * Andruchow et al. [2014] E. Andruchow, G. Larotonda, L. Recht, and A. Varela.  The left invariant metric in the general linear group.  _Journal of Geometry and Physics_ , 86:241–257, 2014.
  * Arjovsky et al. [2016] M. Arjovsky, A. Shah, and Y. Bengio.  Unitary evolution recurrent neural networks.  In _International Conference on Machine Learning_ , pages 1120–1128, 2016.
  * Arsigny et al. [2006] V. Arsigny, O. Commowick, X. Pennec, and N. Ayache.  A log-euclidean framework for statistics on diffeomorphisms.  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , pages 924–931. Springer, 2006.
  * Arsigny et al. [2007] V. Arsigny, P. Fillard, X. Pennec, and N. Ayache.  Geometric means in a novel vector space structure on symmetric positive-definite matrices.  _SIAM journal on matrix analysis and applications_ , 29(1):328–347, 2007.
  * Bahdanau et al. [2014] D. Bahdanau, K. Cho, and Y. Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Becigneul and Ganea [2019] G. Becigneul and O.-E. Ganea.  Riemannian adaptive optimization methods.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=r1eiqi09K7.
  * Berg et al. [2018] R. v. d. Berg, L. Hasenclever, J. M. Tomczak, and M. Welling.  Sylvester normalizing flows for variational inference.  _arXiv preprint arXiv:1803.05649_ , 2018.
  * Bonnabel [2013] S. Bonnabel.  Stochastic gradient descent on riemannian manifolds.  _IEEE Transactions on Automatic Control_ , 58(9):2217–2229, 2013.
  * Bonnabel and Sepulchre [2009] S. Bonnabel and R. Sepulchre.  Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank.  _SIAM Journal on Matrix Analysis and Applications_ , 31(3):1055–1070, 2009.
  * Boumal et al. [2016] N. Boumal, P.-A. Absil, and C. Cartis.  Global rates of convergence for nonconvex optimization on manifolds.  _IMA Journal of Numerical Analysis_ , 2016.
  * Cho et al. [2014] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ , 2014.
  * do Carmo [1992] M. do Carmo.  _Riemannian Geometry_.  Mathematics (Boston, Mass.). Birkhäuser, 1992.  ISBN 9783764334901.  URL https://books.google.co.uk/books?id=uXJQQgAACAAJ.
  * Dreisigmeyer [2018] D. W. Dreisigmeyer.  Direct search methods on reductive homogeneous spaces.  _Journal of Optimization Theory and Applications_ , 176(3):585–604, 2018.
  * Duchi et al. [2011] J. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(Jul):2121–2159, 2011.
  * Edelman et al. [1998] A. Edelman, T. A. Arias, and S. T. Smith.  The geometry of algorithms with orthogonality constraints.  _SIAM journal on Matrix Analysis and Applications_ , 20(2):303–353, 1998.
  * Gallier and Quaintance [2019] J. Gallier and J. Quaintance.  Differential geometry and Lie groups. a computational perspective.  Available in https://www.seas.upenn.edu/~jean/diffgeom-spr-I.pdf, 2019.
  * Gallot et al. [2012] S. Gallot, D. Hulin, and J. Lafontaine.  _Riemannian Geometry_.  Springer, 2 edition, 2012.
  * Hall [2015] B. Hall.  _Lie Groups, Lie Algebras, and Representations: An Elementary Introduction_.  Graduate Texts in Mathematics. Springer International Publishing, 2015\.  ISBN 9783319134673.  URL https://books.google.es/books?id=didACQAAQBAJ.
  * Helfrich et al. [2018] K. Helfrich, D. Willmott, and Q. Ye.  Orthogonal recurrent neural networks with scaled Cayley transform.  In _Proceedings of the 35th International Conference on Machine Learning_ , Proceedings of Machine Learning Research, pages 1969–1978. PMLR, 2018\.
  * Helgason [1979] S. Helgason.  _Differential geometry, Lie groups, and symmetric spaces_ , volume 80.  Academic press, 1979.
  * Henaff et al. [2016] M. Henaff, A. Szlam, and Y. LeCun.  Recurrent orthogonal networks and long-memory tasks.  In _Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 48_ , pages 2034–2042. JMLR. org, 2016.
  * Higham [2008] N. J. Higham.  _Functions of matrices: theory and computation_ , volume 104.  Siam, 2008.
  * Hille [1958] E. Hille.  On roots and logarithms of elements of a complex banach algebra.  _Mathematische Annalen_ , 136(1):46–57, 1958\.
  * Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Iserles and Nørsett [1999] A. Iserles and S. Nørsett.  On the solution of linear differential equations in lie groups.  _Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , 357(1754):983–1019, 1999.
  * Iserles et al. [2000] A. Iserles, H. Z. Munthe-Kaas, S. P. Nørsett, and A. Zanna.  Lie-group methods.  _Acta numerica_ , 9:215–365, 2000.
  * Itoh and Tanaka [1998] J.-i. Itoh and M. Tanaka.  The dimension of a cut locus on a smooth riemannian manifold.  _Tohoku Mathematical Journal, Second Series_ , 50(4):571–575, 1998.
  * Jing et al. [2017] L. Jing, Y. Shen, T. Dubcek, J. Peurifoy, S. Skirlo, Y. LeCun, M. Tegmark, and M. Soljačić.  Tunable efficient unitary neural networks (eunn) and their application to rnns.  In _International Conference on Machine Learning_ , pages 1733–1741, 2017.
  * Kenney and Laub [1991] C. Kenney and A. J. Laub.  Polar decomposition and matrix sign function condition estimates.  _SIAM Journal on Scientific and Statistical Computing_ , 12(3):488–504, 1991.
  * Kingma and Ba [2014] D. Kingma and J. Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kingma and Dhariwal [2018] D. P. Kingma and P. Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In _Advances in Neural Information Processing Systems_ , pages 10215–10224, 2018.
  * Le et al. [2015] Q. V. Le, N. Jaitly, and G. E. Hinton.  A simple way to initialize recurrent networks of rectified linear units.  _arXiv preprint arXiv:1504.00941_ , 2015.
  * LeCun and Cortes [2010] Y. LeCun and C. Cortes.  MNIST handwritten digit database.  http://yann.lecun.com/exdb/mnist/, 2010.  URL http://yann.lecun.com/exdb/mnist/.
  * Lee [2013] J. Lee.  _Introduction to Smooth Manifolds_.  Springer, 2 edition, 2013.
  * Lee [2018] J. Lee.  _Introduction to Riemannian Manifolds_.  Springer, 2 edition, 2018.
  * Lezcano-Casado and Martínez-Rubio [2019] M. Lezcano-Casado and D. Martínez-Rubio.  Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group.  _arXiv preprint arXiv:1901.08428_ , 2019.
  * Maduranga et al. [2018] K. D. Maduranga, K. E. Helfrich, and Q. Ye.  Complex unitary recurrent neural networks using scaled cayley transform.  _arXiv preprint arXiv:1811.04142_ , 2018.
  * Magnus [1954] W. Magnus.  On the exponential solution of differential equations for a linear operator.  _Communications on pure and applied mathematics_ , 7(4):649–673, 1954.
  * Mhammedi et al. [2017] Z. Mhammedi, A. Hellicar, A. Rahman, and J. Bailey.  Efficient orthogonal parametrisation of recurrent neural networks using householder reflections.  In _International Conference on Machine Learning_ , pages 2401–2409, 2017.
  * O’Neill [1983] B. O’Neill.  _Semi-Riemannian Geometry With Applications to Relativity_.  Pure and Applied Mathematics. Elsevier Science, 1983.  ISBN 9780080570570.  URL https://books.google.co.uk/books?id=CGk1eRSjFIIC.
  * Petersen [2016] P. Petersen.  _Riemannian Geometry_.  Springer, 3 edition, 2016.  ISBN 3319266527.
  * Rasmussen and Williams [2005] C. E. Rasmussen and C. K. I. Williams.  _Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning)_.  The MIT Press, 2005.  ISBN 026218253X.
  * Rossmann [2006] W. Rossmann.  _Lie Groups: An Introduction Through Linear Groups_.  Oxford graduate texts in mathematics. Oxford University Press, 2006.  ISBN 9780199202515.  URL https://books.google.co.uk/books?id=bAjulQ65W-UC.
  * S Garofolo et al. [1992] J. S Garofolo, L. Lamel, W. M Fisher, J. Fiscus, D. S. Pallett, N. L. Dahlgren, and V. Zue.  Timit acoustic-phonetic continuous speech corpus.  _Linguistic Data Consortium_ , 11 1992.
  * Sato and Iwai [2015] H. Sato and T. Iwai.  A new, globally convergent riemannian conjugate gradient method.  _Optimization_ , 64(4):1011–1031, 2015.
  * Smith [1993] S. T. Smith.  _Geometric Optimization Methods for Adaptive Filtering_.  PhD thesis, Harvard University, Cambridge, MA, USA, 1993.  UMI Order No. GAX93-31032.
  * Tieleman and Hinton [2012] T. Tieleman and G. Hinton.  Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude.  _COURSERA: Neural networks for machine learning_ , 4(2):26–31, 2012.
  * Tomczak and Welling [2016] J. M. Tomczak and M. Welling.  Improving variational auto-encoders using householder flow.  _arXiv preprint arXiv:1611.09630_ , 2016.
  * Udriste [1994] C. Udriste.  _Convex Functions and Optimization Methods on Riemannian Manifolds_.  Mathematics and Its Applications. Springer Netherlands, 1994.  ISBN 9780792330028.
  * Wang et al. [1969] H.-C. Wang et al.  Discrete nilpotent subgroups of Lie groups.  _Journal of Differential Geometry_ , 3(3-4):481–492, 1969.
  * Wisdom et al. [2016] S. Wisdom, T. Powers, J. Hershey, J. Le Roux, and L. Atlas.  Full-capacity unitary recurrent neural networks.  In _Advances in Neural Information Processing Systems_ , pages 4880–4888, 2016.
  * Zhang and Sra [2016] H. Zhang and S. Sra.  First-order methods for geodesically convex optimization.  In _Conference on Learning Theory_ , pages 1617–1638, 2016.
  * Zhang and Sra [2018] H. Zhang and S. Sra.  Towards riemannian accelerated gradient methods.  _arXiv preprint arXiv:1806.02812_ , 2018.
  * Zhang et al. [2016] H. Zhang, S. J. Reddi, and S. Sra.  Riemannian svrg: Fast stochastic optimization on riemannian manifolds.  In _Advances in Neural Information Processing Systems_ , pages 4592–4600, 2016.
  * Zhang et al. [2018] J. Zhang, Q. Lei, and I. Dhillon.  Stabilizing gradients for deep neural networks via efficient svd parameterization.  In _International Conference on Machine Learning_ , pages 5801–5809, 2018.

##  Appendix A Differential and Riemannian Geometry

In this section we give a short introduction to the concepts used in the paper
and in the appendix of the theories of differential and Riemannian geometry
and Lie groups. The standard modern introduction to differential geometry is
Lee [2013]. This book also gives an introduction to Lie groups. Introductory
texts in Riemannian geometry are do Carmo [1992], Lee [2018]. Introductory
references for Lie groups are Rossmann [2006], Hall [2015]. Although not
covered in this summary, two more advanced texts that cover the classical
theory of the cut locus through Jacobi fields are Gallot et al. [2012],
Petersen [2016].

###  A.1 Differential Geometry

Let $\mathcal{M}$ be an $n$-dimensional differentiable real manifold.
$\mathcal{M}$ has an associated global object called the _tangent bundle_
$T\mathcal{M}\coloneqq\sqcup_{p\in\mathcal{M}}\\{p\\}\times T_{p}\mathcal{M}$,
that is, the disjoint union of all the tangent spaces at every point of
$\mathcal{M}$. The tangent bundle comes with a structure of a $2n$-dimensional
differentiable manifold. A point in $T\mathcal{M}$ consists then of a pair
$(p,v)$ with $p\in\mathcal{M}$ and $v\in T_{p}\mathcal{M}$. On each point, we
also have the _cotangent space_ $T_{p}^{\ast}\mathcal{M}$ of linear
applications from vectors onto the real numbers. The disjoint union of all the
cotangent spaces is another manifold $T^{\ast}\mathcal{M}$ called the
_cotangent bundle_. When considering these bundles, tangent spaces
$T_{p}\mathcal{M}$ and cotangent spaces $T_{p}^{\ast}\mathcal{M}$ are
sometimes called _fibres_.

An _affine connection_ $\nabla$ is a bilinear form that, given two vector
fields $X,Y$, assigns a new one $\nabla_{X}Y$, and it is tensorial on the
first component and Leibnitz on the second. An affine connection defines a
notion of _parallel vector fields_. We say that a vector field $Z$ is parallel
along a curve $\gamma\colon[0,1]\to\mathcal{M}$ if
$\nabla_{\gamma^{\prime}}Z=0$ where
$\gamma^{\prime}\coloneqq\mathrm{d}\gamma\lparen\frac{\mathrm{d}}{\mathrm{d}t}\rparen$.
For any curve, given an initial vector $Z_{0}$, there exists a unique parallel
vector field $Z$ along it such that $Z(0)=Z_{0}$. We say that the vector
$Z(t)$ is the parallel transport of $Z(0)$ for $t\in[0,\varepsilon)$.

###  A.2 Riemannian Geometry

A _Riemannian manifold_ is a differentiable manifold together with a smooth
metric $\textsl{g}_{p}\colon T_{p}\mathcal{M}\times
T_{p}\mathcal{M}\to\mathbb{R}$ which is symmetric and positive definite. A
metric induces a distinguished connection called the _Levi-Civita connection_.
This is the unique connection that is torsion-free,
$\nabla_{X}Y-\nabla_{Y}X=[X,Y]\coloneqq XY-YX$, and it is compatible with the
metric,
$\mathrm{D}_{Z}(\textsl{g}(X,Y))=\textsl{g}(\nabla_{Z}X,Y)+\textsl{g}(X,\nabla_{Z}Y)$,
where $\mathrm{D}_{Z}$ denotes the directional derivative in the direction of
$Z$. Whenever we talk about a connection on a Riemannian manifold we will
always be referring to the Levi-Civita connection.

A Riemannian manifold has a notion of length of a differentiable curve
$c\colon[0,1]\to\mathcal{M}$,
$L(c)=\int_{0}^{1}\lVert\gamma^{\prime}(t)\rVert\,\mathrm{d}t$. When the
manifold is connected, this allows to put the structure of a metric space on
the manifold, defining the distance between two points as the length of the
shortest piece-wise differentiable curve joining these two points.

Given a connection, we define a _geodesic_
$\gamma\colon[0,\varepsilon)\to\mathcal{M}$ as a self-parallel curve,
$\nabla_{\gamma^{\prime}}\gamma^{\prime}=0$. Geodesics are defined for any
starting conditions $(p,v)\in T\mathcal{M}$, $\gamma(0)=p$,
$\gamma^{\prime}(0)=v$ on an interval $[0,\varepsilon)$. If a Riemannian
manifold is connected and complete, the _Hopf-Rinow theorem_ asserts that
geodesics not only exist locally, but globally, that is, they can be extended
indefinitely taking $\varepsilon=\infty$ giving
$\gamma\colon[0,\infty)\to\mathcal{M}$. Furthermore, Hopf-Rinow adds that,
under the same conditions, there exists a geodesic connecting any two given
points. When the connection comes from a metric, geodesics are the locally
length-minimizing curves on $\mathcal{M}$.

Given a connection, we define the exponential map as
$\exp_{p}(v)\coloneqq\gamma_{p,v}(1)$ where $\gamma_{p,v}$ is the geodesic
with initial conditions $(p,v)$. On a connected and complete Riemannian
manifold, Hopf-Rinow says that the exponential map is defined in the whole
tangent bundle.

A metric induces an isomorphism between the tangent and cotangent bundle
$\alpha\colon T\mathcal{M}\to T^{\ast}\mathcal{M}$ defined as
$\alpha(X)\coloneqq\textsl{g}(X,-)$. $\alpha$ is sometimes called the _musical
isomorphism_. The gradient of a function is defined as the vector field
associated to the differential form $\mathrm{d}f$ through this isomorphism
$\nabla f\coloneqq\alpha^{-1}(\mathrm{d}f)$. In other words, it is the vector
field such that $\mathrm{d}f=\textsl{g}(\nabla f,-)$. As such, the gradient
depends on the choice of metric. A metric also allows to define the adjoint of
a differential $\mathrm{d}\phi\colon T_{p}\mathcal{M}\to
T_{\phi(p)}\mathcal{M}$ at a point $p\in\mathcal{M}$ as the application
$\mathrm{d}\phi^{\ast}\colon T_{\phi(p)}\mathcal{M}\to T_{p}\mathcal{M}$ such
that for every $X\in T_{p}\mathcal{M},Y\in T_{\phi(p)}\mathcal{M}$ we have
that
$\textsl{g}(\mathrm{d}\phi(X),Y)_{\phi(p)}=\textsl{g}(X,\mathrm{d}\phi^{\ast}(Y))_{p}$.

###  A.3 Lie groups

A Lie group $G$ is a differentiable manifold equipped with a differentiable
group structure. Lie groups have a distinguished tangent space called the _Lie
algebra_ , which is the tangent space at the identity $\mathfrak{g}\coloneqq
T_{e}G$. Any closed subgroup of a Lie group is itself a Lie group. A (real)
_matrix manifold_ is a closed subgroup of the _general linear group_
$\operatorname{GL}\lparen n\rparen=\\{B\in\mathbb{R}^{n\times n}\>|\>\det
A\neq 0\\}$. The Lie algebra of the general linear group is
$\operatorname{\mathfrak{gl}}\lparen n\rparen=\mathbb{R}^{n\times n}$. In
general, the general linear group of a vector space $V$ is the Lie group
formed by the invertible automorphisms of $V$, $\operatorname{GL}\lparen
V\rparen$.

On a Lie group, one has for every $g,x\in G$ the diffeomorphisms given by left
translations $L_{g}(x)\coloneqq gx$, right translations $R_{g}(x)\coloneqq
xg$, and conjugation $c_{g}(x)=gxg^{-1}$. Using left translations, one can
identify any tangent space with the Lie algebra via the vector space
isomorphism $\lparen\mathrm{d}L_{g^{-1}}\rparen_{g}\colon
T_{g}G\to\mathfrak{g}$. The differential of the conjugation at the identity is
called the _adjoint representation of $G$_, $\operatorname{Ad}\colon
G\to\operatorname{GL}\lparen\mathfrak{g}\rparen$. The differential of
$\operatorname{Ad}$ at the identity is the _adjoint representation of
$\mathfrak{g}$_,
$\operatorname{ad}\colon\mathfrak{g}\to\operatorname{End}\lparen\mathfrak{g}\rparen$.
For matrix Lie groups, $\operatorname{Ad}_{g}(X)=gXg^{-1}$ and
$\operatorname{ad}_{X}(Y)=[X,Y]$.

Given a vector $X\in\mathfrak{g}$, we can consider the _one parameter
subgroup_ with starting vector $X$, which is the unique group homomorphism
$\gamma_{X}\colon\mathbb{R}\to G$ such that $\gamma_{X}^{\prime}(0)=X$. The
Lie exponential is then defined for every $X\in\mathfrak{g}$ as
$\exp(X)\coloneqq\gamma_{X}(1)$. For matrix Lie groups, the Lie exponential is
given by the exponential of matrices.

A Riemannian metric on a Lie group is said to be left (resp. right) invariant
if it turns left (resp. right) translations into isometries. A metric is said
to be bi-invariant if it is both left and right invariant. Every Lie group
admits a left-invariant metric, given by choosing any inner product in
$\mathfrak{g}$ and pushing it forward using $L_{g^{-1}}$. Only compact Lie
groups, commutative Lie groups, and products of them admit bi-invariant
metrics. When a Lie group is equipped with a bi-invariant metric, the Lie
exponential coincides with the Riemannian exponential at the identity.

##  Appendix B Parametrizations on Manifolds

In this section we look at the problem of how does optimizing $f\circ\phi$
affect the optimization problem, depending on the properties of $\phi$. As a
disclaimer we would like to mention that, although this section and next
section are original, most of them would be considered routine in the field of
differential geometry.

Consider the optimization problem

$\min_{x\in\mathcal{M}}f(x)$ (1)

where $\mathcal{M}$ is a Riemannian manifold. In this section we will look at
parametrizations, which can be regarded as a generalization of certain
trivializations, when the domain is not necessary $\mathbb{R}^{n}$ but a
Riemannian manifold.

Suppose that we have access to a diffeomorphism between Riemannian manifolds

$\phi\colon\mathcal{N}\to\mathcal{M}.$

and denote the metric on $\mathcal{N}$ as $\textsl{g}_{2}$. We say that $\phi$
is a _parametrization of $\mathcal{M}$ in terms of $\mathcal{N}$_.

We can then consider the problem

$\min_{y\in\mathcal{N}}f(\phi(y)).$

In order to apply a first-order method to this new problem we first have to
compute the gradient of this new function $f\circ\phi$. In order to do so, let
us first define some notation.

Denote by $\mathrm{d}\phi$ and $\mathrm{d}\phi^{\prime}$ the differential and
its dual

$\displaystyle\mathrm{d}\phi$ $\displaystyle\colon T\mathcal{N}\to
T\mathcal{M}$ $\displaystyle\mathrm{d}\phi^{\prime}$ $\displaystyle\colon
T^{\ast}\mathcal{M}\to T^{\ast}\mathcal{N}$

and denote by $\alpha$ and $\beta$ the canonical isomorphisms between the
tangent and the cotangent bundle induced by the metrics

$\displaystyle\alpha$ $\displaystyle\colon
T\mathcal{M}\overset{\cong}{\to}T^{\ast}\mathcal{M}$ $\displaystyle\beta$
$\displaystyle\colon T\mathcal{N}\overset{\cong}{\to}T^{\ast}\mathcal{N}.$

Finally, denote by $\mathrm{d}\phi^{\ast}$ the fibre-wise adjoint with respect
to the two metrics of $\mathrm{d}\phi$

$\mathrm{d}\phi^{\ast}\colon T\mathcal{M}\to T\mathcal{N}.$

######  Proposition B.1.

Using the notation above, the following relation holds

$\beta\circ\mathrm{d}\phi^{\ast}=\mathrm{d}\phi^{\prime}\circ\alpha.$

###### Proof.

For $Y\in T\mathcal{N},X\in T\mathcal{M}$, we have that

$\lparen\mathrm{d}\phi^{\prime}\circ\alpha\rparen(X)(Y)=\alpha(\mathrm{d}\phi(Y))(X)=\beta\lparen\mathrm{d}\phi^{\ast}(X)\rparen\lparen
Y\rparen=\lparen\beta\circ\mathrm{d}\phi^{\ast}\rparen(X)(Y).\qed$

Using this proposition, we can compute the gradient with respect to the new
parametrization.

######  Corollary B.2.

Let $\phi\colon\mathcal{N}\to\mathcal{M}$ be a smooth map between Riemannian
manifolds and $f$ be a function on $\mathcal{M}$. We have that

$\nabla\lparen f\circ\phi\rparen=\mathrm{d}\phi^{\ast}(\nabla f).$

###### Proof.

This is direct using the previous proposition since

$\nabla\lparen f\circ\phi\rparen:=\beta^{-1}\lparen\mathrm{d}\lparen
f\circ\phi\rparen\rparen=\lparen\beta^{-1}\circ\mathrm{d}\phi^{\prime}\rparen\lparen\mathrm{d}f\rparen=\mathrm{d}\phi^{\ast}\lparen\nabla
f\rparen.\qed$

This motivates the definition of the metric associated to a parametrization
$\phi$.

######  Definition B.3 (Metric associated to a parametrization).

A parametrization between Riemannian manifolds
$\phi\colon\mathcal{N}\to\mathcal{M}$ induces a metric on $\mathcal{M}$ as per

$\lparen\phi_{\ast}\textsl{g}_{2}\rparen(X_{1},X_{2})_{p}:=\textsl{g}_{2}\lparen\mathrm{d}\phi^{\ast}(X_{1}),\mathrm{d}\phi^{\ast}(X_{2})\rparen_{\phi^{-1}(p)}\qquad\forall
p\in\mathcal{M}.$

This is a metric since $\mathrm{d}\phi^{\ast}(X)=0$ if and only if $X=0$ by
the inverse function theorem, given that $\phi$ is a diffeomorphism.

Another way of looking at this construction is through the lens of
submersions.

######  Definition B.4 (Riemannian Submersion).

A Riemannian submersion is a surjective map
$\phi\colon\mathcal{N}\to\mathcal{M}$ such that its differential is surjective
at every point and

$\mathrm{d}\phi\colon\lparen\ker\lparen\mathrm{d}\phi\rparen\rparen^{\perp}\to
T\mathcal{M}$

is an isometry.

This is equivalent to saying that the adjoint $\mathrm{d}\phi^{\ast}$ should
be an isometry. This is exactly the construction that we are using, we take
the metric that converts $\phi$ into a Riemannian submersion.

We now look at this new metric. We will prove that doing gradient descent
using a retraction along $\phi_{\ast}\textsl{g}_{2}$, is not a retraction with
respect to $\textsl{g}_{2}$, and hence, it constitutes an optimization method
fundamentally different to the original Riemannian gradient descent.

Using this metric, gradient descent on $\mathcal{M}$ with a step-size $\eta>0$
is given by the map

$y_{t+1}=\lparen\phi\circ\exp_{\mathcal{N},\textsl{g}_{2}}\circ\mathrm{d}\phi^{\ast}\rparen\lparen-\eta\nabla
f(y_{t})\rparen$

where $\exp_{\mathcal{N},\textsl{g}_{2}}\colon T\mathcal{N}\to\mathcal{N}$ is
the Riemannian exponential map on $(\mathcal{N},\textsl{g}_{2})$. Note that
since $\nabla f=\alpha^{-1}\circ\mathrm{d}f$, this step does not depend on the
initial metric on $\mathcal{M}$, as we already observed in the proof of
Corollary B.2.

More generally, recall the definition of a retraction.

######  Definition B.5 (Retraction).

A differentiable map $r\colon T\mathcal{N}\to\mathcal{N}$ is called a
retraction if for every $p\in\mathcal{N}$

$r_{p}(0)=p\qquad\text{and}\qquad\lparen\mathrm{d}r_{p}\rparen_{0}=\mathrm{Id}.$

In other words, $r$ is an order one approximation to the Riemannian
exponential.

As proved in Boumal et al. [2016], under Lipschitzness conditions, it is
enough to follow retractions rather than the exponential map in order to
achieve convergence to a local minimum with Riemannian gradient descent. As
such, a natural question to ask is whether the function that defines the
update step defines a retraction.

######  Proposition B.6.

Let
$\lparen\mathcal{M},\textsl{g}_{1}\rparen,\lparen\mathcal{N},\textsl{g}_{2}\rparen$
be Riemannian manifolds. Let $\phi$ be a parametrization between them and let
$r\colon T\mathcal{N}\to\mathcal{N}$ be a retraction. The map

$\phi_{\ast}r\coloneqq\phi\circ r\circ\mathrm{d}\phi^{\ast}\colon
T\mathcal{M}\to\mathcal{M}$

is a retraction if and only if $\phi$ is a local isometry.

###### Proof.

It is clear that $\lparen\phi_{\ast}r\rparen_{p}(0)=p$. For the second
condition, differentiating, we have that the map is a retraction if and only
if

$\mathrm{d}\phi\circ\mathrm{d}\phi^{\ast}=\mathrm{Id}_{T_{p}\mathcal{M}}.$

or equivalently $\mathrm{d}\phi^{-1}=\mathrm{d}\phi^{\ast}$. Now,

$\lparen\mathrm{d}\phi\circ\mathrm{d}\phi^{\ast}\circ\mathrm{d}\phi\circ\mathrm{d}\phi^{\ast}\rparen_{p}=\mathrm{Id}_{T_{p}\mathcal{M}}$

so

$\lparen\mathrm{d}\phi^{\ast}\circ\mathrm{d}\phi\rparen_{\phi^{-1}(p)}=\lparen\mathrm{d}\phi^{-1}\circ\mathrm{d}\phi^{\ast}\rparen_{\phi^{-1}(p)}=\mathrm{Id}_{T_{\phi^{-1}(p)}\mathcal{N}}.$

Finally, since $\mathrm{d}\phi^{\ast}$ is the adjoint operator with respect to
the metrics $\textsl{g}_{2}$ and $\textsl{g}_{1}$, evaluating this last
expression on two points using the metric

$\textsl{g}_{1}\lparen\mathrm{d}\phi(u),\mathrm{d}\phi(v)\rparen=\textsl{g}_{2}(u,v)\qquad\forall
u,v\in T_{\phi^{-1}(p)}\mathcal{N},$

which is equivalent to $\phi$ being a local isometry. ∎

This is not a surprising result, since a retraction is a map that preserves
the gradient. The way we have defined $\phi_{\ast}r$ is such that it preserves
the gradient with respect to $\textsl{g}_{2}$. If it also preserved the
gradient with respect to $\textsl{g}_{1}$, that would mean that the gradients
with respect to the two metrics are the same, modulo a transformation through
$\mathrm{d}\phi^{\ast}$, in other words, $\mathrm{d}\phi$ should be a local
isometry.

##  Appendix C Proof of Theorem 4.7

In this section we generalize to general matrix Lie groups the classic proof
presented in Theorem D.$2.$ in Lezcano-Casado and Martínez-Rubio [2019].

In order to generalize this proof, we need the following theorem.

######  Theorem C.1 (Theorem $4$ in Hille [1958]).

Let $A,B\in\mathbb{C}^{n\times n}$. If there are no two eigenvalues in $A$
such that their difference is of the form $2n\pi i$ for $n>0$ and, if
$e^{A}=e^{B}$, we have that $AB=BA$.

With this theorem in hand we can prove the following strengthened result.

######  Theorem C.2 (Properties of the Lie exponential).

Let $G$ be a closed subgroup of $\operatorname{GL}\lparen
n,\mathbb{C}\rparen$, the Lie exponential is a diffeomorphism on the set
$U=\\{A\in\mathfrak{g}\>|\>\lvert\mathrm{Im}\lparen\lambda_{i}(A)\rparen\rvert<\pi\\}$
with $\lambda_{i}(A)$ the eigenvalues of $A$.

###### Proof.

The fact that the differential of the exponential is surjective on this domain
is classic (Section $1$, Proposition $7$ in Rossmann [2006]). As such, we just
have to prove that the exponential is injective on this domain.

If $A\in U$ is diagonalizable, $A=C\Sigma C^{-1}$ with $\Sigma$ diagonal, and
$\exp(A)=C\exp(\Sigma)C^{-1}$ where $\exp(\Sigma)$ is just the element-wise
exponential of the diagonal elements.

By Hille [1958], for any two matrices $A,B\in U$, if $e^{A}=e^{B}$ we have
that $AB=BA$. In particular, as they commute, we have that
$e^{A}e^{-B}=e^{A-B}=\mathrm{I}$.

As $A,B\in U$, we have that $\mathrm{Im}\lparen\lambda_{i}\lparen
A-B\rparen\rparen<2\pi$, and as the eigenvalues of $e^{A-B}$ are $1$, and the
eigenvalues of the exponential of a matrix is the exponential of its
eigenvalues, we have that the eigenvalues of $A-B$ are all zero. Putting it in
Jordan-normal form, we can assume that $A-B$ is upper triangular so, as the
eigenvalues of $A-B$ are zero, we can assume that $A-B$ is also nilpotent.

Now, if we prove that the only upper triangular nilpotent matrix that is
mapped to the identity matrix under the exponential is the null matrix, we
finish the proof, as this would imply that $A=B$.

The set of upper-triangular nilpotent matrices is the Lie algebra of the Lie
group of upper triangular matrices with ones on the diagonal. Recall the
formula for the logarithm

$\log(B)=\sum_{k=1}^{\infty}(-1)^{k+1}\frac{\lparen
B-\mathrm{I}\rparen^{k}}{k}.$

Whenever $B$ is upper triangular with ones on the diagonal, $B-\mathrm{I}$ is
nilpotent, so the series converges. As such, all these matrices have one and
just one logarithm in $U$. In particular, the exponential is a bijection on
this set. ∎

##  Appendix D Gradient of the Matrix Exponential

In this section we give a formula for the gradient of the pullback of a
function by the matrix exponential. The implementation of these formulas in
practice and how can they be applied on different manifolds is considered in
Appendix E.

We will prove a stronger result, which also applies to other matrix functions
like $\cos(X)$, $\sin(X)$ and, with minor modifications, to functions like
$\sqrt{X}$, $X^{1/n}$, and $\log(X)$.888See the remark after the proof of the
theorem.

######  Theorem D.1.

Consider a real analytic function

$\\!\begin{aligned} \phi\colon\mathbb{R}&\to\mathbb{R}\\\
x&\mapsto\sum_{n=0}^{\infty}\frac{a_{n}}{n!}x^{n}\end{aligned}$

with associated matrix function

$\\!\begin{aligned} \phi\colon\mathbb{R}^{n\times n}&\to\mathbb{R}^{n\times
n}\\\ X&\mapsto\sum_{n=0}^{\infty}\frac{a_{n}}{n!}X^{n}\end{aligned}$

We then have that, for the canonical inner product $\lparen
A_{1},A_{2}\rparen=\operatorname{tr}\lparen A_{1}^{\intercal}A_{2}\rparen$,

$\lparen\mathrm{d}\phi\rparen^{\ast}_{X}=\lparen\mathrm{d}\phi\rparen_{X^{\intercal}}\qquad
X\in\mathbb{R}^{n\times n}.$

###### Proof.

We can compute the differential of $\phi$ as

$\lparen\mathrm{d}\phi\rparen_{X}(E)=\sum_{n=0}^{\infty}\Big{\lparen}\frac{a_{n}}{n!}\sum_{i=0}^{n}X^{i}EX^{n-i}\Big{\rparen}.$

By linearity, it is enough to compute the adjoint of functions of the form
$X\mapsto X^{i}EX^{n-i}$.

Observe that the adjoint of the left multiplication $L_{A}(X)=AX$ is exactly
$L_{A^{\intercal}}$

$\langle L_{A}(X),Y\rangle\coloneqq\operatorname{tr}\lparen\lparen
AX\rparen^{\intercal}Y\rparen=\operatorname{tr}\lparen
X^{\intercal}A^{\intercal}Y\rparen=\langle X,L_{A^{\intercal}}(Y)\rangle.$

In the case of right multiplication, we also get
$R^{\ast}_{A}=R_{A^{\intercal}}$.

Finally, we just have to apply this formula to the functions
$L_{X^{i}}(E)=X^{i}E$ and $R_{X^{n-i}}(E)=EX^{n-i}$, and noting that $X\mapsto
X^{i}EX^{n-i}=L_{X^{i}}(R_{X^{n-i}}(E))$, and that for any two functions,
$(f\circ g)^{\ast}=g^{\ast}\circ f^{\ast}$, we get the result. ∎

After obtaining this more general result, we thought that this should be
folklore in some areas of functional analysis and numerical analysis. In fact,
this result can be found without proof in Higham [2008, p.66].

######  Remark.

The generalization of this result to functions complex functions is direct,
modulo computing the differential of the analytic function with conjugate
coefficients in its Taylor series. In this case, one can interpret this
theorem by saying that “the adjoint of the differential is the differential of
the adjoint at the adjoint”, noting the two different meanings of the word
_adjoint_ in the sentence.

In the complex setting, one can formulate the theorem for a holomorphic
function defined just on an open subset $U\subseteq\mathbb{C}$, and define the
function on matrices on the set of matrices such that their spectrum is
contained in $U$, hence making sense also of functions like $\log(X)$.

The result still holds true for many other inner product in
$\mathbb{C}^{n\times n}$ (or $\mathbb{R}^{n\times n}$), in particular, for
those for which for every matrix $X$ there exists a matrix $Y$ such that
$L^{\ast}_{X}=L_{Y}$. If this is the case, we write $X^{\ast}\coloneqq Y$ and
the theorem still holds true, as in this case, $R^{\ast}_{X}=R_{X^{\ast}}$.
Most of the scalar products on matrix spaces that appear in differential
geometry have this property. For example, if we have a symmetric positive
definite matrix $G\in\mathbb{R}^{n\times n}$ and we define the following
product $\langle X,Y\rangle\coloneqq\operatorname{tr}\lparen
X^{\intercal}GY\rparen$, then we have that $X^{\ast}=\lparen
GXG^{-1}\rparen^{\intercal}$.

We can now state the case of $\exp(X)$ as a corollary of Theorem D.1 and
Corollary B.2.

######  Corollary D.2 (Gradient of the matrix parametrization).

Let $f\colon\operatorname{GL}\lparen n\rparen\to\mathbb{R}$ be a smooth
function, the gradient of $f\circ\exp$ at a matrix
$A\in\operatorname{\mathfrak{gl}}\lparen n\rparen\cong\mathbb{R}^{n\times n}$
with respect to the canonical metric at a matrix $B\in\operatorname{GL}\lparen
n\rparen$, $\langle A_{1},A_{2}\rangle_{B}=\operatorname{tr}\lparen
A_{1}^{\intercal}A_{2}\rparen$ is given by

$\nabla\lparen f\circ\exp\rparen\lparen
A\rparen=\lparen\mathrm{d}\exp\rparen_{A^{\intercal}}\lparen\nabla
f(e^{A})\rparen.$

Using the chain rule, we can also compute the gradient with respect to the
dynamic Lie trivialization $\exp_{B}$.

######  Corollary D.3.

Let $f\colon\operatorname{GL}\lparen n\rparen\to\mathbb{R}$ be a smooth
function, and let $B\in\operatorname{GL}\lparen n\rparen$. The gradient of
$f\circ\exp_{B}$ at a matrix $A\in T_{B}\operatorname{GL}\lparen
n\rparen\cong\operatorname{\mathfrak{gl}}\lparen
n\rparen\cong\mathbb{R}^{n\times n}$ with respect to the canonical metric
$\langle A_{1},A_{2}\rangle_{B}=\operatorname{tr}\lparen
A_{1}^{\intercal}A_{2}\rparen$ is given by

$\nabla\lparen f\circ\exp_{B}\rparen\lparen A\rparen=\lparen
B^{-1}\rparen^{\intercal}\lparen\mathrm{d}\exp\rparen_{\lparen
B^{-1}A\rparen^{\intercal}}\lparen B^{\intercal}\nabla f(\exp_{B}(A))\rparen.$

######  Remark.

These two corollaries still hold if we replace $\operatorname{GL}\lparen
n\rparen$ by any real matrix Lie group with this metric. The complex case is
analogous.

######  Remark.

In Lezcano-Casado and Martínez-Rubio [2019] the following slightly different
formula for the gradient of the exponential is derived for compact real matrix
Lie groups:

$\nabla\lparen
f\circ\exp\rparen(A)=e^{A}\lparen\mathrm{d}\exp\rparen_{-A}\lparen
e^{-A}\nabla f(\exp(A))\rparen.$

This formula agrees with the one presented here, as it turns out that
multiplication by $e^{A}$ commutes with $\lparen\mathrm{d}\exp\rparen_{-A}$.
This can be seen, for example, modifying the proof of formula for the
derivative of exponential map in Rossmann [2006, Chapter 1, Theorem 5] to
obtain

$\lparen\mathrm{d}\exp\rparen_{A}(X)=\sum_{k=0}^{\infty}\frac{\lparen-\operatorname{ad}_{A}\rparen^{k}}{(k+1)!}(e^{A}X).$

Finally, if $G$ is a real compact matrix Lie group together with a bi-
invariant metric, one has that for every $A\in\mathfrak{g}$, $A^{\ast}=-A$,
where $A^{\ast}$ should be understood in the sense of
$L^{\ast}_{A}=L_{A^{\ast}}$. This can be seen, for example, considering that a
real compact matrix Lie group is either a subgroup of the orthogonal group or
a conjugate of one. Using this, we finally see that the formula presented in
Lezcano-Casado and Martínez-Rubio [2019] is equivalent to Corollary D.2.

##  Appendix E Examples of Matrix Manifolds and Specific Trivializations

This section has an expository purpose. It is intended as a compilation of
useful results for the implementation of different trivializations. We will go
over the forms that the Lie exponential and the Riemannian
exponential—geodesics—take in different manifolds that are useful in the field
of machine learning.

We will deliberately develop as least theory as possible, but we will still
point out the relevant literature sources as _remarks_ , for those interested
in the theoretical background. At the end, we will also describe some
retractions, which are useful for problems on which computing the geodesics or
the Lie exponential is too expensive.

We will put as examples some Lie groups, the sphere and the hyperbolic space,
the Stiefel manifold, and the space of symmetric positive definite matrices.

######  Remark.

On some of the manifolds considered below, the metric is not the canonical one
given by $\langle A_{1},A_{2}\rangle_{B}=\operatorname{tr}\lparen
A_{1}^{\intercal}A_{2}\rparen$, but often a left-translation of this one of
the form

$\langle A_{1},A_{2}\rangle_{B}=\operatorname{tr}\lparen\lparen
B^{-1}A_{1}\rparen^{\intercal}B^{-1}A_{2}\rparen\qquad\forall A_{1},A_{2}\in
T_{B}\mathcal{M}.$

For these metrics, when we compute the gradient, we cannot use Corollary D.2
directly. On the other hand, after a similar reasoning, we get that the
differential with respect to these metrics is given by the formula

$\nabla\lparen f\circ\exp\rparen\lparen
A\rparen=B\lparen\mathrm{d}\exp\rparen_{A^{\intercal}}\lparen B^{-1}\nabla
f(e^{A})\rparen.$

We can also deduce this formula just noting that, for these metrics, left
translations are isometries by construction.

###  E.1 Compact matrix Lie groups

On a Lie group, we can identify all the tangent spaces using left
multiplication. In particular, we have that

$T_{B}G=\\{BA\>|\>A\in\mathfrak{g}\\}\qquad B\in G$

where $\mathfrak{g}\coloneqq T_{e}G$ is the tangent space at the identity: the
Lie algebra of $G$. As such, if we know the structure of $\mathfrak{g}$ we can
parametrize any tangent space of $G$.

For compact Lie groups, the Lie exponential and the Riemannian exponential
agree999Here we are assuming that we consider the group $G$ together with a
bi-invariant metric. For compact matrix Lie groups this metric is exactly
$\langle A_{1},A_{2}\rangle_{B}=\operatorname{tr}\lparen
A_{1}^{\intercal}A_{2}\rparen$. For more on this, we refer the reader Lezcano-
Casado and Martínez-Rubio [2019, Appendix C.1.]. and take the form

$\exp_{G,B}(\tilde{A})=\exp_{B}(\tilde{A})=B\exp(B^{-1}\tilde{A})=B\exp(A)\qquad
A\in\mathfrak{g}.$ (2)

where $\exp$ is the exponential of matrices and we still used the
identification $\tilde{A}=BA$. For these groups, the Riemannian exponential is
surjective.

These Lie groups were already presented in Lezcano-Casado and Martínez-Rubio
[2019] in the context of optimization for neural networks. In that paper, this
trivialization was only considered in the static case, namely
$\exp\colon\mathfrak{g}\to G$.

The gradient of Equation 2 is given by Proposition 6.1.

Finally, for compact matrix Lie groups, in order to use this formula to
implement the dynamic trivialization method, we are just missing the
expression for the Lie algebra $\mathfrak{g}\subseteq\mathbb{R}^{n\times n}$
of the Lie group in which we are interested. We give a list of some of these
below.

##### Special orthogonal group

$\operatorname{SO}\lparen n\rparen=\\{B\in\mathbb{R}^{n\times
n}\>|\>B^{\intercal}B=\mathrm{I},\det
B=1\\}\qquad\operatorname{\mathfrak{so}}\lparen
n\rparen=\operatorname{Skew}\lparen n\rparen=\\{A\in\mathbb{R}^{n\times
n}\>|\>A^{\intercal}=-A\\},$

##### Unitary group

$\operatorname{U}\lparen n\rparen=\\{B\in\mathbb{C}^{n\times
n}\>|\>B^{\ast}B=\mathrm{I}\\}\qquad\operatorname{\mathfrak{u}}\lparen
n\rparen=\\{A\in\mathbb{C}^{n\times n}\>|\>A^{\ast}=-A\\},$

##### Special unitary group

$\operatorname{SU}\lparen n\rparen=\\{B\in\mathbb{C}^{n\times
n}\>|\>B^{\ast}B=\mathrm{I},\det
B=1\\}\qquad\operatorname{\mathfrak{su}}\lparen
n\rparen=\\{A\in\mathbb{C}^{n\times
n}\>|\>A^{\ast}=-A,\operatorname{tr}A=0\\}.$

##### Complex torus

$\operatorname{\mathbb{T}}\lparen
n,\mathbb{C}\rparen=\\{B\in\operatorname{Diag}\lparen
n,\mathbb{C}\rparen\>|\>\lvert
B_{ii}\rvert=1\\}\qquad\operatorname{\mathfrak{t}}\lparen
n,\mathbb{C}\rparen=\\{A\in\operatorname{Diag}\lparen
n,\mathbb{C}\rparen\>|\>A_{ii}\in i\mathbb{R}\subseteq\mathbb{C}\\},$

######  Remark.

We say that $\operatorname{\mathbb{T}}\lparen n,\mathbb{C}\rparen$ is a torus
because it is a product of $n$ circles. This can easily be seen simply
defining the circle as $S^{1}=\\{z\in\mathbb{C}\>|\>\lvert z\rvert=1\\}$, so
that $\operatorname{\mathbb{T}}\lparen n,\mathbb{C}\rparen\cong
S^{1}\times\dots\times S^{1}$. In this case, the correspondence between the
Lie algebra and the Lie group is given by the Euler formula.

##### Real torus

The real torus $\operatorname{\mathbb{T}}\lparen 2n,\mathbb{R}\rparen$
consists of the $2n\times 2n$ block-diagonal matrices with blocks of the form

$\begin{pmatrix}\cos(\theta)&-\sin(\theta)\\\
\sin(\theta)&\cos(\theta)\end{pmatrix}\qquad\theta\in[-\pi,\pi].$

Note that is exactly the matrix representation of the complex number
$e^{\theta i}$. In this case, its Lie algebra is given by the block-diagonal
matrices with blocks given by

$\begin{pmatrix}0&-a\\\ a&0\end{pmatrix}\qquad a\in\mathbb{R}.$

######  Remark.

In the case of the real and complex torus, the exponential is a Riemannian
covering map, this meaning that, in particular, it is always a local isometry,
and it does not create local minima or saddle points. For this reason, to
optimize on these two manifolds, we would not need to use dynamic
trivializations, given that a static trivialization would work just fine as a
direct corollary of Theorem 4.3.

###  E.2 The groups $\operatorname{GL^{+}}\lparen n\rparen$ and
$\operatorname{SL}\lparen n\rparen$

We then look at two more Lie groups on which we can compute the Riemannian
exponential. These groups are of primal importance for problems that require
invertible matrices or the study of volume-flows, like normalizing flows.

These groups are also an important example of groups on which the Riemannian
exponential and the Lie exponential do not agree, and thus, in this case, we
have two different trivialization schemes.

Furthermore, the Lie exponential is not surjective on these groups, so these
are also examples of a retraction that could not be used as a static
trivialization, but it can be used as a dynamic one.

##### Positive general linear group

$\operatorname{GL^{+}}\lparen n\rparen=\\{B\in\mathbb{R}^{n\times n}\>|\>\det
B>0\\}\qquad\operatorname{\mathfrak{gl}}\lparen n\rparen=\mathbb{R}^{n\times
n}.$

This is the connected component containing the identity matrix of the general
linear group

$\operatorname{GL}\lparen n\rparen=\\{B\in\mathbb{R}^{n\times n}\>|\>\det
B\neq 0\\}.$

##### Special linear group

$\operatorname{SL}\lparen n\rparen=\\{B\in\mathbb{R}^{n\times n}\>|\>\det
B=1\\}\qquad\operatorname{\mathfrak{sl}}\lparen
n\rparen=\\{A\in\mathbb{R}^{n\times n}\>|\>\operatorname{tr}A=0\\}.$

######  Remark.

The orthogonal projection from $\mathbb{R}^{n\times n}$ onto
$\operatorname{\mathfrak{sl}}\lparen n\rparen$ is given by

$\\!\begin{aligned} \pi_{\operatorname{\mathfrak{sl}}\lparen
n\rparen}\colon\mathbb{R}^{n\times n}&\to\operatorname{\mathfrak{sl}}\lparen
n\rparen\\\ A&\mapsto
A-\tfrac{1}{n}\operatorname{tr}(A)\mathrm{I}\end{aligned}$

We can use this formula to parametrize $\operatorname{\mathfrak{sl}}\lparen
n\rparen$, in the same way that we use $A\mapsto\frac{1}{2}\lparen
A-A^{\intercal}\rparen$ to parametrize $\operatorname{\mathfrak{so}}\lparen
n\rparen\cong\operatorname{Skew}\lparen n\rparen$.

On these groups have two different trivializations based on the exponential of
matrices.

On the one hand, we still have the dynamic Lie trivialization $\exp_{B}$
presented in Section E.1.

On the other hand, if $G$ is $\operatorname{GL}\lparen n\rparen$ or
$\operatorname{SL}\lparen n\rparen$ for $n>2$ equipped with the metric
$\langle\tilde{A}_{1},\tilde{A}_{2}\rangle_{B}=\operatorname{tr}\lparen\lparen
B^{-1}\tilde{A}_{1}\rparen^{\intercal}B^{-1}\tilde{A}_{2}\rparen$, we have
that the Riemannian trivialization for these groups is given by 101010This
result applies not only to $\operatorname{SL}\lparen n\rparen$, but to any
semisimple Lie group equipped with the left-invariant metric associated to the
Killing form.

$\exp_{G,B}(BA)=B\exp\lparen A^{\intercal}\rparen\exp\lparen
A-A^{\intercal}\rparen\quad\text{for }A\in\mathfrak{g}.$

Note that $BA\in T_{B}G$, as one would expect.

######  Remark.

This result was first stated in Wang et al. [1969], and a proof of it can be
found in Helgason [1979, Chapter 6, Exercise A.9]. For the proof for
$\operatorname{GL}\lparen n\rparen$, see Andruchow et al. [2014, Theorem
$2.14$].

We can then compute the gradient of this parametrization as we know how to
compute the gradient of the exponential map with respect to this metric, as
detailed at the beginning of Appendix E.

######  Remark.

It happens that the Lie exponential is not surjective on
$\operatorname{SL}\lparen n\rparen$ so, in this case, it would not be possible
to set $K=\infty$ in the dynamic trivialization algorithm, that is, it would
be necessary to change the basis of the trivialization. The Lie trivialization
is not surjective on $\operatorname{GL^{+}}\lparen n,\mathbb{R}\rparen$
either, but it is surjective on $\operatorname{GL}\lparen
n,\mathbb{C}\rparen$, with $\operatorname{\mathfrak{gl}}\lparen
n,\mathbb{C}\rparen\cong\mathbb{C}^{n\times n}$.

These are examples for which using dynamic trivializations allow us to use
certain parametrizations that we would not be able to use in the context of
static trivializations.

The Riemannian exponential on $\operatorname{SL}\lparen n\rparen$ and
$\operatorname{GL}\lparen n,\mathbb{R}\rparen$ is surjective with this metric.

######  Remark.

On these two manifolds, we can also use their polar decomposition as a
trivialization to optimize over them, see Hall [2015, Proposition $2.19$].

###  E.3 Naturally reductive homogeneous spaces

In this section we touch on a few of the most used manifolds in optimization,
namely the Stiefel manifold, the sphere, the hyperbolic space, and the
symmetric positive definite matrices.

In this section we will restrict ourselves to expose the formulae for the
exponential on these manifolds for certain metric. Most of these manifolds
fall under the theory of symmetric manifolds, or the more general theory of
naturally reductive homogeneous spaces. For a derivation of the fomulae in
this section in the more general context of naturally reductive homogeneous
spaces, we refer the reader to the self-contained exposition in Gallier and
Quaintance [2019, Chapter 22].

####  E.3.1 Stiefel manifold

The Stiefel manifold is the manifold of $n\times k$ matrices with $k\leq n$
with orthonormal columns. Equivalently, it is the set of orthonormal
$k$-frames on $\mathbb{R}^{n}$. In symbols we can see the Stiefel manifold as
a submanifold of $\mathbb{R}^{n\times k}$ as follows:

$\operatorname{St}\lparen n,k\rparen\coloneqq\\{B\in\mathbb{R}^{n\times
k}\>|\>B^{\intercal}B=\mathrm{I}_{k}\\}\qquad T_{B}\operatorname{St}\lparen
n,k\rparen=\\{\tilde{A}\in\mathbb{R}^{n\times
k}\>|\>B^{\intercal}\tilde{A}\in\operatorname{\mathfrak{so}}\lparen
k\rparen\\}$

Note that $\operatorname{St}\lparen n,n\rparen\cong\operatorname{O}\lparen
n\rparen$. In this case, compare the formula of the tangent space with that
given for $T_{B}\operatorname{SO}\lparen n\rparen$ Lie groups in Section E.1,
in particular that of $\operatorname{\mathfrak{so}}\lparen n\rparen$.

If we consider any completion of the frame $B$ into a basis of
$\mathbb{R}^{n}$, that is, a matrix $B_{\bot}\in\mathbb{R}^{n\times n-k}$ such
that $\begin{pmatrix}B&B_{\bot}\end{pmatrix}\in\operatorname{O}\lparen
n\rparen$, we have the more computationally amenable description of the
tangent spaces of $\operatorname{St}\lparen n,k\rparen$

$T_{B}\operatorname{St}\lparen
n,k\rparen=\\{BA+B_{\bot}A_{\bot}\in\mathbb{R}^{n\times
k}\>|\>A\in\operatorname{\mathfrak{so}}\lparen
k\rparen,A_{\bot}\in\mathbb{R}^{n-k\times k}\\}.$

Note that if $n=k$, $T_{B}\operatorname{St}\lparen
n,n\rparen=\\{BA\>|\>A\in\operatorname{\mathfrak{so}}\lparen n\rparen\\}$ and
we still recover the same definition from Section E.1.

The canonical metric 111111We say that this is the canonical metric because it
is the one inherited from the quotient structure—as a homogeneous space—of
$\operatorname{St}\lparen n,k\rparen$ as $\operatorname{St}\lparen
n,k\rparen\cong\operatorname{O}\lparen n\rparen/\operatorname{O}\lparen
n-k\rparen$. If we put the Euclidean metric $\operatorname{tr}\lparen
X^{\intercal}Y\rparen$ on $\operatorname{O}\lparen n\rparen$, this metric is
bi-invariant under the action of $\operatorname{O}\lparen n-k\rparen$ and
descends into the canonical metric on the quotient manifold
$\operatorname{O}\lparen n\rparen/\operatorname{O}\lparen n-k\rparen$
described here. For the exact computations see Edelman et al. [1998]. on the
Stiefel manifold is given for $B\in\operatorname{St}\lparen n,k\rparen$,
$\tilde{A}_{1},\tilde{A}_{2}\in T_{B}\operatorname{St}\lparen n,k\rparen$ by

$\langle\tilde{A}_{1},\tilde{A}_{2}\rangle_{B}=\operatorname{tr}\lparen\tilde{A}^{\intercal}_{1}\lparen\mathrm{I}_{n}-\tfrac{1}{2}BB^{\intercal}\rparen\tilde{A}_{2}\rparen$

With the notation as above, consider the QR decomposition
$QR=(\mathrm{I}_{n}-BB^{\intercal})\tilde{A}$ with
$Q\in\operatorname{St}\lparen n,k\rparen$, $R\in\mathbb{R}^{k\times k}$, then
we have that is the we have that the Riemannian exponential is given

$\exp_{\operatorname{St}\lparen
n,k\rparen,B}(\tilde{A})=\begin{pmatrix}B&Q\end{pmatrix}\exp\begin{pmatrix}A&-R\\\
R&0\end{pmatrix}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}.$

######  Remark.

The computational cost of computing geodesics on $\operatorname{St}\lparen
n,k\rparen$ is then dominated by the computation of a thin-QR factorization of
a $n\times k$ matrix and the computation of a exponential of a skew-symmetric
$2k\times 2k$ matrix.

If $2k>n$, a more efficient algorithm is possible. We just have to compute the
geodesics on $\operatorname{SO}\lparen n\rparen$ as per Section E.1 and then
drop then project the result onto $\operatorname{St}\lparen n,k\rparen$
dropping the last $n-k$ columns. This process requires the computation of just
one exponential of an $n\times n$ matrix. This process is equivalent to the
formula described above.

######  Remark.

In Edelman et al. [1998, Section 2.2.2] the authors give a formula for the
geodesics of $\operatorname{St}\lparen n,k\rparen$ seen as a submanifold of
$\mathbb{R}^{n\times k}$, that is, with the metric
$\langle\tilde{A}_{1},\tilde{A}_{2}\rangle=\operatorname{tr}\lparen\tilde{A}^{\intercal}_{1}\tilde{A}_{2}\rparen$.
In Section 2.4.1 they also discuss an essential difference between the
Euclidean metric and the canonical metric on the Stiefel manifold.

####  E.3.2 The sphere and the hyperbolic plane

The case of the sphere $S^{n}=\\{x\in\mathbb{R}^{n+1}\>|\>\lVert x\rVert=1\\}$
is probably one of the most classical ones. We will always consider the _round
sphere_ , this is, the sphere as a subset of $\mathbb{R}^{n+1}$ together with
the metric inherited from $\mathbb{R}^{n+1}$.

Its tangent space at a point $x\in S^{n}$ is simply given by the set of
vectors orthogonal to it

$T_{x}S^{n}=\\{v\in\mathbb{R}^{n}\>|\>\langle x,v\rangle=0\\}.$

and the geodesics are given by

$\exp_{S^{n},x}(v)=\cos(\lVert v\rVert)x+\sin(\lVert v\rVert)\frac{v}{\lVert
v\rVert}.$

To describe the $n$-dimensional hyperbolic space, first consider the diagonal
matrix $\mathrm{I}_{n,1}$ with $n$ positive ones and a negative one in its
diagonal. We will use the following notation

$\langle x,y\rangle_{\operatorname{\mathbb{H}}}\coloneqq\langle
x,\mathrm{I}_{n,1}y\rangle=\sum_{i=1}^{n}x_{i}y_{i}-x_{n+1}y_{n+1}\qquad\forall
x,y\in\mathbb{R}^{n+1}$

and denote by $\lVert x\rVert_{\operatorname{\mathbb{H}}}=\sqrt{\langle
x,x\rangle_{\operatorname{\mathbb{H}}}}$ whenever $\langle
x,x\rangle_{\operatorname{\mathbb{H}}}\geq 0$.

With this notation, the $n$-dimensional hyperbolic space
$\operatorname{\mathbb{H}}^{n}$ can be seen as the submanifold of
$\mathbb{R}^{n+1}$ defined by

$\operatorname{\mathbb{H}}^{n}=\\{x\in\mathbb{R}^{n+1}\>|\>\langle
x,x\rangle_{\operatorname{\mathbb{H}}}=-1,x_{n+1}>0\\}$

with tangent space at $x\in\operatorname{\mathbb{H}}^{n}$ given by

$T_{x}\operatorname{\mathbb{H}}^{n}=\\{v\in\mathbb{R}^{n+1}\>|\>\langle
x,v\rangle_{\operatorname{\mathbb{H}}}=0\\}.$

The geodesics are then given by

$\exp_{\operatorname{\mathbb{H}}^{n},x}(v)=\cosh(\lVert
v\rVert_{\operatorname{\mathbb{H}}})x+\sinh(\lVert
v\rVert_{\operatorname{\mathbb{H}}})\frac{v}{\lVert
v\rVert_{\operatorname{\mathbb{H}}}}.$

######  Remark.

The formula for the sphere is just a particular case of the one given for
$\operatorname{St}\lparen n+1,1\rparen\cong S^{n}$.

The reason why the formulas of the geodesics on the sphere and the hyperbolic
plane are so similar has a geometric meaning. This can be seen in a more
general case, considering the oriented Grassmannian manifold and the
hyperbolic Grassmannian. The sphere and the hyperbolic plane are special cases
of these manifolds. These manifolds are _symmetric spaces_ and they are dual
to each other. For more on the duality between symmetric spaces of compact and
non-compact type, we refer the reader to Helgason [1979, Chapter 5, Example 1]
or O’Neill [1983, Chapter 11].

######  Remark.

In the same spirit as we can compute the geodesics on
$\operatorname{St}\lparen n,k\rparen$ by taking a geodesic in
$\operatorname{SO}\lparen n\rparen$ and projecting it down to
$\operatorname{St}\lparen n,k\rparen$, we can also compute the geodesics of
the real projective plane $\operatorname{\mathbb{RP}}^{n}$ by computing the
geodesic on $S^{n}$ and projecting it down to
$\operatorname{\mathbb{RP}}^{n}$. The metric induced on
$\operatorname{\mathbb{RP}}^{n}$ is called the _standard round metric_ on
$\operatorname{\mathbb{RP}}^{n}$. If we perform the same process between
$S^{2n+1}$ and $\operatorname{\mathbb{CP}}^{n}$ and, in this case, we would
get the _Fubini-Study_ metric. This construction arises naturally in the
context of principal bundles with invariant metrics.

####  E.3.3 The symmetric positive definite matrices

The symmetric positive definite matrices $\operatorname{Sym}^{+}\lparen
n\rparen$ do not form a Lie group, as they are not closed under matrix
multiplication, but they are a symmetric space.

When seen as a subset of $\mathbb{R}^{n\times n}$, we can endow it with a
left-invariant metric defined as
$\langle\tilde{A}_{1},\tilde{A}_{2}\rangle_{B}=\operatorname{tr}\lparen
B^{-1}A_{1}B^{-1}A_{2}\rparen$. The tangent space at a point
$B\in\operatorname{Sym}^{+}\lparen n\rparen$ is given by

$T_{B}\operatorname{Sym}^{+}\lparen
n\rparen=\\{B^{1/2}AB^{1/2}\>|\>A\in\operatorname{\mathfrak{sym}}\lparen
n\rparen\\}$

where $\operatorname{\mathfrak{sym}}\lparen n\rparen$ is the tangent space at
the identity, given by the symmetric matrices

$\operatorname{\mathfrak{sym}}\lparen n\rparen=\\{A\in\mathbb{R}^{n\times
n}\>|\>A^{\intercal}=A\\}.$

Note that for a symmetric positive definite matrix the square root is well
defined, as symmetric positive definite matrices are diagonalizable, and the
square root is just the matrix whose eigenvalues are the (positive) square
root of the eigenvalues of the initial matrix.

Following the notation for Lie groups, if we denote
$\tilde{A}=B^{1/2}AB^{1/2}$, we have that

$\exp_{\operatorname{Sym}^{+}\lparen n\rparen,B}(\tilde{A})=B^{1/2}\exp\lparen
B^{-1/2}\tilde{A}B^{-1/2}\rparen B^{1/2}=B^{1/2}\exp\lparen A\rparen B^{1/2}.$

######  Remark.

In this case, this manifold also constitutes an example of a symmetric space
since $\operatorname{Sym}^{+}\lparen n\rparen\cong\operatorname{GL^{+}}\lparen
n\rparen/\operatorname{O}\lparen n\rparen$. The metric considered here is the
natural one with respect to this structure. An introduction to the
computational aspects of this manifold can be found in Bonnabel and Sepulchre
[2009].

###  E.4 Some retractions

For now we have just mentioned examples regarding either the Lie exponential
or the Riemannian exponential, but the dynamic trivialization framework allows
us to use any function that is a retraction. In order to make use of arbitrary
retractions, we just have to be able to compute the gradient of the function
when precomposed with them. We will do so for a few important examples in this
section.

In the case of the two retractions mentioned in Section 6.3, the Cayley map
and projectors, their derivatives are already implemented in the major deep-
learning packages, like Pytorch or Tensorflow. The first one just requires an
inverse (or, more efficiently and stable, the solution of a system of the form
$AX=B$) and the second one just requires the derivatives with respect to the
SVD decomposition.

The retraction induced by a projector can be easily implemented for most
manifolds. For example, for the sphere takes just the form
$x\mapsto\frac{x}{\lVert x\rVert}$, whose derivative can also be computed just
using autodiff.

For the symmetric positive definite matrices, we have the retraction from the
symmetric matrices into the positive semidefinite matrices given by $A\mapsto
A^{2}$. This one is similar to the frequently used from the upper triangular
matrices given by the Cholesky decomposition $L\mapsto LL^{\intercal}$. The
former has the advantage that we have access to $A$ which is the square root
of its image. This can be helpful, as sometimes the square root of the matrix
is needed for some computations, as we have seen in Section E.3.3. The
retraction given by the Cholesky decomposition has the advantage that, if the
diagonal of the upper-triangular matrix $L$ is strictly positive, then
$LL^{\intercal}$ will be positive definite. For this reason this retraction is
often used to parametrize variance kernels in Bayesian statistics.

Another retraction for $\operatorname{Sym}^{+}\lparen n\rparen$ is given by
the exponential of matrices $\exp\colon\operatorname{\mathfrak{sym}}\lparen
n\rparen\to\operatorname{Sym}^{+}\lparen n\rparen$ which is a diffeomorphism.
As such, it provides a rather good, although expensive, option to parametrize
this manifold.

For a much more in-depth treatment of retractions, we refer the reader to
Absil et al. [2009].

##  Appendix F Detailed Experiment Set-Up and Hyperparameters

We tried to reproduce as faithfully as possible the set-up from previous
experiments, to achieve a fair comparison. The batch size for all the
experiments is $128$. We fixed the seed to be $5544$ of both Numpy and Pytorch
for reproducibility in the final runs.

The exact architecture to process for a sequence of inputs
$x_{t}\in\mathbb{R}^{d}$ with a hidden size $p$ is given by the formula

$h_{t+1}=\sigma\lparen\exp(A)h_{t}+Tx_{t+1}\rparen$

with $A\in\operatorname{Skew}\lparen p\rparen$ and $T\in\mathbb{R}^{p\times
d}$. $\sigma$ is the modrelu non-linearity introduced in Arjovsky et al.
[2016].

The initialization _Henaff_ refers to initializing the diagonal blocks of the
skew-symmetric matrices with elements sampled from the uniform distribution
$\mathcal{U}\lparen-\pi,\pi\rparen$ as detailed in Henaff et al. [2016]. The
_Cayley_ initialization refers to sampling the diagonal from a distribution
$u\sim\mathcal{U}\lparen 0,\pi/2\rparen$ and then computing
$s=-\sqrt{\frac{1-\cos(u)}{1+\cos(u)}}$ as detailed in Helfrich et al. [2018].

As we mentioned in the experiments section, we did not include the copying
experiment that was usually used in previous papers, given that, as it was
demonstrated in Lezcano-Casado and Martínez-Rubio [2019], the exponential
trivialization converges to the exact solution even when based at the
identity. The same happens when used with the dynamic trivialization, so we do
not think that this experiment adds anything to the results.

Table 3: Hyperparameters for dtriv$1$. Dataset | Size | Optimizer | Learning Rate | Orthogonal optimizer | Orthogonal Learning Rate
---|---|---|---|---|---
mnist | $170$ | rmsprop | $10^{-3}$ | rmsprop | $10^{-4}$
$360$ | $10^{-3}$ | $10^{-4}$
$512$ | $5\cdot 10^{-4}$ | $7\cdot 10^{-5}$
p-mnist | $170$ | $7\cdot 10^{-4}$ | $2\cdot 10^{-4}$
$360$ | $7\cdot 10^{-4}$ | $7\cdot 10^{-5}$
$512$ | $5\cdot 10^{-4}$ | $5\cdot 10^{-5}$
timit | $224$ | adam | $10^{-3}$ | rmsprop | $10^{-4}$
$322$ | $10^{-3}$ | $10^{-4}$
$425$ | $10^{-3}$ | $10^{-4}$
Table 4: Hyperparameters for dtriv$100$. Dataset | Size | Optimizer | Learning Rate | Orthogonal optimizer | Orthogonal Learning Rate
---|---|---|---|---|---
mnist | $170$ | rmsprop | $5\cdot 10^{-4}$ | rmsprop | $10^{-4}$
$360$ | $3\cdot 10^{-4}$ | $5\cdot 10^{-5}$
$512$ | $5\cdot 10^{-4}$ | $10^{-4}$
p-mnist | $170$ | $7\cdot 10^{-4}$ | $10^{-4}$
$360$ | $5\cdot 10^{-4}$ | $7\cdot 10^{-5}$
$512$ | $5\cdot 10^{-4}$ | $5\cdot 10^{-5}$
timit | $224$ | adam | $10^{-3}$ | rmsprop | $2\cdot 10^{-4}$
$322$ | $10^{-3}$ | $2\cdot 10^{-4}$
$425$ | $10^{-3}$ | $10^{-4}$
Table 5: Hyperparameters for dtriv$\infty$. Dataset | Size | Optimizer | Learning Rate | Orthogonal optimizer | Orthogonal Learning Rate
---|---|---|---|---|---
mnist | $170$ | rmsprop | $7\cdot 10^{-4}$ | rmsprop | $10^{-4}$
$360$ | $5\cdot 10^{-4}$ | $10^{-4}$
$512$ | $10^{-4}$ | $7\cdot 10^{-5}$
p-mnist | $170$ | $7\cdot 10^{-4}$ | $2\cdot 10^{-4}$
$360$ | $7\cdot 10^{-4}$ | $5\cdot 10^{-5}$
$512$ | $3\cdot 10^{-4}$ | $7\cdot 10^{-5}$
timit | $224$ | adam | $10^{-3}$ | rmsprop | $2\cdot 10^{-4}$
$322$ | $10^{-3}$ | $2\cdot 10^{-4}$
$425$ | $10^{-3}$ | $2\cdot 10^{-4}$