12
$\begingroup$

Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$?

There is an issue of representing real values here - for simplicity assume that there is (a short) algebraic formula for each coordinate, such that cost of basic arithmetic operations can be assumed as O(1).

The basic question is if this problem is in P?

While at first view this problem might seem simple - usually it is sufficient to test norms of the points and local relations like angles, there are nasty examples where it is e.g. equivalent to graph isomorphism problem.

Specifically, looking at eigenspaces of adjacency matrix of strongly regular graphs (SRG), we can give it geometrical interpretation. Below is the simplest example - two 16 vertex SRGs, which locally look identical, but are not isomorphic:

enter image description here

Adjacency matrix of SRGs has always only three eigenvalues (of known formulas) - looking at eigenspace for eigenvalue 2 above (kernel of $A-2I$), it has dimension 6 - of basis written above. Orthonormalizing it (Gram-Schmidt), we get large space of possible orthonormal bases - differing by $O(6)$ rotation, which rotates "vertical vectors": 16 of length 6. Define such set of vectors as $X\subset \mathbb{R}^6$, $|X|=16$ here, and $Y$ correspondingly for the second graph - converting graph isomorphism question into question if $X$ and $Y$ differ only by rotation.

The difficulty is that all these points are in a sphere and recreate original relations: all neighbors (6 here) are in fixed angle <90 degrees, all non-neighbors (9 here) in another fixed angle >90 degrees, like in the schematic picture above.

So testing based on norm and local angles takes as back to graph isomorphism problem ... but geometric interpretation allows to work on global properties like rotation invariants.

Generally, a natural "global" approach is trying to describe both sets "modulo rotation" (which contains $n(n-1)/2$ degrees of freedom), and then just check if both descriptions are identical.

We can usually define rotation invariants - the question is constructing a complete set of rotation invaraints: completely determining a set modulo rotation.

While I couldn't find a way for practical rotation invariants directly working on points (?), it can be done for polynomials (stack). For degree 2 polynomial $x^T A x$, a complete basis of rotation invariants is e.g. $Tr(A^k)$ for $k=1,\ldots,n$. Diagrammatically they can be represented as length $k$ cycle, and we can analogously construct rotation invariants for higher order polynomials (the remaining question is their independence), e.g. each graph below corresponds to a single rotation invariant of degree 1,2,3,4 polynomial:

enter image description here

The question is how to describe a set of points with a polynomial - generally we need high degree polynomials, e.g. $p(z)=\prod_{x\in X} (x\cdot (z-x))$, but sets for SRGs are quite regular - can be described with just degree 6 polynomial:

$$p(z)=\sum_{x\in X} (x\cdot z -a)^2 (x\cdot z -b)^2 (x\cdot z -c)^2 $$ where $a,b,c$ describe norm and angles in sets obtained for given SRG (are known).

So can we test if two degree 6 polynomials differ only by rotation in polynomial time? If so, graph isomorphism for SRGs is in P.

Are there tougher examples (for testing if two sets differ only by rotation) than from SRGs? I doubt it, allowing for quasi-polynomial upper bound thanks to Babai (?)

Update: I was pointed similarity with (solved) orthogonal Procrustes problem:

$$\min_{O:O^TO=I} \|OA-B\|_F \quad\textrm{achieved for}\quad O=UV^T,\quad\textrm{ where}\quad BA^T=UDV^T$$

from singular value decomposition. We could construct these matrices from our points, however, it would require knowing the order - which we don't know and there are $m!$ possibilities.

We could try e.g. Monte-Carlo or genetic algorithm: switching some points and testing distance improvement using above formula, however, I suspect that such heuristic algorithm might have exponential number of local minima (?)

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Well, the killer examples for practical graph isomorphism algorithms are not necessarily SRGs. There are two papers by Daniel Neuen and Pascal Schweitzer that I discussed here, which give the currently toughest examples. My discussion claims that "the multipede construction ... is basically the normal CFI construction applied to an undirected multi-edge hypergraph". This construction is further modified to make it rigid, which removes all the automorphisms. It was no SRG before, but after it will definitely be not an SRG. $\endgroup$
    – Thomas Klimpel
    Feb 22, 2018 at 21:24
  • $\begingroup$ I think finding principal components of the point sets and checking them would help since PCA transformation has some pretty nice properties. $\endgroup$
    – FazeL
    Feb 22, 2018 at 22:12
  • 1
    $\begingroup$ ThomasKlimpel, could you say something about eigenspaces of these other tough examples? @FazeL, eigenvalues of correlation matrix from PCA are examples of rotation invariants - necessary conditions for differing only by rotation (trivial for SRGs). The problem is to get a sufficient condition, e.g. through a complete basis of rotation invariants - completely determining set (or polynomial) modulo rotation. Here is a general construction for polynomials: arxiv.org/pdf/1801.01058 , the question is how to choose sufficient number (known) of independent invariants? $\endgroup$
    – Jarek Duda
    Feb 23, 2018 at 7:55
  • 1
    $\begingroup$ Those graphs are already colored, For fixed $k$, there are colors for which $2^{k-1}$ nodes have that color, and colors for which 2 nodes have that color. In terms of eigenspaces, this means you get many eigenspaces of dimension $2^{k-1}$, and even more eigenspaces of dimension $2$. At least that is what happens if the CFI construction is applied to a k-regular undirected graph. (But don't worry, isomorphism of SRG is an open problem too.) $\endgroup$
    – Thomas Klimpel
    Feb 23, 2018 at 9:45
  • 1
    $\begingroup$ The eigenspaces of dimension $2^{k-1}$ might actually separate into even smaller eigenspaces, since even for SRG, we have more than 1 eigenspace, but the logic above would suggest that there is just a single eigenspace. Take a look at figure 4.2 in the shorter (more theoretical) paper, so see/understand how those graphs look like. $\endgroup$
    – Thomas Klimpel
    Feb 23, 2018 at 10:06

1 Answer 1

Reset to default
5
$\begingroup$

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree three polynomials is GI-hard (Agrawal-Saxena STACS '06, author's freely available version), and in fact is at least as hard as testing isomorphism of algebras. Now, GI-hardness is not evidence that your problem is not in $\mathsf{P}$, as indeed, your whole questions is essentially whether we can put GI into $\mathsf{P}$ by the approach you suggest. However, the fact that cubic form equivalence already seems significantly harder than GI (e.g. we still do not know if algebra isomorphism is in quasi-poly time, unlike GI) suggests that (a) people have thought of this approach and (b) it is still open.

While I don't know for sure if similar results hold for the orthogonal group, I would be surprised if they didn't hold (esp. if you move from degree 3 to degree 6).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, I see I have a lot to read. Does testing differing by rotation of polynomials also became tough for degree three? The number of coefficients is O(dim^degree), rotation has dim(dim-1)/2 coefficients, so complete description modulo rotation should be given by O(dim^degree) independent rotation invariants. I know how to construct rotation invariants ( arxiv.org/pdf/1801.01058 ), the independence condition seems tough to prove, but high dependence seem unlikely (?) $\endgroup$
    – Jarek Duda
    Feb 23, 2018 at 20:54
  • $\begingroup$ @JarekDuda: The same argument you make in your comment would apply to general linear equivalence, except instead of $\binom{dim}{2}$ coefficients you'd have $dim^2$, but those are both $\Theta(dim^2)$... Dependence between invariants is often a very deep question. Also, it's not just a question of how many independent invariants you need, but (a) can you compute which invariants you need in poly-time, and (b) can you even compute the value of each such invariant in poly-time? $\endgroup$
    – Joshua Grochow
    Feb 24, 2018 at 2:30
  • $\begingroup$ Sure, if only being able to construct large number of invariants - while I don't know if it is true for other equivalence types(?), for rotation invariants there is construction where every graph gives one invariant, and there are systematic constructions of large numbers e.g. in analogy to length k cycle graphs for Tr(A^k) invariant for degree 2 polynomial x^T Ax. For fixed degree polynomial, we can produce sufficient number (or much more) of invariants in poly-time - the remaining problem is to ensure sufficient number of independent ones among them. $\endgroup$
    – Jarek Duda
    Feb 24, 2018 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.