¿existe un algoritmo eficiente para comparar colecciones de puntos?

Question

Digamos que usted tiene dos conjuntos de puntos de M $p_1...p_M$ y $q_1...q_M$, que se encuentran en $\mathbb{R}^N$. ¿Hay una manera eficiente (por ejemplo polinomio en M y N) algoritmo para determinar si los sistemas del punto son los mismos hasta algunos transformación ortogonal? Es decir, $\exists O$ donde $O^T O=I$s.t. $p_i = O q_i, i=1...M$.

Answer 1

Sí. Calcular la descomposición de valor singular de los dos conjuntos de puntos (como matrices de vectores de sus coordenadas). Si los valores singulares no está de acuerdo, entonces no hay ortogonal de la matriz de asignación de uno a otro. Si los valores propios de acuerdo, entonces los vectores singulares son un sistema de coordenadas ortogonales en el que los dos conjuntos pueden ser idénticos, lo que es fácil de comprobar ya que ahora usted puede ordenar los puntos con respecto a su proyección en el primer singular vector, que los divide en compartimientos -- si los envases son todos la misma cardinalidad, ordenar cada bin por la proyección en el segundo singular vector, que los divide en subbins -- si el subbins son todos de la misma cardinalidad, ordenar cada subbin por la proyección en la tercera del singular del vector, ..., y así sucesivamente. Algunos sub-...-subbin no coinciden cardinalidad, por lo que el punto de conjuntos no son ortogonalmente relacionados, o cada recipiente se reduce a la cardinalidad de uno, por lo que es trivial para verificar los partidos, o se reduce a los conjuntos de puntos cuyas coordenadas completamente de acuerdo. En cada paso, usted encontrar los puntos no coinciden, o se termina mostrando lo que hacen.

Tenga en cuenta que este método realmente determinar si existe una traducción seguida de una rotación a la que se asigna el punto uno en el otro. (Esto es debido a que la enfermedad vesicular porcina ignora la media del conjunto de puntos, y usted también puede: traducir uno significa para el otro, a continuación, girar.) Si usted no desea permitir las dos nubes de puntos de a distintos medios, a continuación, comprobar que esta primera. Si no la han igualado los medios, luego de aplicar la anterior.

Como un aparte, ya que el problema en realidad no solicitar el ortogonal de la matriz: la Transformación del conjunto de vectores singulares por un conjunto de puntos para el conjunto de vectores singulares para el otro, para el cálculo de la transformación ortogonal entre ellos, es sencillo. (En realidad. Es sólo un cambio de base entre bases ortogonales.)

El SVD es $O(N^2M + M^3)$. Las proyecciones son en el peor de los $O(NM)$. La clasificación es, en el peor, $O(NM \log M)$ (ya que estamos sólo la clasificación en la pseudo-real número de proyecciones, no algún tipo de orden lexicographic) y no puede ser que este mal desde la dirección de la mayor dispersión en el conjunto de puntos es capturada en el primer singular vector (de modo que no puede haber un solo ocupado de reciclaje en las primeras repeticiones de la clasificación-en-contenedores de fase). En realidad podemos ser descuidado en la clasificación-en-contenedores de fase y sólo una especie en cubos en lugar de precisar las proyecciones. (Esto será necesario si las proyecciones se calculan con precisión finita ya que no queremos rechazar dos puntos que de acuerdo a la precisión de la multiplican y se acumula en la comparación.) La asintótica en el tiempo de ejecución de las estimaciones anteriores asumen que la constante de tiempo de la aritmética, que puede no ser el caso si usted está usando algo más complicado que el de la máquina de punto flotante de precisión de las representaciones de las coordenadas.

Answer 2

Yo llamo a esto el método de fuerza bruta y no sé lo suficiente como para hacer Grandes-O análisis en ello, pero ya va.

Usted está preguntando si existe $O = (o_{ij})$ tal que $p_i = O q_i$. Pero cada una de las $p_i$$\Bbb{R}^N$, por lo que es lo mismo que preguntar si hay una especial operador lineal

$\mathcal{O} = \begin{pmatrix} O & 0 & \dots & 0 \\ 0 & O & \dots & 0 \\ \vdots & & \ddots\\ 0 & 0 & \dots & O\end{pmatrix}$ ($NM \times NM$ matriz con $O$ ampliado de la manera obvia) de forma tal que $p = \begin{pmatrix} p_1^1 \\ p_1^2 \\ \vdots \\ p_1^N \\ \vdots \\ p_M^1 \\ \vdots \\ p_M^N\end{pmatrix} = \mathcal{O} q$. El único problema ahora es que las cantidades que se está resolviendo para residir en una matriz de cuando sería más agradable a en el vector que se multiplica una matriz por. De esa manera usted puede utilizar el estándar de matriz ampliada métodos con la fila de la eliminación.

Así, encontramos los dispersos $NM \times N^2$ matriz $\mathcal{Q}$ con las entradas de $q$ tal que $\mathcal{Q} o = p$ donde $o$ es el vector de entradas de $O$ que se está resolviendo.

Esta no es la dirección de la transformación ortogonal parte. Para que demostrar que $p_i = O q_i$ $O^TO = I$ fib $p_i = O q_i$$q_i = O^T p_i$. A continuación, el formulario de $p$ $\mathcal{Q}$ $q_i$'s así como a $p_i$'s.

Ahora resolver para$o$, usando el estándar de la fila-elemination.

Answer 3

Primero de todo, la respuesta a la pregunta como se dijo es claramente negativo: hay Que tener en cuenta no sólo el número de puntos, sino también de sus coordenadas. Para simplificar, voy a trabajar con los puntos que sólo tienen coordenadas enteras escritas en forma binaria. Para hacer cualquier cálculo con un vector de ${\bf x}=(x_1,...,x_N)$ primero tienes que ser capaz de escribir que tiene la complejidad comparable a la $$ ({\bf x}):=\sum_{i=1}^N\log(|x_i|).$$ Por lo tanto, la pregunta correcta es un polinomio algoritmo en términos de $$ (p):= \sum_{j=1}^M ({\bf p}_j)$$ donde cada una de las ${\bf p}_j$ es un vector, y lo mismo $q$'s. Voy a considerar el caso general cuando todos los cuadrados de la distancia Euclídea normas $$ |{\bf p}_j|^2, i=1,...,M$$ son distintas y todas las normas $$ |{\bf q}_j|^2, i=1,...,M$$ también son distintos. A continuación, puede aplicar primero un algoritmo de ordenación para organizar los números de $|{\bf p}_j|^2, j=1,...,M$ $|{\bf q}_j|^2, j=1,...,M$ en el orden decreciente. Dicha clasificación se puede hacer en el polinomio (en realidad, subquadratic) tiempo. Supongo, que ya está hecho. Entonces cualquier transformación ortogonal envío de $p$'s $q$'s tiene que enviar a ${\bf p}_i$${\bf q}_i$. A continuación, la transformación ortogonal existe si y sólo si el correspondiente interna de productos $$ \langle {\bf p}_j, {\bf p}_k\rangle , \langle {\bf q}_j, {\bf q}_k\rangle $$ son todos de la misma (por cada par $(j,k)$, $j<k$). [Verificar si y sólo si es elemental de álgebra lineal.] La comparación de estas interior de productos se puede hacer en el polinomio del tiempo con respecto a $(p)$$(q)$.

Similar polinomio solución existe en el no genéricas caso así, que implica la clasificación de (algunos de) los anteriores interior de los productos en el orden decreciente. Sin embargo, los detalles son un poco larga para los márgenes proporcionados por el MSE.