Implement `translate_diff` and `inv_diff` for all groups (#679)

olivierverdier commented 9 months ago

The main work of implementing translate_diff for all groups is done.

The main method that has to be implemented on any given group is adjoint_action!, the rest is done automatically.

[x] Replace translate_diff by adjoint_action
[x] Implement inv_diff as well
[x] Fixes for RealCircleGroup
[x] Fixes for SpecialEuclidean
[x] ~Add the extra erroring methods for SemiDirectProductGroup~ (no longer necessary)
[x] Fix the "wrapped" SpecialEuclidean cases (for instance, ConnectionManifold(SpecialEuclidean(2), CartanSchoutenMinus()))
[x] ~Implement inv_diff for Product/Power ~manifolds~ groups~ (no longer necessary)
[x] ~Add tests with a product/power ~manifold~ groups containing a SpecialEuclidean or CircleGroup, two groups which do not use the left-invariant storage of tangent vectors~ (no longer necessary)
[x] Implement adjoint_action for SpecialEuclidean
[x] Use left invariant storage for SpecialEuclidean
[x] Implement exp and log for Lie group based on exp_lie and log_lie

codecov[bot] commented 9 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 99.40%. Comparing base (676b0f5) to head (3dfde35). Report is 2 commits behind head on master.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #683 +/- ## ========================================== - Coverage 99.58% 99.40% -0.18% ========================================== Files 114 114 Lines 11244 11320 +76 ========================================== + Hits 11197 11253 +56 - Misses 47 67 +20 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

olivierverdier commented 9 months ago

The PR is mostly implemented although it doesn't pass all the tests. Two problems essentially remain, which I'm not sure how I can fix:

The RealCircleGroup stores its elements as float, so the translate_diff! which is called after allocation doesn't work. Do you know how to fix it?
For a group such as SpecialEuclidean, everything works, but stops working when it is wrapped, for instance as a MetricSpace, because then the general translate_diff methods are called (instead of the SpecialEuclidean ones). Do you know how to fix that?

kellertuer commented 9 months ago

Hi, I just saw that the format check failed. If you install JuliaFormatter.jl (in your favourite environment) and you switch with your current folder into the Manifolds.jl base folder (we have an individual setup for formatter specified in that folder) you can run

using JuliaFormatter; format(".")

to format the code according to our rules. Actually the Formatter check does nothing else than that and checks whether the run changed the code (and if it changed on CI, it complains).

kellertuer commented 9 months ago

The other test that is currently not passed is the one that checked, that every PR changes the NEWS.md file to report what was changed with that PR (so that it is in the list of changes for the next released version).

olivierverdier commented 9 months ago

I can add the missing erroring method (task 5), but I leave the remaining tasks to you (explained in more details above), since I'm not really sure how to proceed.

kellertuer commented 9 months ago

That is one reason why I asked you to start working on this, only when working on this, one notices the remaining gaps in the ideas. I personally usually try to find some time nearly every day to work on these packages here, but for the next few weeks, also called semester end time, this will not be possible from my side, due to too many other duties.

olivierverdier commented 9 months ago

I’d be happy to finish this myself if you give me pointers as to how to proceed, that’s all I’m asking.

mateuszbaran commented 9 months ago

Thank you for this work, I will try to help finish this. I need to clarify a couple of things first.

If I understand correctly, adjoint_action for the left action is differential of $Ψ_p(q) = pqp^{-1}$, while for the right action it is the differential of $Ψ_p(q) = p^{-1}qp$? Also, why did you remove inv_diff and translate_diff for product and power manifolds? That would only work if inv_diff and translate_diff are never going to be specialized for particular manifolds.

The RealCircleGroup stores its elements as float, so the translate_diff! which is called after allocation doesn't work. Do you know how to fix it?

I will fix that myself.

olivierverdier commented 9 months ago

Thank you for this work, I will try to help finish this. I need to clarify a couple of things first.

Thank you, that's much appreciated!

If I understand correctly, adjoint_action for the left action is differential of Ψp(q)=pqp−1, while for the right action it is the differential of Ψp(q)=p−1qp?

Yes, exactly. Let's fix $ψ_p(q) := p q p^{-1}$. Then the adjoint action is the derivative of $ψp$ at the identity. The right action is the left adjoint action, but at $p^{-1}$ so the derivative of $ψ{p^{-1}}$ at the identity, as you say (is is the same relation as between any other left/right actions).

Also, why did you remove inv_diff and translate_diff for product and power manifolds? That would only work if inv_diff and translate_diff are never going to be specialized for particular manifolds.

Excellent point, I made a mistake there. It would only work if all the group use the left-invariant storage, which shouldn't be assume indeed.

The RealCircleGroup stores its elements as float, so the translate_diff! which is called after allocation doesn't work. Do you know how to fix it?

I will fix that myself.

Thanks a lot!

olivierverdier commented 9 months ago

Also, why did you remove inv_diff and translate_diff for product and power manifolds? That would only work if inv_diff and translate_diff are never going to be specialized for particular manifolds.

I've tried to rectify that in 6f57baf.

However, the fact that the tests didn't catch that indicates that all the tests for product/power manifolds never involve groups with no left-invariant storage, so it could be an idea to add such tests?

olivierverdier commented 9 months ago

Unless I am mistaken, inv_diff was not implemented for product/power ~manifolds~ groups, but it should be (similarly to translate_diff) if one of the components does not use the left-invariant storage. I add that as a task.

kellertuer commented 9 months ago

just to aim for the same precision as you do – software wise we try to split for some time, to have first manifolds (e.g. power manifold and product manifold) and have the Lie part as an add-on (not yet 100% consistent, since some time all new stuff is, cf. rotations and their split from SO(n)).

So with that in mind, please implement inv_diff for the product and power group and not the manifold :)

olivierverdier commented 9 months ago

So with that in mind, please implement inv_diff for the product and power group and not the manifold :)

Yes, I meant "product/power group", as inv_diff doesn't make sense for manifolds.

For the record, before this PR, inv_diff was not available at all for product/power groups, as far as I know.

kellertuer commented 9 months ago

Sure, sometimes we (a) might not have implemented existing methods for a new manifold directly or (b) when implementing a new method we might not have taken the whole ecosystem under revision; both cases might espcially happen, when a method is still new and needs more experience or an “external contributor“ started them.

mateuszbaran commented 9 months ago

Thanks for clarification, I should have some time tomorrow to work on this PR.

mateuszbaran commented 9 months ago

I've fixed CircleGroup and RealCircleGroup. They can be sometimes a little annoying to work with because numbers can't be allocated and we need specialized non-allocating methods.

kellertuer commented 5 months ago

HI @olivierverdier, do you have plans and time to continue this? That would be great. We could help merging the current master here for example.

I think in the long run it would be really great to move the Lie group parts to a dedicated LieGroups.jl package (depedingin on ManifoldsBase and Manifolds – we could also do a LieGroupsBase.jl just depending on ManifoldsBase, but that can also be done in a later step). Such a “restart” is maybe also a good point to rethink a few of the design choices.

olivierverdier commented 5 months ago

No, I don't have plans to work on this. The main issue is that some of the groups store tangent vectors differently than others (I think it is SpecialEuclidean and RealCircleGroup), and that creates a lot of unnecessary complications.

My personal solution: I'm running my own version of Manifolds.jl which is this PR along with these complications removed and I'm happy with that solution so far.

kellertuer commented 5 months ago

That is interesting to know.

I think the reason here might be that until now we often inherited the representation from the manifold – which for some manifolds might not make sense, you are right.

I think switching to your variant might also be a good idea, with the small caveat, that this would be breaking. on the other hand, if your new representation is worth that, maybe it is worth releasing a breaking change.

kellertuer commented 5 months ago

If you do not plan to propose a breaking change here, we should maybe see how we can adapt this PR (maybe @mateuszbaran you can take a look)? And we should close this PR.

olivierverdier commented 5 months ago

The essential difference in my version is that I just removed the translate_diff! method in semidirect_product_group.jl. This allows me to use the SemiDirectProductGroup the way I wanted, with left translated vectors as implemented in this PR.

(I also had to remove the get_vector, get_vector! and get_coordinates! method for the VeeOrthogonalBasis, in that same file, for some reason, I can't remember why)

mateuszbaran commented 5 months ago

One possible approach would be to allow both representations and have a flag in Lie groups that tells which one is used. That's something I could do but there are a few other things I'd like to do first (some extensions and improvements to Manopt, maybe pushing a bit forward my work on fiber bundles and state estimation).

kellertuer commented 5 months ago

If we allow both, we could do that maybe with different tangent vector types? Until now that was the way we distinguished different tangent vector types.

mateuszbaran commented 5 months ago

That's possible but it would be quite inconvenient to wrap every tangent vector when someone only works in the left-invariant setting.

kellertuer commented 5 months ago

That one could counter a bit by making our current modelling of “what does an array represent” a bit more public (I am no sure how public that is now directly), so a user can easily (or easier) specify his/her default behaviour of what tangent vectors are usually represented in.

mateuszbaran commented 5 months ago

That one could counter a bit by making our current modelling of “what does an array represent” a bit more public (I am no sure how public that is now directly),

Currently it's up to each manifold what an array means but that is a part of the public interface (of that particular manifold).

so a user can easily (or easier) specify his/her default behaviour of what tangent vectors are usually represented in.

And that would have to be done through a flag in the manifold/Lie group as far as I can see.

kellertuer commented 5 months ago

I see. What I meant was is that currently we have lines like

ManifoldsBase.@default_manifold_fallbacks Hyperbolic HyperboloidPoint HyperboloidTVector value value

and sure these are macros that define the default (fallback) that specify what arrays are the same as. We could also have a function dispatch for that instead of a parameter maybe?

Sure in the end we have to store the information somewhere, just that maybe a dispatch is nicer than a parameter in a struct (since we would have to add that to a lot of structs).

But this is maybe also a discussion beyond this PR. The question here is, how do we resolve the bugs mentioned / noticed here? Or is that just a matter of how to represent tangent vectors?

mateuszbaran commented 5 months ago

and sure these are macros that define the default (fallback) that specify what arrays are the same as. We could also have a function dispatch for that instead of a parameter maybe?

Sure in the end we have to store the information somewhere, just that maybe a dispatch is nicer than a parameter in a struct (since we would have to add that to a lot of structs).

That dispatch is very different though, I don't see how we could re-use a trick like that for having two different representations of tangent vectors.

But this is maybe also a discussion beyond this PR. The question here is, how do we resolve the bugs mentioned / noticed here? Or is that just a matter of how to represent tangent vectors?

IIRC there were no bugs addressed here, only change of representation and implementation of a few functions that are currently not implemented in Manifolds.jl for some groups. New implementations can be added without change of representation but only in a less nice way.

kellertuer commented 5 months ago

You are right, it might not be super easy.

Ah, I did not see that in the changes so clearly. But then we can close this PR?

mateuszbaran commented 5 months ago

Closing this PR would make it easier to forget about it, and I don't want to forget. It has valuable contributions to Lie groups which I would like to incorporate into Manifolds.jl next time I have time to work on this area.

olivierverdier commented 5 months ago

Motivation for this PR

kellertuer commented 5 months ago

Hm, I think you meant to refer to #679 ? I am aware of that issue, that is why I was wondering whether this PR was still an active approach to fixing this. Thank for the info, that that is not the case any longer. But then one of the developers will take care of this, when our own schedules permit – I for example am a bit busy until end of May.

olivierverdier commented 2 months ago

This PR is finished. It assumes left-invariant storage for all the groups. Now, when creating a new group:

implementing adjoint_action allows to use translate_diff in all its flavours, as well as inv_diff.
implementing exp_lie and log_lie allows to use exp and log

And more specifically, now the adjoint action is finally defined for the special euclidean group.

kellertuer commented 2 months ago

We would have to check with the conflicts to current master (hopefully that's mainly the changelog),

But great to read that you continued this! Mateusz is probably the better person to review the last changes. Then we just also check for tests and documentation.

But if we can push to this branch, I can surely help with tests and docs as well.

kellertuer commented 2 months ago

I checked the conflicts to master (but I think I can not even push to your branch here in the GitHub web interface, where I tried that on purpose)

in groups and power groups it seems both on master and here similar lines where changed (just a few). Would be great if you could check that

In the news just add your 3 entries to the current unreleased 0.9.19 version and keep all existing content from master.

When that is resolved, the tests will run.

mateuszbaran commented 2 months ago

Thank you for continuing your work here. I will try to allocate enough time during this summer to review and hopefully merge this PR.

kellertuer commented 2 months ago

Cool! Version 8.19 was in preparation but not yet registered (nothing urgent basically) so yo can add your changes to that version as well :) the rest looks good.

Can you check the initial post? It has a list. Have you done the points that are still unchecked? Maybe if you do not plan to do them, strike them out?

mateuszbaran commented 1 month ago

I've taken another look at this PR. Here are some notes:

Adding direction to adjoint_action is completely fine and can be made non-breaking.
I don't like the idea of abandoning support for the current tangent vector representation. For all groups without left-invariant storage, I would suggest adding such option (but the default is still the current behavior to avoid breaking changes). In the future we could change the default if it appears to be the better default.
I don't think the defaults are going to work with disconnected groups outside of their identity component. It could then cause wrong results for other components which would be difficult to track. As a solution I propose adding an opt-in flag to IsGroupManifold and GroupManifold that enables these defaults, for example an additional type parameter TangentStorage which can be LeftInvariantStorage and if so, your defaults are activated.

olivierverdier commented 1 month ago

Thank you for reviewing this PR. It took me a lot of time to write and I appreciate that you take time to look into it thoroughly.

I also appreciate that you had this great idea of using left invariant storage on groups. I just pushed the idea a little further.

Adding direction to adjoint_action is completely fine and can be made non-breaking.

Great!

I don't like the idea of abandoning support for the current tangent vector representation.

This PR does not force the user to any representation at all.

It's just that if you optionally use left-invariant storage and implement adjoint action, the other methods are implemented for you automatically.

You are absolutely free to use another storage method. This means implementing all the methods accordingly (but that is a lot of work, of course). An example was the previous implementation of SE(n), which was largely incomplete. The current implementation of SE(n) is shorter and complete. What's not to like about that?

For all groups without left-invariant storage,

There aren't any, currently. All groups use the left invariant storage. Again, it means that all the standard methods are automatically defined for them, all this with less code and more functionality.

(For the record, before this PR, all the groups except for SE(n) were already using left-invariant storage)

I don't think the defaults are going to work with disconnected groups outside of their identity component.

I understand your concern, however (a) left invariant storage was already implemented for disconnected groups before this PR (b) all the tests pass, even with disconnected groups. (c) the approach is mathematically sound, and works on all Lie groups no matter what (connected or not).

But if you figure out a concrete example where this (optional) approach does not work, and that the tests would then have missed, please let me know.

Let me know if you have more questions about this PR.

kellertuer commented 1 month ago

I can take a closer look the next few days as well. Two things I noticed are

we are missing about 38 lines of code coverage, see the first comment on this PR by codecov.
currently there is a merge conflict with master. That is just the News.md, so if you could merge master into here and resolve that (keeping the master version and adding your new parts as a new version in the file).

mateuszbaran commented 1 month ago

Thank you for reviewing this PR. It took me a lot of time to write and I appreciate that you take time to look into it thoroughly.

I also appreciate your contribution :+1: . My main remaining concern is that I would like to keep the current storage of SpecialEuclidean (and CircleGroup, which is the other exception to left-invariant storage) as an option, even in its incomplete state. I can work on it myself though.

There aren't any, currently. All groups use the left invariant storage. Again, it means that all the standard methods are automatically defined for them, all this with less code and more functionality.

I understand your concern, however (a) left invariant storage was already implemented for disconnected groups before this PR (b) all the tests pass, even with disconnected groups. (c) the approach is mathematically sound, and works on all Lie groups no matter what (connected or not).

Yes, thanks for pointing it out, I've reconsidered it and it indeed looks sound.

olivierverdier commented 1 month ago

I stand corrected, CircleGroup does indeed not use left-invariant storage. (As of this PR, it is the only group which does not.) This proves the point that it is possible to opt out of the left invariant storage.

In the future, one could be given the choice of the storage for a given group. There are only a handful of methods which depend on the storage. I believe it's only translate_diff and inv_diff. (But such a change would probably warrant another separate PR.)

olivierverdier commented 1 month ago

besides that it would maybe be great to document the left-right-action thing on group.md a bit more so an only midly-Lie-group-experienced person like me has a chance to read up on the detail fixed here?

I agree. I'll try to do that.

olivierverdier commented 4 weeks ago

besides that it would maybe be great to document the left-right-action thing on group.md a bit more so an only midly-Lie-group-experienced person like me has a chance to read up on the detail fixed here?

I agree. I'll try to do that.

Done. Let me know if it is understandable.

mateuszbaran commented 3 weeks ago

I'm going to merge this PR into #732 next week and then make necessary adaptations there. Thank you again for this contribution :+1:

mateuszbaran commented 2 weeks ago

By the way, I've already merged this PR into #732 and I will polish it there.

olivierverdier commented 2 days ago

I realised I forgot to redefine inverse_translate_diff. The default (for left invariant representation) should be:

inverse_translate_diff!(G, Y, ::Any, ::Any, X, ::LeftForwardAction,) = copyto!(G, Y, X)
inverse_translate_diff!(G, Y, ::Any, ::Any, X, ::RightForwardAction,) = copyto!(G, Y, X)
inverse_translate_diff!(G, Y, p, ::Any, X, ::LeftBackwardAction,) = adjoint_action!(G, Y, p, X, RIghtAction())
inverse_translate_diff!(G, Y, p, ::Any, X, ::RightBackwardAction,) = adjoint_action!(G, Y, p, X, LeftAction())

The current definition is not wrong, and it works for all representations, but it is very inefficient, as it potentially inverts a matrix three times instead of once, or once instead of zero.

This change does not have to occur within the scope of this PR, it can be done later, maybe in a separate issue.

kellertuer commented 2 days ago

We coudls surely still ad it to the 0.10 PR that is still open?

mateuszbaran commented 2 days ago

Thanks, I will add that to the 0.10 PR.

mateuszbaran commented 2 days ago

Uh, it seems to cause lots of ambiguities, so maybe let's resolve that in a new PR since it not breaking. Anyway, here is the adapted code:

function inverse_translate_diff!(
    ::TraitList{<:IsGroupManifold{<:AbstractGroupOperation,LeftInvariantRepresentation}},
    G::AbstractDecoratorManifold,
    Y,
    ::Any,
    ::Any,
    X,
    ::LeftForwardAction,
)
    return copyto!(G, Y, X)
end
function inverse_translate_diff!(
    ::TraitList{<:IsGroupManifold{<:AbstractGroupOperation,LeftInvariantRepresentation}},
    G::AbstractDecoratorManifold,
    Y,
    ::Any,
    ::Any,
    X,
    ::RightForwardAction,
)
    return copyto!(G, Y, X)
end
function inverse_translate_diff!(
    ::TraitList{<:IsGroupManifold{<:AbstractGroupOperation,LeftInvariantRepresentation}},
    G::AbstractDecoratorManifold,
    Y,
    p,
    ::Any,
    X,
    ::LeftBackwardAction,
)
    return adjoint_action!(G, Y, p, X, RightAction())
end
function inverse_translate_diff!(
    ::TraitList{<:IsGroupManifold{<:AbstractGroupOperation,LeftInvariantRepresentation}},
    G::AbstractDecoratorManifold,
    Y,
    p,
    ::Any,
    X,
    ::RightBackwardAction,
)
    return adjoint_action!(G, Y, p, X, LeftAction())
end

JuliaManifolds / Manifolds.jl

Implement `translate_diff` and `inv_diff` for all groups (#679) #683

Codecov Report