I have a dataset of ~7k scattered points in 3D which represents a manifold that may or may not "fold unto itself". Here's an example where this does happen (look at the top-right yellow triangles):
My ultimate goal is to have a metric to compare many such datasets, in order to optimize the hyperparameters leading to the formation of this hypersurface/manifold/volume, while minimizing the unwanted folding.
One way to detect whether such folding occurs is by examining the errors when performing leave-one-out cross-validation. Specifically, we can quantify the folding, by a) interpolating the value (color) of each point based on
k nearest neighbors; b) comparing it the interpolated and correct value; and c) aggregating the errors.
When I tried implementing this in MATLAB, using a combination of
kfoldLoss, processing took on the order of minutes - which is unacceptably slow - as I must be able to perform this error computation on the order of a second or less. I know about CUDA-based algorithms for accelerated knn search1. However, as I don't come from this field I can't tell if I can leverage a fast knn search algorithm to speed up the leave-one-out error computation. (In fact, I don't even know if this is the most suitable approach to the problem.)
Is there something "costly" I can compute once for each dataset (kdtree? pairwise distances?) and use that for fast computation of the aggregate error? How else can I speed this up?
I would also be happy to hear about any other algorithm that could quantify the folding effect.