# How to find almost periodic lattices in a set of high-dimensional points?

sorry for lame question, but I just have no maturity in this direction.

Let's say I have very large set ( millions ) of high-dimensional vectors ( typical dimensionality is 64). These vectors typically come from embedding of social network into a vector space, but this is not so important. Here is what we see using tSNE, for example:

We know, that sometimes some subsets of these points could form almost regular lattices like that: I need either: 1. To prove, that no such structures exist 2. Or find all these structures ( if any )

But the hard part of a problem is that these regular structures could be different, and no one can say -- what type of lattice could approximate these better than another?

It seems, that I have to find some clusters in my vector space, which are not just "dense", but also have some unknown form of regularity. And typical algorithms like DBSCAN or MeanShift will not help me much.

So, could you please give me a couple of hints : what articles to read on this subject ( at least to have more clear problem statement )?

• (+1) I don't think this is a lame question :) - and I definitely don't know how to do it. – Peter Woolfitt May 7 '15 at 19:24
• To start with, I would read about Bravias lattices in 2D and 3D. In 3D, crystallography does stuff like this, look up 'crystal symmetry groups'. In 64D... It's very hard:) – Valentin May 7 '15 at 19:41
• Maybe look for peaks in the Fourier transform? I don't know if that's practical in high dimensions. – Rahul May 7 '15 at 19:43
• Thank you, colleagues ( and @Rahul especially )! I was thinking about k-space approximation, but just wasn't certain about the simplicity of this approach. Basically, I'm trying to solve this task in two steps: 1) Apply conventional density clustering to isolate areas with apparently high density ( i.e. such lattices are likely to be there ), 2) Build BSP tree in each high-density region, and then count the sample entropy of each leaf. If the entropy is at maximum, then it's likely, that points are regularly spaced. – Vast Academician May 7 '15 at 22:04