Switch to Euclidean-invariant projection onto tangent space of solution variety #34

Vectornaut · 2025-01-22T03:57:34Z

Vectornaut commented

2025-01-22 03:57:34 +00:00

This pull request addresses issues #32 and #33 by projecting nudges onto the tangent space of the solution variety using a Euclidean-invariant inner product, which I'm calling the uniform inner product.

Definition of the uniform inner product

For spheres and planes, the uniform inner product is defined on the tangent space of the hyperboloid \langle v, v \rangle = 1. For points, it's defined on the tangent space of the paraboloid \langle v, v \rangle = 0,\; \langle v, I_\infty \rangle = 1.

The tangent space of an assembly can be expressed as the direct sum of the tangent spaces of the elements. We extend the uniform inner product to assemblies by declaring the tangent spaces of different elements to be orthogonal.

For spheres and planes

If v = [x, y, z, b, c]^\top is on the hyperboloid \langle v, v \rangle = 1, the vectors

\left[ \begin{array}{c} 2b \\ \cdot \\ \cdot \\ \cdot \\ x \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ 2b \\ \cdot \\ \cdot \\ y \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ \cdot \\ 2b \\ \cdot \\ z \end{array} \right],\;\left[ \begin{array}{l} 2bx \\ 2by \\ 2bz \\ 2b^2 \\ 2bc + 1 \end{array} \right]

form a basis for the tangent space of hyperboloid at v. We declare this basis to be orthonormal with respect to the uniform inner product.

The first three vectors in the basis are unit-speed translations along the coordinate axes. The last vector moves the surface at unit speed along its normal field. For spheres, this increases the radius at unit rate. For planes, this translates the plane parallel to itself at unit speed. This description makes it clear that the uniform inner product is invariant under Euclidean motions.

For points

If v = [x, y, z, b, c]^\top is on the paraboloid \langle v, v \rangle = 0,\; \langle v, I_\infty \rangle = 1, the vectors

\left[ \begin{array}{c} 2b \\ \cdot \\ \cdot \\ \cdot \\ x \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ 2b \\ \cdot \\ \cdot \\ y \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ \cdot \\ 2b \\ \cdot \\ z \end{array} \right]

form a basis for the tangent space of paraboloid at v. We declare this basis to be orthonormal with respect to the uniform inner product.

The meanings of the basis vectors, and the argument that the uniform inner product is Euclidean-invariant, are the same as for spheres and planes. In the engine, we pad the basis with [0, 0, 0, 0, 1]^\top to keep the number of uniform coordinates consistent across element types.

Confirmation of intended behavior

Two new tests confirm that we've corrected the misbehaviors described in issues #32 and #33.

Issue	Test
#32	`proj_equivar_test`
#33	`tangent_test_kaleidocycle`

This pull request addresses issues #32 and #33 by projecting nudges onto the tangent space of the solution variety using a Euclidean-invariant inner product, which I'm calling the *uniform* inner product. ### Definition of the uniform inner product For spheres and planes, the uniform inner product is defined on the tangent space of the hyperboloid $\langle v, v \rangle = 1$. For points, it's defined on the tangent space of the paraboloid $\langle v, v \rangle = 0,\; \langle v, I_\infty \rangle = 1$. The tangent space of an assembly can be expressed as the direct sum of the tangent spaces of the elements. We extend the uniform inner product to assemblies by declaring the tangent spaces of different elements to be orthogonal. #### For spheres and planes If $v = [x, y, z, b, c]^\top$ is on the hyperboloid $\langle v, v \rangle = 1$, the vectors $$\left[ \begin{array}{c} 2b \\ \cdot \\ \cdot \\ \cdot \\ x \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ 2b \\ \cdot \\ \cdot \\ y \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ \cdot \\ 2b \\ \cdot \\ z \end{array} \right],\;\left[ \begin{array}{l} 2bx \\ 2by \\ 2bz \\ 2b^2 \\ 2bc + 1 \end{array} \right]$$ form a basis for the tangent space of hyperboloid at $v$. We declare this basis to be orthonormal with respect to the uniform inner product. The first three vectors in the basis are unit-speed translations along the coordinate axes. The last vector moves the surface at unit speed along its normal field. For spheres, this increases the radius at unit rate. For planes, this translates the plane parallel to itself at unit speed. This description makes it clear that the uniform inner product is invariant under Euclidean motions. #### For points If $v = [x, y, z, b, c]^\top$ is on the paraboloid $\langle v, v \rangle = 0,\; \langle v, I_\infty \rangle = 1$, the vectors $$\left[ \begin{array}{c} 2b \\ \cdot \\ \cdot \\ \cdot \\ x \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ 2b \\ \cdot \\ \cdot \\ y \end{array} \right],\;\left[ \begin{array}{c} \cdot \\ \cdot \\ 2b \\ \cdot \\ z \end{array} \right]$$ form a basis for the tangent space of paraboloid at $v$. We declare this basis to be orthonormal with respect to the uniform inner product. The meanings of the basis vectors, and the argument that the uniform inner product is Euclidean-invariant, are the same as for spheres and planes. In the engine, we pad the basis with $[0, 0, 0, 0, 1]^\top$ to keep the number of uniform coordinates consistent across element types. ### Confirmation of intended behavior Two new tests confirm that we've corrected the misbehaviors described in issues #32 and #33. Issue | Test ---|--- #32 | `proj_equivar_test` #33 | `tangent_test_kaleidocycle`

Vectornaut added 2 commits 2025-01-22 03:57:35 +00:00

Try projecting with the uniform inner product 03da831c9a

This projection should be invariant under Euclidean motions. For now, we
assume that all of the elements are spheres.

Implement the uniform inner product for points a05a2e1d54

Vectornaut added 2 commits 2025-01-22 03:57:50 +00:00

Write kaleidocycle nudge in uniform coordinates 01261aed91

In the previous commit, the nudge was written in standard coordinates,
so the example shouldn't have worked. However, by sheer dumb luck, the
standard and uniform coordinates match for this particular nudge. In
fact, the expression used before to get the standard coordinates may
even produce equivalent floating point values as the expression used
here to get the uniform coordinates. That would explain why the example
prints exactly the same output in this commit.

Do symmetric_kernel in projection coordinates 21cefa9f8a

Instead of finding the kernel in the standard coordinates and then
expressing it in the projection coordinates, work in the projection
coordinates from the beginning by applying a change of basis to the
input matrix.

glen commented

2025-01-22 05:58:16 +00:00

I see there were two batches of commits. Is this PR ready for review? Does this inner product seem to provide all of our nudging desiderata, or is it a tradeoff? If so, what are the pros and cons? I mean, I assume one main pro is that translating and nudging now commute, correct? Do we have an explicit unit test to examine that commutativity?

Vectornaut commented

2025-01-22 19:43:09 +00:00

I see there were two batches of commits. Is this PR ready for review?

Yes, it's ready for review—I just forgot to push the second batch of commits before posting the pull request. There are things that could be added, like:

A test based on the kaleidocycle example, as we discussed during our last meeting.
A test to verify that nudging commutes with Euclidean motions, as you suggested.

I'd be equally happy to add these to this PR (I could probably have them ready to review by Thursday) or to put them in a separate PR. Let me know which you prefer.

Does this inner product seem to provide all of our nudging desiderata, or is it a tradeoff?

I think it has all the properties we want. It fixes issues #32 and #33, which are the two formal desiderata that I recall discussing. It also feels fine when I'm playing around with the pre-made assemblies in the prototype, which is the biggest informal desideratum that I've been paying attention to.

I assume one main pro is that translating and nudging now commute, correct? Do we have an explicit unit test to examine that commutativity?

No, but we should! I can either add that to this PR or do it separately, as mentioned above.

> I see there were two batches of commits. Is this PR ready for review? Yes, it's ready for review—I just forgot to push the second batch of commits before posting the pull request. There are things that could be added, like: - A test based on the kaleidocycle example, as we discussed during our last meeting. - A test to verify that nudging commutes with Euclidean motions, as you suggested. I'd be equally happy to add these to this PR (I could probably have them ready to review by Thursday) or to put them in a separate PR. Let me know which you prefer. > Does this inner product seem to provide all of our nudging desiderata, or is it a tradeoff? I think it has all the properties we want. It fixes issues #32 and #33, which are the two formal desiderata that I recall discussing. It also feels fine when I'm playing around with the pre-made assemblies in the prototype, which is the biggest informal desideratum that I've been paying attention to. > I assume one main pro is that translating and nudging now commute, correct? Do we have an explicit unit test to examine that commutativity? No, but we should! I can either add that to this PR or do it separately, as mentioned above.

glen commented

2025-01-22 20:16:44 +00:00

Yes, since the claim is to resolve #32 and #33 when this is merged, it would be good for it to have these two explicit tests connected to those two issues included in this PR. Thanks for adding them, then I'll do the review.

Nice progress!

Yes, since the claim is to resolve #32 and #33 when this is merged, it would be good for it to have these two explicit tests connected to those two issues included in this PR. Thanks for adding them, then I'll do the review. Nice progress!

👍 1

glen commented

2025-01-22 20:19:48 +00:00

Oh, and I don't think the documentation in the PR summary is anywhere in the source/docs files. It should be. I realize we don't really have a comprehensive in-source doc system set up yet. I know we discussed it but I forget what we concluded. Please open an issue for it and include whatever notes/memory you have on the approach we were heading toward.

Vectornaut commented

2025-01-22 20:52:12 +00:00

I just checked by hand that the twisting motion printed by the kaleidocycle example is an actual first-order motion of the kaleidocycle. That means we could reasonably turn the kaleidocycle example into a test in the style of the existing tangent_test.

I just checked by hand that the twisting motion printed by the kaleidocycle example is an actual first-order motion of the kaleidocycle. That means we could reasonably turn the kaleidocycle example into a test in the style of the existing [`tangent_test`](src/commit/22870342f3370197fce91aa47ece13558a1b5dee/app-proto/src/engine.rs#L488-L541).

Vectornaut commented

2025-01-22 20:55:02 +00:00

Yes, since the claim is to resolve #32 and #33 when this is merged, it would be good for it to have these two explicit tests connected to those two issues included in this PR.

I'll switch the PR to work-in-progress until this is done, and then switch it back when it's ready to review again.

> Yes, since the claim is to resolve #32 and #33 when this is merged, it would be good for it to have these two explicit tests connected to those two issues included in this PR. I'll switch the PR to work-in-progress until this is done, and then switch it back when it's ready to review again.

Vectornaut commented

2025-01-22 20:58:09 +00:00

I realize we don't really have a comprehensive in-source doc system set up yet. I know we discussed it but I forget what we concluded.

I think we decided it would be fine for now to document the tangent projection options we've investigated on the wiki.

Please open an issue for it and include whatever notes/memory you have on the approach we were heading toward.

Should the issue be specifically for documenting the tangent projection options in the repository, or more generally for setting up an in-repository documentation system?

> I realize we don't really have a comprehensive in-source doc system set up yet. I know we discussed it but I forget what we concluded. I think we decided it would be fine for now to document the tangent projection options we've investigated on the wiki. > Please open an issue for it and include whatever notes/memory you have on the approach we were heading toward. Should the issue be specifically for documenting the tangent projection options in the repository, or more generally for setting up an in-repository documentation system?

Vectornaut changed title from ~~Switch to Euclidean-invariant projection onto tangent space of solution variety~~ to WIP: Switch to Euclidean-invariant projection onto tangent space of solution variety

2025-01-22 20:58:25 +00:00

glen commented

2025-01-22 21:43:26 +00:00

I think we decided it would be fine for now to document the tangent projection options we've investigated on the wiki.

OK, but in the long run the one we go with for "production" (if we ever get to that stage) needs to be documented in-source. (Just something to keep in mind.)

Should the issue be specifically for documenting the tangent projection options in the repository, or more generally for setting up an in-repository documentation system?

The latter more general one, thanks.

> I think we decided it would be fine for now to document the tangent projection options we've investigated on the wiki. OK, but in the long run the one we go with for "production" (if we ever get to that stage) needs to be documented in-source. (Just something to keep in mind.) > > Should the issue be specifically for documenting the tangent projection options in the repository, or more generally for setting up an in-repository documentation system? The latter more general one, thanks.

👍 1

glen commented

2025-01-22 21:43:57 +00:00

I just checked by hand that the twisting motion printed by the kaleidocycle example is an actual first-order motion of the kaleidocycle. That means we could reasonably turn the kaleidocycle example into a test in the style of the existing tangent_test.

Excellent, thank you! Sounds good.

> I just checked by hand that the twisting motion printed by the kaleidocycle example is an actual first-order motion of the kaleidocycle. That means we could reasonably turn the kaleidocycle example into a test in the style of the existing [`tangent_test`](src/commit/22870342f3370197fce91aa47ece13558a1b5dee/app-proto/src/engine.rs#L488-L541). Excellent, thank you! Sounds good.

👍 1

Vectornaut added 3 commits 2025-01-23 20:24:27 +00:00

Update the tangent test with uniform coordinates e61047cb86

The motions we feed into the projection map now need to be expressed in
uniform coordinates. I've verified by hand that `tangent_motions_unif`
and `tangent_motions_std` represent the same motions.

Confirm that projection is Euclidean-equivariant 1e3505dd01

Test the kaleidocycle's first-order motions 51df7defc5

Vectornaut commented

2025-01-23 20:24:31 +00:00

I've added tests for #32 and #33, as described in the updated PR description, so the PR is ready for review again! (I also updated the existing tangent space test to use the new coordinate system.)

Vectornaut changed title from ~~WIP: Switch to Euclidean-invariant projection onto tangent space of solution variety~~ to Switch to Euclidean-invariant projection onto tangent space of solution variety

2025-01-23 20:24:45 +00:00

Vectornaut added 1 commit 2025-01-23 23:29:04 +00:00

Move a stray declaration into a commented section 2f3fc2ed6e

Vectornaut added 1 commit 2025-01-24 20:45:24 +00:00

Stop printing the projection basis f9026c847a

glen referenced this pull request

2025-01-29 04:43:47 +00:00

Self-documentation of UI #38

glen commented

2025-01-29 04:52:20 +00:00

OK, I got a chance to look at this tonight, and I started by playing around with it. I started with the default "moons of mars" configuration, and made Deimos internally tangent to Pollux (no other constraints), and then selected Deimos and got the graphic view active (see #37). I then nudged it around with WASD (I think there are two more keys but I couldn't remember them, see #38). I observed the following bits of interesting behavior:

generally speaking, most nudges were accompanied by a change in the radius of Deimos; I had expected it to "roll around inside" Pollux more, except when nudging it perpendicular to the the tangent plane at the point of tangency, at which point it has little option but to shrink/grow.
Pollux's radius was more resistant to change, which seemed good
Once I had Deimos "cornered" in the sense of moving toward its point of tangency, it shrank in earnest, down to a very small radius at which it became roughly the size of a pixel or a few pixels on screen. (I was wondering if things might crash as its radius approached zero...) Then it entered a new mode of evolution -- it grew a bit and Pollux started to grow in radius considerably, and then as I kept nudging, Deimos's radius started to oscillate (never getting as small as its initial minimum), with Pollux steadily growing in radius.

Before I continue the review, I would be interested to hear if you can reproduce these behaviors and what if anything you think they imply about how well the current projection scheme is working. Thanks!

OK, I got a chance to look at this tonight, and I started by playing around with it. I started with the default "moons of mars" configuration, and made Deimos internally tangent to Pollux (no other constraints), and then selected Deimos and got the graphic view active (see #37). I then nudged it around with WASD (I think there are two more keys but I couldn't remember them, see #38). I observed the following bits of interesting behavior: * generally speaking, most nudges were accompanied by a change in the radius of Deimos; I had expected it to "roll around inside" Pollux more, except when nudging it perpendicular to the the tangent plane at the point of tangency, at which point it has little option but to shrink/grow. * Pollux's radius was more resistant to change, which seemed good * Once I had Deimos "cornered" in the sense of moving toward its point of tangency, it shrank in earnest, down to a very small radius at which it became roughly the size of a pixel or a few pixels on screen. (I was wondering if things might crash as its radius approached zero...) Then it entered a new mode of evolution -- it grew a bit and Pollux started to grow in radius considerably, and then as I kept nudging, Deimos's radius started to oscillate (never getting as small as its initial minimum), with Pollux steadily growing in radius. Before I continue the review, I would be interested to hear if you can reproduce these behaviors and what if anything you think they imply about how well the current projection scheme is working. Thanks!

Vectornaut commented

2025-01-29 09:45:22 +00:00

Reproduction

I've reproduced most of what you describe using the following steps:

Set the Lorentz product between Deimos and Pollux to 1
Select Deimos and then focus the display
Press and hold D or W

The one thing I couldn't reproduce was "Deimos's radius started to oscillate." With the procedures described above, Deimos's radius seemed to decrease, hit a minimum, and then slowly increase again, with every indication that it would continue to increase from then on.

Reaction

I think this behavior could plausibly result from the intended projection scheme; it doesn't raise any suspicion of an implementation bug for me.

In terms of usability, I find it annoying, but far from disqualifying. To play with a similar assembly where the current projection scheme feels more natural, try setting up three or four spheres that are all internally tangent to a containing sphere and externally tangent to each other. When you nudge one of the internal spheres, it "rolls around" in the way that you might've expected Deimos to do. That might be because it's hard for one of the internal spheres to shrink without forcing another of the internal spheres to expand.

You can make the radius dimension stiffer by shortening the last vector in the uniform basis at a sphere. For example, try replacing the matrix in the else clause in local_unif_to_std with the following:

DMatrix::from_column_slice(ELEMENT_DIM, UNIFORM_DIM, &[
             curv,           0.0,           0.0,           0.0,                  v[0],
              0.0,          curv,           0.0,           0.0,                  v[1],
              0.0,           0.0,          curv,           0.0,                  v[2],
    0.5*curv*v[0], 0.5*curv*v[1], 0.5*curv*v[2], 0.5*curv*v[3], 0.5*(curv*v[4] + 1.0)
])

This makes Deimos shrink slower and shrink less during the reproduction procedure.

Controls

I think there are two more keys but I couldn't remember them

For reference during testing, here are all the current nudge controls. The expansion and contraction nudges are new in this pull request.

Keys	Motion
A/D	`x` translation
W/S	`y` translation
shift+W/S	`z` translation
[/]	expansion and contraction

#### Reproduction I've reproduced most of what you describe using the following steps: 1. Set the Lorentz product between Deimos and Pollux to 1 2. Select Deimos and then focus the display 3. Press and hold **D** or **W** The one thing I couldn't reproduce was "Deimos's radius started to oscillate." With the procedures described above, Deimos's radius seemed to decrease, hit a minimum, and then slowly increase again, with every indication that it would continue to increase from then on. #### Reaction I think this behavior could plausibly result from the intended projection scheme; it doesn't raise any suspicion of an implementation bug for me. In terms of usability, I find it annoying, but far from disqualifying. To play with a similar assembly where the current projection scheme feels more natural, try setting up three or four spheres that are all internally tangent to a containing sphere and externally tangent to each other. When you nudge one of the internal spheres, it "rolls around" in the way that you might've expected Deimos to do. That might be because it's hard for one of the internal spheres to shrink without forcing another of the internal spheres to expand. You can make the radius dimension stiffer by shortening the last vector in the uniform basis at a sphere. For example, try replacing the matrix in the `else` clause in `local_unif_to_std` with the following: ``` DMatrix::from_column_slice(ELEMENT_DIM, UNIFORM_DIM, &[ curv, 0.0, 0.0, 0.0, v[0], 0.0, curv, 0.0, 0.0, v[1], 0.0, 0.0, curv, 0.0, v[2], 0.5*curv*v[0], 0.5*curv*v[1], 0.5*curv*v[2], 0.5*curv*v[3], 0.5*(curv*v[4] + 1.0) ]) ``` This makes Deimos shrink slower and shrink less during the reproduction procedure. #### Controls > I think there are two more keys but I couldn't remember them For reference during testing, here are all the current nudge controls. The expansion and contraction nudges are new in this pull request. Keys | Motion ---|--- **A**/**D** | $x$ translation **W**/**S** | $y$ translation **shift**+**W**/**S** | $z$ translation **[**/**]** | expansion and contraction

glen commented

2025-01-29 21:15:25 +00:00

Hmm. Correct me if I am wrong -- the fourth coordinate is proportional to 1/radius? If I do exactly your steps and hold down W, the fourth coordinate eventually does start to go up and down on various steps. This is most obvious when the coordinate is crossing the value of 10 -- the number of digits flickers back and forth for a bit, until it becomes steady. Or is the problem that the raw projected value is shown, then a re-solve value is shown, then a projected value, then a re-solve? That could quite plausibly explain the back-and-forth, and if that's the case, we should likely limit the re-displays to the re-solves (?). Thanks for your thoughts.

👍 1

Vectornaut commented

2025-01-30 10:47:07 +00:00

Reproduction

If I do exactly your steps and hold down W, the fourth coordinate eventually does start to go up and down on various steps. This is most obvious when the coordinate is crossing the value of 10 -- the number of digits flickers back and forth for a bit, until it becomes steady.

Oh, yes, I do see this. For a clearer demonstration, I can start tapping W instead of holding it while the fourth coordinate of Deimos is descending through 10 to 12 range. Sometimes, a tap makes the coordinate go slightly up instead of down.

Or is the problem that the raw projected value is shown, then a re-solve value is shown, then a projected value, then a re-solve?

The use of update_silent in deform should prevent this. Even if it's happening, it can't be the only thing going on, because it wouldn't account for the way that tapping W can sometimes make the fourth coordinate go up instead of down.

Potential explanation: error in following the nudge vector field?

After investigating, I suspect that the fourth coordinate never hits a maximum on the ideal nudging trajectory that we're trying to approximate. It could be that the jittering you noticed comes from small-scale numerical error in following the vector field, and the fourth coordinate switches from increasing to decreasing when the numerical error becomes big enough to affect the trajectory's long-term behavior.

The investigation I did was to reduce the step size of the nudge by reducing TRANSLATION_SPEED in display.rs from 0.15 to 0.05 to 0.01. This causes the turnaround in the fourth coordinate to happen later: it happens in the 20s at speed 0.15, but I've seen it happen around the 100s at speed 0.05, and it seems to happen in the 60s at speed 0.01.

Here's more evidence that we're seeing numerical error in following the vector field. Load the assembly, select Deimos, and watch the third coordinate as you tap or hold W. Since Deimos is unconstrained, the nudge you're doing should change the second coordinate while keeping the third coordinate constant. However, the third coordinate drifts slowly while also jittering a bit. When I reduce TRANSLATION_SPEED to 0.01, the drift rate of the third coordinate (per unit change in the second coordinate) is much smaller.

In the constrained case, the oscillation of the fourth coordinate reminds me of the zig-zagging one sometimes sees when doing gradient descent through a valley (like in figure 10.6.1 of the 1992 edition of Numerical Recipes in C). Since both situations involve integrating a vector field by taking discrete steps, I could believe that the behaviors are related.

Evaluation

Long-term error in following the nudge vector field might not be a big problem. Our goal is to explore the space of solutions, not to simulate trajectories accurately or reproducibly. As long as the assembly responds reasonably to nudges in the short term, the user should be able to guide it in whatever direction they want over the long term.

On the other hand, reducing jitter could make the interface feel smoother. The jitter could also be a sign of inefficiency in our nudging technique. Nudging has at least one other known numerical quirk, which I'll describe in another comment; it's present both on the main branch and in the branch to be merged. Maybe fixing the jitter would also help fix that quirk.

#### Reproduction > If I do exactly your steps and hold down W, the fourth coordinate eventually does start to go up and down on various steps. This is most obvious when the coordinate is crossing the value of 10 -- the number of digits flickers back and forth for a bit, until it becomes steady. Oh, yes, I do see this. For a clearer demonstration, I can start tapping **W** instead of holding it while the fourth coordinate of Deimos is descending through 10 to 12 range. Sometimes, a tap makes the coordinate go slightly up instead of down. > Or is the problem that the raw projected value is shown, then a re-solve value is shown, then a projected value, then a re-solve? The use of `update_silent` in `deform` should prevent this. Even if it's happening, it can't be the only thing going on, because it wouldn't account for the way that tapping **W** can sometimes make the fourth coordinate go up instead of down. #### Potential explanation: error in following the nudge vector field? After investigating, I suspect that the fourth coordinate never hits a maximum on the ideal nudging trajectory that we're trying to approximate. It could be that the jittering you noticed comes from small-scale numerical error in following the vector field, and the fourth coordinate switches from increasing to decreasing when the numerical error becomes big enough to affect the trajectory's long-term behavior. The investigation I did was to reduce the step size of the nudge by reducing `TRANSLATION_SPEED` in `display.rs` from 0.15 to 0.05 to 0.01. This causes the turnaround in the fourth coordinate to happen later: it happens in the 20s at speed 0.15, but I've seen it happen around the 100s at speed 0.05, and it seems to happen in the 60s at speed 0.01. Here's more evidence that we're seeing numerical error in following the vector field. Load the assembly, select Deimos, and watch the third coordinate as you tap or hold **W**. Since Deimos is unconstrained, the nudge you're doing should change the second coordinate while keeping the third coordinate constant. However, the third coordinate drifts slowly while also jittering a bit. When I reduce `TRANSLATION_SPEED` to 0.01, the drift rate of the third coordinate (per unit change in the second coordinate) is much smaller. In the constrained case, the oscillation of the fourth coordinate reminds me of the zig-zagging one sometimes sees when doing gradient descent through a valley (like in [figure 10.6.1](https://archive.org/details/numericalrecipes0000unse_v2g0/page/420/mode/2up) of the 1992 edition of *Numerical Recipes in C*). Since both situations involve integrating a vector field by taking discrete steps, I could believe that the behaviors are related. #### Evaluation Long-term error in following the nudge vector field might not be a big problem. Our goal is to explore the space of solutions, not to simulate trajectories accurately or reproducibly. As long as the assembly responds reasonably to nudges in the short term, the user should be able to guide it in whatever direction they want over the long term. On the other hand, reducing jitter could make the interface feel smoother. The jitter could also be a sign of inefficiency in our nudging technique. Nudging has at least one other known numerical quirk, which I'll describe in another comment; it's present both on the main branch and in the branch to be merged. Maybe fixing the jitter would also help fix that quirk.

glen commented

2025-01-30 15:43:25 +00:00

Sorry I am confused. I am not sure what you mean by short-term vs. long-term. Aren't all nudges, by their nature, very local? Repeated nudging isn't using a "stale" tangent space, is it? Is it just that the tangent space is harder to approximate in the "extreme" cases we get into with lots of nudges in one direction? Is there any way we can detect we are in that regime and dial the TRANSLATION_SPEED down automatically and dial it back up when we are in smoother territory? Just brainstorming.

Vectornaut commented

2025-01-30 21:00:24 +00:00

By "short-term error," I mean things like zig-zagging during gradient descent. On short timescales, the solutions of the differential equation that describes ideal gradient descent look very different from the solutions of the the difference equation that we use to carry out gradient descent. The solutions of the differential equation are smooth, while the solutions of the difference equation can zig-zag, with their velocities jumping back and forth at every step.

On long timescales, the solutions of the differential equation have the same qualitative behavior as the solutions of the difference equation: they both take you to a minimum. In many cases, a solution of the difference equation will roughly follow a solution of the differential equation, even though it might zig-zag while doing it. I'd describe this as having "short-term error" that doesn't lead to "long-term error." However, I can also imagine finding a solution of the difference equation that follows a solution of the differential equation for a while, but then diverges from it, perhaps by falling into a different minimum because it zig-zagged into a different basin of attraction. That's what I'm imagining when I say "long-term error."

When I talk about "long-term error" for nudging, I'm thinking of nudges as vector fields on the solution space of the constraint problem, and asking whether repeated step-by-step nudging along that vector field has the same long-term effect as following the vector field continuously. In the "Potential explanation" section, I described a case where they don't seem to have the same long-term effect. In the "Evaluation" section, however, I pointed out that we may not actually care whether they have the same effect.

By "short-term error," I mean things like zig-zagging during gradient descent. On short timescales, the solutions of the differential equation that describes ideal gradient descent look very different from the solutions of the the difference equation that we use to carry out gradient descent. The solutions of the differential equation are smooth, while the solutions of the difference equation can zig-zag, with their velocities jumping back and forth at every step. On long timescales, the solutions of the differential equation have the same qualitative behavior as the solutions of the difference equation: they both take you to a minimum. In many cases, a solution of the difference equation will roughly follow a solution of the differential equation, even though it might zig-zag while doing it. I'd describe this as having "short-term error" that doesn't lead to "long-term error." However, I can also imagine finding a solution of the difference equation that follows a solution of the differential equation for a while, but then diverges from it, perhaps by falling into a different minimum because it zig-zagged into a different basin of attraction. That's what I'm imagining when I say "long-term error." When I talk about "long-term error" for nudging, I'm thinking of nudges as vector fields on the solution space of the constraint problem, and asking whether repeated step-by-step nudging along that vector field has the same long-term effect as following the vector field continuously. In the "Potential explanation" section, I described a case where they don't seem to have the same long-term effect. In the "Evaluation" section, however, I pointed out that we may not actually care whether they have the same effect.

Vectornaut referenced this pull request

2025-01-31 08:40:11 +00:00

Debug view occasionally lists representation coordinates out of order #41

glen commented

2025-01-31 19:34:18 +00:00

Code looks ok, played with app-proto, run_examples works, and cargo test reports all pass. Merging.

glen merged commit 817a446fad into main

2025-01-31 19:34:34 +00:00

glen referenced this issue from a commit

2025-01-31 19:34:36 +00:00

Switch to Euclidean-invariant projection onto tangent space of solution variety (#34)

glen referenced this pull request