Why are Lie algebra / group useful in practice?

[fghoussen]

Why are Lie algebra / group useful in practice?

I read about Lie algebra / group: basically, I understand that:

• the algebra looks like a "natural" vectorial space where "natural" operations are possible
• there are maps to go from/to the algebra to the group
• the group is a (possibly curved) manifold where operations are not "natural" and "difficult"

OK, that for the theory: using Lie theory allows to get exact result (up to numerical precision)... But in practice, in robotics daily life, why would I care? In all I read, there is never an example that could explain why (i.e. compare with the naive approach and see the benefits).

Could someone give an pragmatic concrete daily-life example? In robotics for example, what example can I use to conclude "if I would have done this naively, I would have ended-up with this big error, but, as I use Lie algebra / group my final error is epsilon machine"?

Is multiplying rotation matrices such an example? Not sure as AFAIU, if I multiply for instance a rotation matrix of 45 degrees over the x-axis with itself I get exactly a rotation matrix of 90 degrees over the x-axis, right? There is no approximation or error here: the Lie theory will not help to get better result. Iterative Closest Point has rotation matrix backed deep in the algorithm, it goes the naive way but doesn't use Lie theory AFAIK and everything seems fine. I am not sure to understand why and when using the Lie theory make a difference.

My question is: what kind of practical example (in robotics for instance) can show the benefit of using Lie theory and illustrate that if I go the naive-way I get an incorrect result (that would have been correct using Lie theory)?

In other words, in which kind of problems must I use Lie theory to avoid errors?

[stefangachter]

Franck, it is less about accuracy and more about consistency and convergence. With consistency, I mean how well the actual error matches with the estimated uncertainty. Thus, you can trust a consistent estimate that the provided covariance reflects well the belief about the error. Guaranteed convergence is important for large initial deviations or if strong noise is present. With the Lie algebra / group formulation, one can show that consistency and global convergence are guaranteed under certain assumptions. This is the power of this approach. Nevertheless, it can have an impact on accuracy as well.

[fghoussen]

Stefan, thanks for this answer: it does really help! I understand that "when a problem is deterministic (no covariance / probability involved) the naive/standard way to deal with S[OE]3 is the way to go (and will produce the same results than using Lie theory), and, when a problem is stochastic (with covariance / probability involved) the Lie theory is to be prefered as it will help convergence": is this correct?

If I take 4 examples:

• composing several rotations (R = R1 o R2 o ... o Rn): deterministic problem, probability are not involved, Lie theory will not help.
• minimizing a cost function like "cos(theta)² + cos(theta)*sin(theta)" (i.e. a function I've just made up with cos/sin and angle as variable): deterministic problem, probability are not involved, Lie theory will not help.
• Iterative Closest Point (in the general case, with unknown associations and non-linear functions, this is solved as a least squares problem with no probability / uncertainty associated to the "x" you want to solve for: Gradient Descent updates "x" but no covariance is associated to "x"): deterministic problem, probability are not involved, Lie theory will not help.
• Kalman Filter and the likes: here probability is key, and, Lie theory does help convergence which is a key thing here.

@stefangachter: for each of these examples, am I correct?

[joansola]

Hi Franck. Thanks for this question.

Good answers to your question may vary a lot. They can go beyond what Stefan explains above.

For example, there is the conceptual benefits of having a theory that abstracts the mechanisms of many different mathematical objects. So you can use the same concepts in unit quaternions, rotaiton matrices in 2 and 3 dims, unit complex numbers, transforms in 2 and 3 dims (the SE(n) groups), the similarity groups, the Galilean group (useful for IMU systems), and many more. Without the unifying framework of Lie theory, you can come up with perfectly accurate solutions for all of these systems, but you have to engineer them explicitly each time. Lie theory allows you to understand all these things at once, then work confidently on each one of them, using the same principles, with the assurance that you are doing things properly.

The idea of conceptualizing and abstracting is interesting per se, and has practical outcome when it comes to implementing software. In manif, we have abstracted all the common concepts, and you can find generic code for interpolating, that you can use in SO2, SO3, SE2 and SE3.

At the end, it is a bit like saying: I can add number 7 eight times to obtain 56. Why do I need multiplication if just summing gives the same exacdt result? Well, multiplication is a tool that allows you do do much more than just add number 7 eight times. Lie theory is the same thing when compared to 3x3 rotation matrices. It allows you to apply the concepts to other domains, and still be sure that you are doing it fine.

Another practical advantage is this. Imagine you are in SE3. You have a pose (R,T) that you want to update with a displacement, obtained by integrating angular and linear velocities (w,v) over a period dt. Many times, we compose translation and rotation doing this:

dT = v*dt
dR = exp(w*dt)
T <- T + R * dT
R <- R * dR

this is fine but it is not accurate. In fact, you are rotating at the same time as translating, proceeding in an arc-shaped trajectory, and therefore the equation T <- T + R*v*dt is wrong, since it proceeds in a straight line (a straight line in the direction of R*v).

What you want is to make sure that at each moment you have accumulated the exact rotation so that your velocity is pointed at all times to the right direction, making an arc. This you achieve with the exponential map of SE(3), like so:

dT = v*dt
dtheta = w*dt
V = V(dtheta) // see micro-lie paper for the expression of V(theta)
T <- T + R * V(dtheta) * dT
R <- R * exp(dtheta)

Now you can see that the update expression for T is different than before, and that the exponential map of SE(3) gives you a more accurate solution than just translating and rotating in the R3 and SO(3) groups separately. The matrix V(dtheta) captures the fact that the trajectory is an arc and not a straight line.

The compact form of writing this update using the exponential of SE(3), which is absolutely equivalent to the above, is:

tau = (v,w)*dt.  \in R^6 // integrate velocity twist in the Lie algebra of SE3
M <- M * exp(tau)

where M = [R T ; 0 1]. Now compare this to what you would do in SO(3):

theta = w*dt.   // integrate angular velocity in the Lie algebra of SO3
R <- R * exp(theta)

or what you would do using unit quaternions

theta = w*dt.   // integrate angular velocity in the Lie algebra of S3
q <- q*exp(theta)

or even what you do in pure translations in R^3

dx = v*dt.  // integrate linear velocity in the Lie algebra of R3 (which is R3 itself)
x <- x * exp(dx) = x + dx

since in R3 you have the trivial exponential map exp(dx) = dx, and the composition * is the sum.

I hope this all makes sense to you.

[fghoussen]

@joansola: thanks for your answer! Indeed, it does make sense.

I feel like I was not "that wrong" in the conclusions I drawn from the 4 examples above... Even if the topic sounds deeper, and, one finally use the Lie approach for other reasons (abstraction for example)

The idea of conceptualizing and abstracting is interesting per se

Yes, sure, I agree with this!

"when a problem is deterministic (no covariance / probability involved) the naive/standard way to deal with S[OE]3 is the way to go (and will produce the same results than using Lie theory), and, when a problem is stochastic (with covariance / probability involved) the Lie theory is to be prefered as it will help convergence"

I feel like the above should be completed with "Also, if you need to compute jacobians of related variables (like poses (T, R) are in SE3), then, the Lie theory is the prefered way to go". Afterwards, I realize that if you consider a jacobian, like a kind of 1st order/moment thing that could (?) be associated to some kind of probability to min/max a cost function, then you may think of this case as a particular sub-case of the formulation above?... Not sure but sounds "possibly right" or "not that wrong" to me afterwards. Anyway...

Putting aside conceptualisation / abstraction (focusing only on what is needed or not - avoiding extra dependency when not needed), I guess that when you need to compute jacobians of rotations only (in SO3) the naive/standard way is enough (not sure here neither): is this correct?

dR = exp(w*dt) // Only in SO3
R <- R * dR // Is this OK? I would say yes

The code
test_rotation_with_lie_theory.cpp.txt
uses Eigen to compose rotations: the standard way gives correct result accurately (unless I am not sure if this can be compared to the pseudo-code above).

>> ./test_rotation_with_lie_theory 
rotation: 
 0.804738 -0.310617  0.505879
 0.505879  0.804738 -0.310617
-0.310617  0.505879  0.804738
rotation: 
 0.333333 -0.244017  0.910684
 0.910684  0.333333 -0.244017
-0.244017  0.910684  0.333333
rotation: 
 0.333333 -0.244017  0.910684
 0.910684  0.333333 -0.244017
-0.244017  0.910684  0.333333

In all case, thanks for this discussion which is really helpful!

[fghoussen]

Imagine you are in SE3. You have a pose (R,T) that you want to update with a displacement, obtained by integrating angular and linear velocities (w,v) over a period dt.... In fact, you are rotating at the same time as translating, proceeding in an arc-shaped trajectory, and therefore the equation T <- T + Rvdt is wrong, since it proceeds in a straight line (a straight line in the direction of R*v). What you want is to make sure that at each moment you have accumulated the exact rotation so that your velocity is pointed at all times to the right direction, making an arc.

Is there an example that illustrates/runs this case? I guess it would be a simpler example to start with.

[joansola]

See here

http://www.iri.upc.edu/people/jsola/JoanSola/objectes/toolbox/courseSLAM.pdf

pag 14, Fig. 2.2, and text. There is no Lie theory, but you can see the different approximations for a curved path.

There is also a discussion here on manif about this topic, see #292 and perhaps also #299.

[fghoussen]

Thanks!

[joansola]

A few quick facts for you to ground some concepts:

Rotation matrices are what SO(3) is about, with and without Lie theory.

In the context of Lie theory, you apply composition to two matrices. In SO(3), composition is achieved through matrix product. Therefore, composing rotations "using Lie theory" is exactly the same as multiplying rotation matrices. Therefore, the result is the same exactly.

In Eigen, rotation composition is done with matrix multiplication. So there is nothing to add to what it has been said in the paragraph above.

Internally, however, Eigen uses quaternions sometimes. Composing quaternions is done through quaternion product, again irrespectively of if you want to call it "Lie theory" or not. Also, quaternions can be exactly converted to rotation matrices, and the product of quaternions becoms exactly equivalent to the product of rotation matrices. Again, it does not matter what you do, you always obtain the same exact result.

Now on to covariances and Jacobians.

In 3x3 rot matrtices, you have 9 parameters. If you go the naive way, the covariance of such matrix is a 9x9 matrix. This is an awful approach.

People used to use quaternions, which have 4 parameters. Then, the naive covariance of a quaternion is a 4x4 matrix. This is better than 9x9, but still wrong, since one dimension is blocked. What you want is a 3x3 covariance matrix.

Lie theory gives you the framework to properly define 3x3 covariance matrices for rotations. It does so by defining the uncertainty in the tangent space, which is 3-dimensional. To do so, all Jacobians in Lie theory transform from tangent space to tangent space, and they have minimal dimension.

Out of Lie theory, all these issues are really messy, and most of the times only approximately accurate.

[fghoussen]

Thanks for theses precisions!