Showing posts with label Manifold. Show all posts

Saturday, September 14, 2024

Lie Algebra on SO3 Groups in Python

Target audience: Advanced

Estimated reading time: 5'

Posts history

Newsletter: Geometric Learning in Python

Curious about manifolds and the SO(3) Lie group?
Your next step is to explore its associated Lie algebra, which lies in the tangent space. This algebra is a linear space with the same dimension as the Lie group, closed under a bilinear alternating operation known as the Lie bracket. The Lie algebra of SO(3), denoted as so3, consists of all 3x3 skew-symmetric matrices.

What you will learn: How to compute SO3 rotation matrices from tangent vector and extract Lie algebra from points on SO3 manifolds.

Table of content

Lie algebra on SO3

Implementation

Setup

Projector operator

Lie bracket

References

Notes:

This post is a follow up on a previous post on SO3 Lie groups [ref 1] and leverage articles related to differential geometry and geometry learning [ref 2, 3, 4 and 5]
Environments: Python 3.11, Matplotlib 3.9, Geomstats 2.8.0
Source code is available at Github.com/patnicolas/Data_Exploration/Lie
To enhance the readability of the algorithm implementations, we have omitted non-essential code elements like error checking, comments, exceptions, validation of class and method arguments, scoping qualifiers, and import statement.

Disclaimer : A thorough tutorial and explanation of Lie groups, Lie algebras, and geometric priors for deep learning models is beyond the scope of this article. Instead, the following sections concentrate on experimenting with the Lie Algebra on 3-dimension Special Orthogonal manifolds using the Geomstats Python library [ref 6].

Lie algebra on so3

As a reminder ....

A smooth manifold is a topological space that locally resembles Euclidean space and allows for smooth (infinitely differentiable) transitions between local coordinate systems. This structure allows for the use of calculus on the manifold.

The tangent space at a point on a manifold is the set of tangent vectors at that point, like a line tangent to a circle or a plane tangent to a surface.

Tangent vectors can act as directional derivatives, where you can apply specific formulas to characterize these derivatives.

Fig. 1 Manifold with tangent space and exponential/logarithm maps

A Lie algebra is a vector space g and a bilinear operator known as Lie bracket or 

Lie commutator  defined as 

$\begin{matrix}\mathfrak{g}\;\times\;\mathfrak{g}\mapsto\mathfrak{g}\\(x,y)\mapsto[x,y]\end{matrix}$

with the properties

Anticommutative:    [X,Y] = -[Y, X]
Jacobi Identity:       [[X,Y], Z] + [[Y,Z],X] + [[Z,X],Y] = 0
Examples
Let's consider the n-dimension General Linear Group on complex numbers 
GL(n, C) of n x n invertible matrices.
The Lie algebra is defined as


The Special Orthogonal Group in 3 dimensions, SO(3) is the group of all rotation matrices in 3 spatial dimensions.

The Lie bracket for the SO3 group is defined as the matrix commutator of two vectors 
X, Y on base point P.
[X, Y] = X.Y - Y.X

with the basis elements:
                  

Implementation

Setup

Geomstats is a free, open-source Python library designed for conducting machine learning on data situated on nonlinear manifolds, an area known as Geometric Learning. This library offers object-oriented, thoroughly unit-tested features for fundamental manifolds, operations, and learning algorithms, compatible with various execution environments, including NumPy, PyTorch, and TensorFlow (Overview Geomstats library).

We leverage the class LieSO3Group defined in the previous article ( Operations on SO3 Lie Groups in Python - Implementation).

import geomstats.backend as gs
from geomstats.geometry.special_orthogonal import SpecialOrthogonal


class LieSO3Group(object):
    dim = 3
    # Lie group as defined in Geomstats library
    lie_group =  SpecialOrthogonal(n=dim, point_type='vector', equip=False)

    identity = gs.eye(dim)

    def __init__(self, tgt_vector: np.array, base_point: np.array = identity) -> None:

        self.tangent_vec = gs.array(tgt_vector)


        # Exp. a left-invariant vector field from a base point
        self.group_element = LieSO3Group.lie_group.exp(self.tangent_vec, base_point)
        self.base_point = base_point

    @classmethod
    def build(cls, tgt_vector: List[float], base_point: List[float] = None) ->

        np_input = np.reshape(tgt_vector, (3, 3))


       np_point = np.reshape(base_point, (3, 3)) if base_point is not None

                         else LieSO3Group.identity

       return cls(tgt_vector=np_input, base_point=np.array(base_point))

The Lie algebra for the Special Orthogonal Group SO3 for a given tangent vector and base point is implemented through the logarithmic map in the method lie_algebra using the SpecialOrthogonal.log method in Geomstats.

def lie_algebra(self) -> np.array:
   return LieSO3Group.lie_group.log(self.group_point, self.base_point)

Fig. 2 Visualization of SO3 Lie point and Algebra

The algebra matrix is computed from a given tangent vector for a +90 degrees rotation along X-axis (3 x 3 rotation matrix) of and a given base point in the SO3 manifold.

# First SO3 rotation matrix 90 degree along x axis
so3_tangent_vec = [1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]

# Base point is SO3 rotation matrix 90 degree along y axis
base_point = [0.0, 0.0, 1.0, 0.0, 1.0, 0.0, -1.0, 0.0, 0.0]

so3_group = LieSO3Group.build(

    tgt_vector=so3_tangent_vec,

    base_point=base_point
print(so3_group)

lie_algebra = so3_group.lie_algebra()

assert np.array_equal(so3_group.tangent_vec, lie_algebra)

print(f'\nLie algebra:\n{lie_algebra}')

As expected the Lie algebra of the Lie group point is identical to the original tangent vector.

Tangent vector:

[[ 1. 0. 0.]

[ 0. 0. -1.]

[ 0. 1. 0.]]

Lie group point:

[[ 0.99 0.00 0.93]

[ 0.00 0.93 -0.99]

[-0.93 0.99 -0.00]]

Lie algebra:

[[ 1.00 0.00 0.00]

[ 0.00 0.00 -1.00]

[ 0.00 1.00 0.00]]

Projector operator

The Lie group projection operator approach is an iterative scheme usually applied to continuous-time optimal control problems on Lie groups. It is mentioned here for reference.

def projection(self) -> Self:
   projected = LieSO3Group.lie_group.projection(self.group_point)
   return LieSO3Group(projected)

We use the same tangent vector and base point on SO3 manifold to compute the projected matrix.

# First SO3 rotation matrix 90 degree along x axis
 so3_tangent_vec = [1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]

so3_group = LieSO3Group.build(tgt_vector=so3_tangent_vec, base_point=LieSO3Group.identity)

projected = so3_group.projection()
print(f'\nProjected point with identity:\n{projected.group_point}')

# Base point is SO3 rotation matrix 90 degree along y axis
base_point = [0.0, 0.0, 1.0, 0.0, 1.0, 0.0, -1.0, 0.0, 0.0]

so3_group = LieSO3Group.build(tgt_vector=so3_tangent_vec, base_point=base_point)
projected = so3_group.projection()
print(f'\nProjected point with\n{so3_group.tangent_vec}\n{projected.group_point}')

Projected point with identity:

[[ 2.00 0.00 0.00]

[ 0.00 1.63 -0.77]

[ 0.00 0.77 1.63]]

Projected point with base point

[[ 1. 0. 0.]

[ 0. 0. -1.]

[ 0. 1. 0.]]:

[[ 1.66 0.35 0.66]

[ 0.35 1.57 -0.74]

[-0.66 0.74 1.25]]

Lie Bracket

Finally, we compute the bracket for this tangent vector, self.tangent with another vector, other_tgt_vector.

def bracket(self,  other_tgt_vector: List[float]) -> np.array:
     np_vector = np.reshape(other_tgt_vector, (3, 3))
     return np.dot(self.tangent.vec, np_vector) - np.dot(np_vector, self.tangent_vec)

Let first try to compute the bracket of a SO3 point (skew matrix) with itself.


# First SO3 rotation matrix 90 degree along x axis
so3_tangent_vec = [1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]

so3_group = LieSO3Group.build(so3_tangent_vec)

 np.set_printoptions(precision=3)
 print(f'\nSO3 point\n{so3_groupA.group_element}')

 bracket = so3_groupA.bracket(so3_tangent_vec)
 print(f'\nBracket [x,x]:\n{bracket}')

Tangent vector:

[[ 1. 0. 0.]

[ 0. 0. -1.]

[ 0. 1. 0.]]

SO3 point

[[ 2.00 0.00 0.00]

[ 0.00 0.93 -0.99]

[ 0.00 0.99 0.93 ]]

Bracket [x,x]:

[[0. 0. 0.]

[0. 0. 0.]

[0. 0. 0.]]

Now Let's compute the Lie bracket of two tangent vectors, one for SO3 90 degrees rotation along X axis and the other along Y axis.


# First SO3 rotation matrix 90 degree along x axis
so3_tangent_vecA = [1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]
so3_groupA = LieSO3Group.build(so3_tangent_vecA)


# Second SO3 rotation matrix 90 degree along y axis
other_tgt_vec = [0.0, 0.0, 1.0, 0.0, 1.0, 0.0, -1.0, 0.0, 0.0]

bracket = so3_groupA.bracket(other_tgt_vec)
print(f'\nBracket:\n{bracket}')

Bracket:

[[ 0. -1. 1.]

[ 1. 0. -1.]

[ -1. 1. 0.]]

Fig 3. Visualization of two tangent vectors on SO3 manifolds

Fig. 4 Visualization of LIe bracket on SO3 manifold

References

[1] Operations on SO3 Lie groups

[2] Foundation of Geometric Learning

[3] Differentiable Manifolds for Geometric Learning

[4] Intrinsic Representation in Geometric Learning

[5] Riemann Metric and Connection

[6] Introduction to Geometric Learning in Python with Geomstats

[7] Lie algebra - Quantum Tinkering - Omar A. Ashour

----------------------------------

Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning.
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning", Packt Publishing ISBN 978-1-78712-238-3 and Geometric Learning in Python Newsletter on LinkedIn.

Thursday, September 5, 2024

Operations on SO3 Lie Groups in Python

Target audience: Advanced

Estimated reading time: 5'

Posts history

Newsletter: Geometric Learning in Python

Lie groups play a crucial role in Geometric Deep Learning by modeling symmetries such as rotation, translation, and scaling. This enables non-linear models to generalize effectively for tasks like object detection and transformations in generative models.

Table of contents

Overview

Lie manifolds

Why Lie groups

Examples of Lie groups

Special Orthogonal Group

Implementation

Inverse rotation

Composition

References

What you will learn: How to implement and evaluate key operations on 3-dimension Special Orthogonal Lie Group.

Notes:

This post is a follow up on articles related to differential geometry and geometry learning [ref 1, 2, 3 and 4]
Environments: Python 3.11, Matplotlib 3.9, Geomstats 2.8.0
Source code is available at Github.com/patnicolas/Data_Exploration/Lie
To enhance the readability of the algorithm implementations, we have omitted non-essential code elements like error checking, comments, exceptions, validation of class and method arguments, scoping qualifiers, and import statement.

Disclaimer : A thorough tutorial and explanation of Lie groups, Lie algebras, and geometric priors for deep learning models is beyond the scope of this article. Instead, the following sections concentrate on experiments involving key elements and operations on Lie groups using the Geomstats Python library [ref 5].

Overview

Let's start with some basic definitions

Lie manifolds

The tangent space at a point on a manifold is the set of tangent vectors at that point, like a line tangent to a circle or a plane tangent to a surface.

Tangent vectors can act as directional derivatives, where you can apply specific formulas to characterize these derivatives.

Fig. 1 Manifold with tangent space and exponential/logarithm maps

In differential geometry, a Lie group is a mathematical structure that combines the properties of both a group and a smooth manifold. It allows for the application of both algebraic and geometric techniques. As a group, it has an operation (like multiplication) that satisfies certain axioms (closure, associativity, identity, and invertibility) [ref 6].

A 'real' Lie group is a set G with two structures: G is a group and G is a (smooth, real) manifold. These structures agree in the following sense: multiplication (a.k.a. product or composition) and inversion are smooth maps.
A morphism of Lie groups is a smooth map which also preserves the group operation: f(gh) = f(g)f(h) and f(1) = 1.

Fig. 2 Manifold with tangent space and identity and group element

(Courtesy A. Kirillov Jr Department of Mathematics SUNY at Stony Brook)

Why Lie groups

Lie groups have numerous practical applications in various fields:

Physics: They describe symmetries in classical mechanics, quantum mechanics, and relativity.
Robotics: Lie groups model the motion of robots, particularly in the context of rotation and translation (using groups like SO(3) and SE(3)).
Control Theory: Lie groups are used in the analysis and design of control systems, especially in systems with rotational or symmetrical behavior.
Computer Vision: They help in image processing and 3D vision, especially in tasks involving rotations and transformations.
Differential Equations: Lie groups are instrumental in solving differential equations by leveraging symmetry properties.

In term of machine learning...

Geometric Deep Learning: Lie groups help capture rotational, translational, or scaling symmetries, making models more efficient and generalizable in tasks like image recognition and 3D object detection.
Generative Models: Lie groups allow for more structured latent spaces, enabling better control over transformations in generative models like GANs and VAEs.
Reinforcement Learning: They are used to model continuous action spaces, improving control over robotic systems.
Optimization: Lie groups help design efficient optimization techniques on curved spaces, like Riemannian manifolds.

Examples of Lie groups

Group of Invertible 2 x 2 matrices of real values

$GL(2,\mathbb{R})=\left\{\begin{bmatrix}a&b\\c&d\\\end{bmatrix}|\;a,b,c,d\in\mathbb{R},\;ad-bc\neq 0\right\}$

Group of Invertible 2 x 2 matrices of complex values

$GL(2,\mathbb{C})=\left\{\begin{bmatrix}a&b\\c&d\\\end{bmatrix}|\;a,b,c,d\in\mathbb{C},\;ad-bc\neq 0\right\}$

Group of Invertible 3 x 3 matrices of real values

$GL(3,\mathbb{R})=\left\{\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\\\end{bmatrix}|a,b,c,d,e,f,g,h,i\in\mathbb{R},\;det\neq 0\right\}$

Special Unitary group 2 x 2 matrices with determinant 1

$SU(2)=\left\{A\in GL(2,\mathbb{R})|\;A.A^{-1}=1,det(A)=1\right\}$

Special Unitary group 3 x 3 matrices with determinant 1

$SU(3)=\left\{A\in GL(3,\mathbb{R})\;|\;A.A^{T}=1,det(A)=1\right\}$

Special Orthogonal (3D rotation, 2x2 matrices) group

$SO(2)=\left\{R\in\mathbb{R}^{2x2}\;|\;R.R^{T}=1,det(R)=1\right\}$

Special Orthogonal (3D rotation, 3x3 matrices) group

$SO(3)=\left\{R\in\mathbb{R}^{3x3}\;|\;R.R^{T}=1,det(R)=1\right\}$

Special Euclidean group

$SE(3)=\left\{\begin{bmatrix}R&t\\0&1\\\end{bmatrix}\in\mathbb{R}^{4x4}\;|\;R\in SO(3),t\in\mathbb{R}^3\right\}$

Special Orthogonal Group

The Special Orthogonal Group in 3 dimensions, SO(3) is the group of all rotation matrices in 3 spatial dimensions.

It can be defined by 3 rotation elements for each of the axis of rotation x, y, and z.

$R_{x}(\theta)=\begin{bmatrix}1&0&0\\0&cos\theta&-sin\theta\\0&sin\theta&cos\theta\\\end{bmatrix}$

$R_{y}(\theta)=\begin{bmatrix}cos\theta&0&sin\theta\\0&1&0\\-sin\theta&0&cos\theta\\\end{bmatrix}$

$R_{z}(\theta)=\begin{bmatrix}cos\theta&-sin\theta&0\\sin\theta&cos\theta&0\\0&0&1\\\end{bmatrix}$

Implementation

The library is structured into two principal components:

geometry: This part provides an object-oriented framework for crucial concepts in differential geometry, such as exponential and logarithm maps, parallel transport, tangent vectors, geodesics, and Riemannian metrics.
learning: This section includes statistics and machine learning algorithms tailored for manifold data, building upon the scikit-learn framework.

First let's wrap the element of a point or matrix into a class, SO3Point with the following attributes:

group_element Point on the manifold
base_point on the manifold (Identity if undefined)
description which describes the rotation matrix

from dataclasses import dataclass

@dataclass
class SO3Point:
    group_element: np.array
    base_point: np.array                # Default identity matrix
    descriptor: AnyStr

Secondly, let's build a class ,LieSO3Group, that encapsulates the definition of the Special orthogonal group of dimension 3 and its related operations.

We specify two constructors:

__init__: Default constructor that create a new element in the SO3 manifold, group_element, using a tangent vector (3x3 rotation matrix) tgt_vector and identity, base_point.
build: Alternative constructor for which the tangent vector is a 9- element list and a tuple as base point.

import geomstats.backend as gs
from geomstats.geometry.special_orthogonal import SpecialOrthogonal


class LieSO3Group(object):
    dim = 3
    # Lie group as defined in Geomstats library
    lie_group =  SpecialOrthogonal(n=dim, point_type='vector', equip=False)

    identity = gs.eye(dim)     # Define identity



    def __init__(self, tgt_vector: np.array, base_point: np.array = identity) -> None

        self.tangent_vec = gs.array(tgt_vector)


        # Exp. a left-invariant vector field from a base point
        self.group_element = LieSO3Group.lie_group.exp(self.tangent_vec, base_point)
        self.base_point = base_point



    @classmethod
    def build(cls, tgt_vector: List[float], base_point: List[float] = None) -> Self:
        np_input = np.reshape(tgt_vector, (3, 3))

        np_point = np.reshape(base_point, (3, 3)) if base_point is not None

                          else LieSO3Group.identity

        return cls(tgt_vector=np_input, base_point=np_point)

We use the constructors of the LieSO3Group class to generate two points on the SO3 manifold, so3_point1 and so3_point2. These points are represented as vectors in 3-dimensional Euclidean space for visualization purposes.

The first point use the identity as base point for the tangent space of rotation of 90 degrees around X axis:

[[ 1. 0. 0.]

[ 0. 0. -1.]

[ 0. 1. 0.]]

The second SO3 point used the same tangent vector with a base

[[ 0. -1. 0.]

[ 1. 0. 0.]

[ 0. 0. 1.]]

so3_tangent_vec = [1.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]

# First rotation matrix +90 degrees around X-axis with identity as base point
so3_group = LieSO3Group.build(so3_tangent_vec)
so3_point1 = SO3Point(
     group_element=so3_group.group_element,
     base_point=LieSO3Group.identity,
     descriptor='SO3 point from tangent vector\n[1 0 0]\n[0 0 -1]\n[0 1 0]\nBase point: Identity')

# Same rotation matrix with another rotation matrix 90 degrees around

# Y-axis for base point
base_point = [0.0, -1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0]
so3_group2 = LieSO3Group.build(so3_tangent_vec, base_point)
so3_point2 = SO3Point(
     group_element=so3_group2.group_element,
     base_point=base_point,
     descriptor='Same SO3 point\nBase point:\n[0 -1 0]\n[0 0 0]\n[0 0 1]')


LieSO3Group.visualize_all([so3_point1, so3_point2])

so3_point1:

[[ 2.00 0.00 0.00] [[2 0 0]

[ 0.00 0.93 -0.99] approximation of [0 1 -1]

[ 0.00 0.99 0.93]] [0 1 1]]

so3_point2:

[[ 0.99 -0.93 0.00] [[1 -1 0]

[ 0.93 0.00 -0.99] approximation of [1 0 -1]

[ 0.00 0.99 0.93]] [0 1 1]

The code for the visualization methods are available on Github at LieSO3Group

Fig. 3 Visualization of SO3 group element at identity vs. arbitrary base point

Inverse rotation

The first operation to illustrate is the inverse rotation using Geomstats library. It is implemented by the LieSO3Group method inverse.

def inverse(self) -> Self:
    inverse_group_element = LieSO3Group.lie_group.inverse(self.group_element)
    return LieSO3Group(inverse_group_element)

For simplicity sake, we create a SO3 group element at identity and visualize its inverse on the same base point.

# Original rotation matrix +90 degrees around X-axis with identity as base point
\so3_tangent_vec = [1.0 0.0,0.0, 0.0, 0.0, -1.0, 0.0, 1.0, 0.0]

so3_group = LieSO3Group.build(so3_tangent_vec)
so3_point = SO3Point(
     group_element=so3_group.group_element,
     base_point=LieSO3Group.identity,
     descriptor='SO3 point from tangent vector\n[1 0 0]\n[0 0 -1]\n[0 1 0]\nBase point: Identity')

 # Inverse SO3 rotation matrix

so3_inv_group = so3_group.inverse()


inv_so3_point = SO3Point(
     group_element=so3_inv_group.group_element,
     base_point=LieSO3Group.identity,

     descriptor='SO3 inverse point')

As expected, the inverse of an SO3 group element represents the inverse rotation in 3-dimensional space. This would not hold true if the base point were not the identity element.

Original SO3 point

[[ 2.00 0.00 0.00]

[ 0.00 0.93 -0.99]

[ 0.00 0.99 0.93]]

SO3 Inverse point:

[[-1.00 0.00 0.00]

[ 0.00 0.00 0.93]

[ 0.00 -0.93 0.00]]

Fig. 4 Visualization of the inverse of SO3 element at identity

Composition

As previously mentioned, a smooth manifold with the structure of a Lie group ensures that the product (or composition) of two elements also belongs to the manifold. The following LieSO3Group method, product, utilizes the `compose method of Geomstats library.

def product(self, lie_so3_group: Self) -> Self:
     composed_group_point = LieSO3Group.lie_group.compose(self.group_element lie_so3_group.group_element)
     return LieSO3Group(composed_group_element)

In this initial test, we use the rotation matrix of 90 degrees around Z-axes as the second component for the composition.

# Second SO3 rotation matrix +90 degree along Z-axis
so3_tangent_vec2 = [0.0, -1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0]

so3_group2 = LieSO3Group.build(tgt_vector=so3_tangent_vec2)
so3_point2 = SO3Point(
      group_element=so3_group2.group_element,
      base_point=LieSO3Group.identity

      descriptor='SO3 point from tangent vector\n[0 -1 0]\n[1  0 0]\n[0  0 1]\nBase point: Identity')

# Composition of two rotation matrices SO3 group
so3_group_product = so3_group.product(so3_group2)

Composition of rotation matrix +90 degrees along X-axis with rotation matrix +90 degrees along Z-axis:

[[-2.11 0.62 0.96]

[ 1.52 1.74 -1.52 ]

[-0.96 -0.62 -2.11 ]]

As expected, the composition produces an anti-symmetric matrix

Fig. 5 Visualization of the composition of a SO3 group element with its inverse at identity

The second evaluation consists of composing the initial SO3 group element (90 degrees rotation along X axis) with identity matrix.

[[-1.28 0.00 0.00 ]

[-0.96 -2.11 0.62]

[-0.96 -0.62 -2.11]]

Fig. 6 Visualization of the composition of two SO3 group elements at identity

References

[1] Foundation of Geometric Learning

[2] Differentiable Manifolds for Geometric Learning

[3] Intrinsic Representation in Geometric Learning

[4] Riemann Metric and Connection

[5] Introduction to Geometric Learning in Python with Geomstats

[6] Introduction to Lie Groups and Lie Algebras - A. Kirillov, Jr - SUNY at Stony Brook

----------------------------------

Saturday, September 14, 2024