Ball/Metric Tree using NearestNeighbors.jl / Manifolds.jl / Distances.jl / CoordinateTransformations.jl

[dehann]

TAC:

On-manifold KDE approx products, e.g. pqr = p * q * r, where p,q,r are probability densities, and on say SE(3) manifold, or similar.

Note: probability density on manifold here is akin to (but "better than") heatmap on torus, or sphere, etc.

Tasks:

• Ball tree: on-manifold, balanced for any number of particles, (future unbalanced), elliptical-covariance (i.e. Gaussian) kernels
• Brute force Evaluate density (future upgrade to known fast techniques),
  • Dual tree: Stack Overflow AND GrayMoorePaper AND BSD C++ implementation AND Gray, A.G. and Moore, A.W., 2003, August. Very fast multivariate kernel density estimation via computational geometry. In Joint Stat. Meeting (Vol. 4).
    • Monte Carlo Dual Tree
  • "FFT-Based Fast Computation of Multivariate Kernel Density Estimators with Unconstrained Bandwidth Matrices"
  • Fast kernels
• LOOLV bandwidth selection/optimization (minimize differential entropy)
  • Task 1: entropy evaluation
  • Task 2: LOOLV optimization
• Gibbs sampling for product approx
  • see here: Sequential Gibbs on manellic #280 (comment)
• Pyramid / waterfall Gibbs upgrade
  • Manellic products are now multiscale (also for unbalanced trees) #282
• is parallel transport needed for kernel products with covariances in different tangent spaces?
• Ensure partials are working
• Ensure all features also work for ProductManifolds and PowerManifolds.

---

Related

• https://arxiv.org/pdf/1805.08342.pdf
• Ichimura, T. and Fukuda, D., 2010. A fast algorithm for computing least-squares cross-validations for nonparametric conditional kernel density functions. Computational statistics & data analysis, 54(12), pp.3404-3410.
• Fast Kernel Density Estimation with Density Matrices and Random Fourier Features
• Ichimura, T. and Fukuda, D., 2010. A fast algorithm for computing least-squares cross-validations for nonparametric conditional kernel density functions. Computational statistics & data analysis, 54(12), pp.3404-3410.
• Klaas, Mike, Mark Briers, Nando de Freitas, Arnaud Doucet, Simon Maskell, and Dustin Lang. 2006. “Fast Particle Smoothing: If I Had a Million Particles.” In Proceedings of the 23rd International Conference on Machine Learning, 481–88. ICML ’06. New York, NY, USA: ACM. http://doi.acm.org/10.1145/1143844.1143905.

---

Initial Comment

Simultaneously see #32 and JuliaRobotics/RoME.jl#244

See:

• https://github.com/JuliaStats/Distances.jl/blob/068f820f960a55fa81d2dc361042c513e38eae80/src/metrics.jl#L592
• https://github.com/KristofferC/NearestNeighbors.jl/blob/master/src/ball_tree.jl
• https://github.com/KristofferC/NearestNeighbors.jl/blob/master/examples/balltree_illustration.ipynb

Need to expand on <: Distances.Metric such that Manifolds.jl can be used to define construction of a BallTree object:

• https://github.com/JuliaStats/Distances.jl/blob/068f820f960a55fa81d2dc361042c513e38eae80/src/metrics.jl#L194

[mateuszbaran]

We've integrated Manifolds.jl and Distances.jl here: https://github.com/JuliaManifolds/ManifoldML.jl/blob/master/src/distances.jl .

[dehann]

Hi @mateuszbaran , oh great thanks -- would you recommend i go down this path (JuliaManifolds/Manifolds.jl#268 (comment))? Basically I'm trying to plan how to do a separate and new rewrite of the KernelDensityEstimate.jl package by first building/exporting a new MetricTree that properly uses <:Manifold. There are many moving parts and just trying to scope out the major pain points first. Thanks for the pointer, will look at ManifoldML.jl more closely (did not see that before).

---

Ref
https://github.com/KristofferC/NearestNeighbors.jl/blob/master/examples/balltree_illustration.ipynb

EDIT, see more comments at Manifolds.jl 268

[dehann]

xref JuliaRobotics/IncrementalInference.jl#1010

[mateuszbaran]

Hi! I see there is quite a lot you're trying to do. Here you can see how to do nearest neighbor search using distances on manifolds: https://juliamanifolds.github.io/ManifoldML.jl/dev/knn.html . The example is for kNN classifier but it can be adapted to NN descent for any purpose.

would you recommend i go down this path (JuliaManifolds/Manifolds.jl#268 (comment))?

Special Euclidean group is one of the trickier manifolds to work with. First of all it's a product manifold, and we have two representations for points and tangent vectors on product manifolds, and then Seth wrote yet another representation. As he responded in that issue, SE doesn't currently support manifold operations on the matrix representation but it could be added. I quite like his idea to make an AffineArray type for that. I think we could help you with that.

ProductRepr is just a wrapper for a tuple that holds projections onto component manifolds of a product manifold. For SE, it just holds a tuple with two elements: translation and rotation matrix. All manifold-related operations are automatically supported. The thing that is problematic with it is that it either can be mutated or stored in-line in arrays (depending on wrapped types) but not both. ProductArray is an attempt at solving this problem but it's not easy to use so I generally recommend avoiding it unless you're sure you need it.

By the way, what representation of points on SE(2) are you currently using?

building/exporting a new MetricTree that properly uses <:Manifold.

What do you mean by MetricTree here? Standard NearestNeighbors.jl trees can handle points on manifolds. I could make an example of NN descent on points from SE.

[dehann]

Thanks, I also worked through your other reply (JuliaManifolds/Manifolds.jl#268 (comment))

I see there is quite a lot you're trying to do

Yes there are a lot of things but it has been coming for a long time. I have been collecting various aspects within the Caesar.jl project and probably time to address the consolidation/standardization with a common JuliaLang definition of Manifolds.

The example is for kNN classifier but it can be adapted to NN descent for any purpose.

Oh great thanks, I missed that.

I quite like his idea to make an AffineArray type for that. I think we could help you with that.

This sounds like the way to go then. I'm probably a little behind on understanding precisely how you intend to expand AffineArray regarding product manifolds, but I'll get there.

ProductArray is an attempt at solving this problem but it's not easy to use so I generally recommend avoiding it unless you're sure you need it.

Okay, will keep this in mind thanks.

By the way, what representation of points on SE(2) are you currently using?

Currently my own hacky bare-minimum definitions as part of a wait-and-see on how to best consolidate Manifolds for Julia in general. Thanks to work from @Affie we at least got our definitions down to a single clean @defVariable macro, which will make the switch out to Manifolds.jl easier once we find our way:

• https://github.com/JuliaRobotics/DistributedFactorGraphs.jl/blob/980938fc88cba0aa9187eba90edc93b8bfa85002/src/services/DFGVariable.jl#L67-L93

Way back in the beginning (like in Julia v0.1 days) I wrote a quick and hacky TransformUtils.jl and have been trying to get away from that ever since (but has been good enough until now). This was long before StaticArrays.jl even existed. CoordinateTransforms.jl (CT.jl) came online a little later and the plan became to rebrand and gut TransformUtils.jl to better use CT.jl, and then reintroduce some of the user friendly "one button" features to automatically switch between manifolds as necessary -- e.g. AngleAxis/SO3/Quaternion/Euler should not require the user to forcefully convert up and down, but instead use multiple dispatch and promotion with common sense rules like SO3 * Quat ==> SO3 (assuming convention aV = aRb*bV).

That was all fine until the plotting libraries also started making Point definitions of their own too -- this lead to name conflicts in Main context when loading many libraries. The effort there seems to be other packages like GeometryBasics.jl that replaced GeometryTypes.jl, etc. Basically everybody seems to be working towards better abstraction beyond Euclidean. As you mentioned Distances.jl too. JuliaManifolds just feels like the right venue, hence all these long comments as part of the process to find the way forward for a sensible abstraction across the Julia ecosystem in general.

What do you mean by MetricTree here?

Building kNN if a metric exists, to generalize "ball tree" beyond Euclidean distance:

• https://core.ac.uk/download/pdf/82189909.pdf
• http://ilpubs.stanford.edu:8090/113/1/1995-44.pdf
• there are quite a few more.

I could make an example of NN descent on points from SE.
I think we could help you with that.

This is exactly what im trying to do as proof of concept -- i.e. trying to find a roadmap of how to do all this consolidation work. If you could help point in the right direction for how to build a tree over SE2 that would be great. Please note that I already did that once, but this was using the hacky manifold definitions (and also I want a fresh implementation under permissive open source license, not something restricted to LGPL as the prior implementation). Won't link it here so that we can keep the copyright as separate as possible :-P.

Perhaps I can ask again from JuliaManifolds/Manifolds.jl#268 (comment), this is what I was planning on doing for a "distance" (either logmap or Frobenius norm), but logmap seems more general for Riemannian:

distance(::SE2, T2, T1) = norm(vee(logmap(inverse(T2) * T1))) 
 # or whatever is most efficient

PS, once there is a route to building kNN for SE2 or SE3 using multiple dispatch around some sort of "metric" or "distance", ("MetricTree" as a grabbag term), I'd like to make my own manifold that is much much more intricate (integrated inertial navigation solution), you might recall an earlier comment

• Curious about making Plots.jl a conditional dependency? JuliaManifolds/Manopt.jl#24 (comment) with interest
  • Looking for a simple, pure inertial motion estimation RoME.jl#334

---

EDIT: Actually, let me add a shameless plug too: https://marinerobotics.mit.edu/sites/default/files/fourie_iros19_manifolds.pdf

Here is the sandbox where I'm trying to find the way forward:
https://github.com/JuliaRobotics/ApproxManifoldProducts.jl/blob/master/examples/dev_BallTreeDensity.jl

[mateuszbaran]

I've made a small example how you can make a NN descent using Manifolds:

using StaticArrays, Manifolds, NearestNeighbors, Distances

M = SpecialEuclidean(2)
N = 100
# convert point to coordinates
function coords(p)
    return SA[p.parts[1][1], p.parts[1][2], atan(p.parts[2][2,1],p.parts[2][1,1])] # fixed from acos(p.parts[2][1,1]
end
# reverse of `coords`
function uncoords(p)
    α = p[3]
    return ProductRepr((SA[p[1], p[2]]), SA[cos(α) -sin(α); sin(α) cos(α)])
end
# some random points to make a tree from
pts = [uncoords(@SVector randn(3)) for _ in 1:N]

# The variant in ManifoldML doesn't support `ProductRepr` currently.
struct SE2Distance{TM<:Manifold} <: Distances.Metric
    manifold::TM
end
function (dist::SE2Distance)(a, b)
    return distance(dist.manifold, uncoords(a), uncoords(b))
end

dist = SE2Distance(M)
# making a tree
point_matrix = reduce(hcat, map(a -> coords(a), pts))
balltree = BallTree(point_matrix, dist)
# finding nearest neighbors
k = 3
idxs, dists = knn(balltree, coords(pts[2]), k)

It could definitely be made a bit nicer, for example coords and uncoords is needed just because ProductRepr is used (I could use the array thing but it's more complicated). I've also made a separate Distances.Metric because I haven't added yet support for ProductRepr to the ManifoldML version.

Currently we have a nice way of representing coordinates of tangent vectors (get_coordinates and get_vector) but so far we haven't needed it that much for points. This is something we need to improve.

Way back in the beginning (like in Julia v0.1 days) I wrote a quick and hacky TransformUtils.jl and have been trying to get away from that ever since (but has been good enough until now). This was long before StaticArrays.jl even existed. CoordinateTransforms.jl (CT.jl) came online a little later and the plan became to rebrand and gut TransformUtils.jl to better use CT.jl, and then reintroduce some of the user friendly "one button" features to automatically switch between manifolds as necessary -- e.g. AngleAxis/SO3/Quaternion/Euler should not require the user to forcefully convert up and down, but instead use multiple dispatch and promotion with common sense rules like SO3 * Quat ==> SO3 (assuming convention aV = aRb*bV).

That was all fine until the plotting libraries also started making Point definitions of their own too -- this lead to name conflicts in Main context when loading many libraries. The effort there seems to be other packages like GeometryBasics.jl that replaced GeometryTypes.jl, etc. Basically everybody seems to be working towards better abstraction beyond Euclidean. As you mentioned Distances.jl too. JuliaManifolds just feels like the right venue, hence all these long comments as part of the process to find the way forward for a sensible abstraction across the Julia ecosystem in general.

That's good to know, I'll have to take a closer look at CT.jl. I think we just need to add dispatches to Manifolds.jl that accept additional representations of points on SE(N), SO(N), etc.

Perhaps I can ask again from JuliaManifolds/Manifolds.jl#268 (comment), this is what I was planning on doing for a "distance" (either logmap or Frobenius norm), but logmap seems more general for Riemannian:

distance(::SE2, T2, T1) = norm(vee(logmap(inverse(T2) * T1))) 
 # or whatever is most efficient

We have a slightly different default definition of distance: https://github.com/JuliaManifolds/ManifoldsBase.jl/blob/aeded401bdd7b00029051a92e7fb5c4771fb998a/src/ManifoldsBase.jl#L292 . Anyway, most manifolds have better implementations because log can be very slow for some manifolds. For SE(2) our distance currently takes about 30ns to compute but it could be improved.

PS, once there is a route to building kNN for SE2 or SE3 using multiple dispatch around some sort of "metric" or "distance", ("MetricTree" as a grabbag term), I'd like to make my own manifold that is much much more intricate (integrated inertial navigation solution), you might recall an earlier comment

• JuliaManifolds/Manopt.jl#24 (comment) with interest

  • JuliaRobotics/RoME.jl#334

Nice, that would be really cool 🙂 .

[mateuszbaran]

Here is the sandbox where I'm trying to find the way forward:
https://github.com/JuliaRobotics/ApproxManifoldProducts.jl/blob/master/examples/dev_BallTreeDensity.jl

I've taken a look there. @sethaxen, what do you think about integrating CoordinateTransformations.jl into Manifolds.jl for things like SE(N) or SO(N) or groups of translations? What we offer now is definitely not great.

[dehann]

I've made a small example how you can make a NN descent using Manifolds

@mateuszbaran , thank you very much! I'm going to work through this now, this is I was missing before. Will look to build more in-place etc. and will call again when I have something to show.

(From @sethaxen at JuliaManifolds/Manifolds.jl#268 (comment)) So there are a few ways forward. One is to use ProductArray or ProductRepr. Another is to implement a custom AffineArray type, similar to Rotations.jl's custom array types (and this maybe would belong in [Manifolds.jl] package). Third, you could use a custom type like CoordinateTransformations.AffineMap (though I don't see the benefit of this, as it's basically the same idea as ProductArray or ProductRepr). For the latter two options, you probably only need a few overloads in Manifolds to make it work.

Good to see the ProductRepr approach, thanks!

It could definitely be made a bit nicer, for example coords and uncoords is needed just because ProductRepr is used (I could use the array thing but it's more complicated). I've also made a separate Distances.Metric because I haven't added yet support for ProductRepr to the ManifoldML version.

Currently we have a nice way of representing coordinates of tangent vectors (get_coordinates and get_vector) but so far we haven't needed it that much for points. This is something we need to improve.

Its looking like we are now going to do a major re-write of some core features between ApproxManifoldProducts.jl and IncrementalInference.jl to fix a whole slew of stuff identified in the last months including #42, JuliaRobotics/IncrementalInference.jl#1010, JuliaRobotics/IncrementalInference.jl#1025, JuliaRobotics/RoME.jl#244, and a few others. Thanks for the pointer on distances, it has an immediate impact for us here!

For SE(2) our distance currently takes about 30ns to compute but it could be improved.

That's great! Will look at that more. Here on the Caesar.jl/RoME.jl side we are working to finish the 2020 abstraction / numerical quality round probably by early 2021, after which we plan to switch into a short performance round through late Spring '21.

Just in case you hadn't seen yet, SLEEFPirates.jl do high speed hardware tricks with AVX. According to quick tests I did using @btime something like scalar log or exp drop from 5ns to 0.02ns, which is a little mind-blowing. I had a some trouble recently trying to get that improvement for a large workload, but probably something I did wrong and not the priority just yet.

sethaxen what do you think about integrating CoordinateTransformations.jl

(From @sethaxen at JuliaManifolds/Manifolds.jl#268 (comment)) [Third option], you could use a custom type like CoordinateTransformations.AffineMap (though I don't see the benefit of this, as it's basically the same idea as ProductArray or ProductRepr). For the latter two options, you probably only need a few overloads in Manifolds to make it work.

So it's an issue of consolidation between Manifolds.jl and CoordinateTransformations.jl regarding some of the manifolds? CT.jl is all about manipulating 3D points in XYZ space at maximum speed. The bad option is for each user to mix abstraction from Manifolds.jl with performance from CT.jl themselves, but we don't know until we try. So likely that the work here in AMP.jl and RoME.jl might be bit of guinea pig for how that will play out. Happy to move code upstream however is sensible. I'll link future comments on that to this issue for record keeping.

I'd add to this that several of the JuliaRobotics packages (beyond the ones I'm directly involved with) and other packages in Julia ecosystem use CT.jl. CT.jl went hard early on performance by using StaticArrays.jl, so think it will be difficult to squeeze more speed out with a different implementation. I would say that CT.jl has good traction in the community, so sharing the load with them is advisable. I'd hope updating both Manifolds.jl and CT.jl will be doable to get best of both on abstraction and performance.

[dehann]

Looking at CT.jl dependencies, it seems like an isolated package:

• https://github.com/JuliaGeometry/CoordinateTransformations.jl/blob/master/Project.toml

At worst we can just lift efficient code from CT.jl into a Manifolds.jl related packages, or at best find the right compatibility between JuliaManifolds and JuliaGeometry.

[dehann]

Oh sorry one more question @mateuszbaran, I'm just checking that the door is still open for using either Vector of elements or Matrix to build a NN tree -- i.e. it doesn't have to be a matrix of points concatenated together?

From code above:

balltree = BallTree(point_matrix, dist)

What I mean is that there still is a route to instead do something like:

vector_elem = coords.(pts)
balltree = BallTree(vector_elem, dist)

---

EDIT, looks like it is working

[dehann]

Tangentially related, just keeping link in this thread (apologies for noise):
http://scikit-learn.sourceforge.net/stable/auto_examples/manifold/plot_manifold_sphere.html

[mateuszbaran]

Just in case you hadn't seen yet, SLEEFPirates.jl do high speed hardware tricks with AVX. According to quick tests I did using @btime something like scalar log or exp drop from 5ns to 0.02ns, which is a little mind-blowing. I had a some trouble recently trying to get that improvement for a large workload, but probably something I did wrong and not the priority just yet.

Just a small tip, when you see @btime reporting times below about 1ns they are most likely incorrect. Compiler can optimize too much of the benchmarking code and working around this (by using setup or references) can add a few nanoseconds. Anyway, at that level of execution time performance is heavily dependent on the surrounding code.

I know about SLEEFPirates but so far I've been struggling with more high-level performance bottlenecks so I haven't used it yet. There is quite a lot happening in Julia about such optimizations, for example with LoopVectorization and KernelAbstractions so I think it will only get easier to write fast code.

Its looking like we are now going to do a major re-write of some core features between ApproxManifoldProducts.jl and IncrementalInference.jl to fix a whole slew of stuff identified in the last months including #42, JuliaRobotics/IncrementalInference.jl#1010, JuliaRobotics/IncrementalInference.jl#1025, JuliaRobotics/RoME.jl#244, and a few others. Thanks for the pointer on distances, it has an immediate impact for us here!

Cool! I don't quite understand what these issues are about but you can ask me about Manifolds.jl if it can help solve them 🙂 .

So it's an issue of consolidation between Manifolds.jl and CoordinateTransformations.jl regarding some of the manifolds? CT.jl is all about manipulating 3D points in XYZ space at maximum speed. The bad option is for each user to mix abstraction from Manifolds.jl with performance from CT.jl themselves, but we don't know until we try. So likely that the work here in AMP.jl and RoME.jl might be bit of guinea pig for how that will play out. Happy to move code upstream however is sensible. I'll link future comments on that to this issue for record keeping.

Maybe not so much a consolidation but I can definitely see a space for interoperability. Manifolds.jl is designed in a way that makes it relatively easy to achieve maximum speed. It should be enough to add methods to functions like log or exp that work on types from CT.jl, and I think it would most likely make sense to upstream such methods. These functions already work for a variety of different types so I wouldn't expect major problems. In any case I can help.

I'd add to this that several of the JuliaRobotics packages (beyond the ones I'm directly involved with) and other packages in Julia ecosystem use CT.jl. CT.jl went hard early on performance by using StaticArrays.jl, so think it will be difficult to squeeze more speed out with a different implementation. I would say that CT.jl has good traction in the community, so sharing the load with them is advisable. I'd hope updating both Manifolds.jl and CT.jl will be doable to get best of both on abstraction and performance.

Sure, I already know StaticArrays.jl quite well and I care about interoperability between it and Manifolds.jl. I've even added a few things to StaticArrays.jl to make it easier. It definitely makes sense to make Manifolds.jl work well with CT.jl too.

Looking at CT.jl dependencies, it seems like an isolated package:

• https://github.com/JuliaGeometry/CoordinateTransformations.jl/blob/master/Project.toml

At worst we can just lift efficient code from CT.jl into a Manifolds.jl related packages, or at best find the right compatibility between JuliaManifolds and JuliaGeometry.

I think it would be easiest to just make Manifolds.jl depend on CT.jl. Manifolds.jl is not intended to be a particularly lightweight package (although we are planning to split out some parts related to distributions to make it a bit lighter). Lightweight interface is in ManifoldsBase.jl.

Oh sorry one more question @mateuszbaran, I'm just checking that the door is still open for using either Vector of elements or Matrix to build a NN tree -- i.e. it doesn't have to be a matrix of points concatenated together?

From code above:

balltree = BallTree(point_matrix, dist)

What I mean is that there still is a route to instead do something like:

vector_elem = coords.(pts)
balltree = BallTree(vector_elem, dist)

Yes, sure, I didn't previously check how exactly NN.jl stores points and it actually makes the most sense to give it a Vector of coordinates.

Tangentially related, just keeping link in this thread (apologies for noise):
http://scikit-learn.sourceforge.net/stable/auto_examples/manifold/plot_manifold_sphere.html

That's quite cool and we already have an issue about it: JuliaManifolds/ManifoldML.jl#4 .

[dehann]

all good, thanks. Think i have what i need to move forward. Will post again when i have something to show. From there we can move code upstream to Manifolds.jl or however makes most sense.

Will look at Manifolds.jl getting CT.jl as a dependency and will comment when i know more, but sounds like the cleanest solution and my initial reaction is yes that sounds like the right path.

Last note, likely that i will try make a GeometryBasics.MetricSphere as a more general version of a HyperSphere. Imagine a "ball" in SE2/SE3 ProductManifold ... kinda weird, but no reason not too, right? Triangle Inequality with mechanism to detect shortest path that "might be behind you" (Manopt.jl perhaps) and circumference is now path around union of all subregions (likely non-differentiable). Perhaps piecewise Greens theorem or something like that will show up, either way i'm going to try. Thanks!

[dehann]

Regular update that preparation work is underway for "vector of manifold elements" that will use content of this issue. Also note some ongoing precursor steps at:

• Consolidate / Simplify factor evaluation (CalcFactor) IncrementalInference.jl#467
• Issue with differential constraint from partial factors IncrementalInference.jl#1010
• Integrate with Manifolds.jl RoME.jl#244

[mateuszbaran]

Hi!

I've recently added more functionality related to distributions on manifolds. Here is an example of Pelletier's KDE: https://juliamanifolds.github.io/Manifolds.jl/stable/tutorials/integration.html#Kernel-density-estimation which looks relevant to this issue. That tutorial also has some notes about exponential-wrapped distributions. They are not fully implemented in Manifolds.jl yet but it shows that key tools are present.

[dehann]

Hi @mateuszbaran, thanks! I looked through the KDE code you added.

---

Just for information/trivia's sake, there are two specific features I am busy implementing which the Pelletier approach does not cover:

• non-isotropic kernels
• computing the products between KDE approximations, including all partial dimension cases.

Further, something that might also not be obvious at first is that the KDEs we use have an internal Ball Tree structure (similar to NearestNeighbors, as above). We however need both balanced (and future work unbalanced) ball trees. Unfortunately the NearestNeighbor.jl implementation of Ball trees was not usable for our case.

I'm implementing (i.e. forced to) all these features from scratch. To highlight the specialized requirements of the implementation, I have called the new on-manifold, metric dependent, balanced/unbalanced ball tree, non-isotropic, kernel agnostic, computational geometry enhanced KDE data structure a 'Manellic tree'. Work currently in progress and hoping to finally close out this years old issue in the near future.

[mateuszbaran]

Hi! That sounds interesting. That Pelletier example is quite basic but the one interesting part of it you can use is the volume_density correction -- it's kernel-independent.

What exactly do you mean by partial dimension cases?

[dehann]

partial dimension cases?

So @Affie and I have been talking about this quite often. Loosely speaking it's the (sub) manifold equivalent of algebraic operations over say for example three variables with only two equations. So for a robotics localization example, if you have two range measurements from known beacons (2 x TranslationGroup{1}) and you're resolving for vehicle position and orientation represented via a SpecialEuclidean(2) variable.

Our legacy code works these "partial" cases by converting to coordinates, conducting the computations on only the affected coordinates; and then retract back to group/manifold after. We're still debating which way we'd like to go forward on this, but it's looking like it will most likely be functional with traits approach.

There is also the consideration of deferring "partial" computations to as late as possible and then invoking all the dispatches for projections etc. just before inference.

[mateuszbaran]

This is an interesting problem. I would say that if we have such partial observations, this is no longer kernel density estimation but something more general. The main feature of KDE is that contributions to density from each observation are additive but here they are not.

I was considering if KDE could be tricked to handle partial observations but there doesn't seem to be any elegant way to do this. The problem is that each sample in KDE has to be a complete one, and when we marginalize out the joint distributions, everything seems to fall apart.

[dehann]

What we've done in the past is have a KDE data structure that can be partial but only certain "features" work. We need the product of KDEs as a major algorithm workhorse. So the ability to multiply various partial KDEs together allows us to reduce the partial nature in the posterior. E.g. p1 = [X; *] and p2 = [*; Y], so then the product of these two partials would be trivial p1 * p2 = [X; Y]. This is sufficient for our current approach, however, we are looking to generally improve on this as we rewrite this part of the code. I have to tell a long story on deconvolutions be more clear.