Me gustaría poder determinar rápidamente si un núcleo 2D dado de coeficientes enteros es separable en dos núcleos 1D con coeficientes enteros. P.ej
2 3 2
4 6 4
2 3 2
es separable en
2 3 2
y
1
2
1
La prueba real de separabilidad parece ser bastante sencilla utilizando la aritmética de enteros, pero la descomposición en filtros 1D con coeficientes enteros está demostrando ser un problema más difícil. La dificultad parece radicar en el hecho de que las relaciones entre filas o columnas pueden ser no enteras (fracciones racionales), por ejemplo, en el ejemplo anterior tenemos relaciones de 2, 1/2, 3/2 y 2/3.
Realmente no quiero usar un enfoque de servicio pesado como SVD porque (a) es relativamente computacionalmente costoso para mis necesidades y (b) todavía no necesariamente ayuda a determinar los coeficientes enteros .
Algunas ideas ?
MÁS INFORMACIÓN
Los coeficientes pueden ser positivos, negativos o cero, y puede haber casos patológicos en los que la suma de uno o ambos vectores 1D sea cero, p. Ej.
-1 2 -1
0 0 0
1 -2 1
es separable en
1 -2 1
y
-1
0
1
fuente
Respuestas:
Tomé
@Phonon
la respuesta y la modifiqué un poco para que use el enfoque GCD solo en la fila superior y la columna izquierda, en lugar de en las sumas de fila / columna. Esto parece manejar los casos patológicos un poco mejor. Todavía puede fallar si la fila superior o la columna izquierda son todos ceros, pero estos casos se pueden verificar antes de aplicar este método.Muchas gracias a
@Phonon
y@Jason R
por las ideas originales para esto.fuente
¡Lo tengo! Al publicar el código MATLAB, publicaremos una explicación esta noche o mañana
fuente
A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;
. El problema aquí es quesum(A) = 0
síSb = [0 0 0 0 0]
. Voy a intentar modificar su algoritmo para que use la suma de valores absolutos de los coeficientes y ver si eso ayuda. De nuevo, gracias por tu ayuda.abs(M)
, es decir,Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);
y luego siga las indicaciones anteriores, pero todavía no puede ver cómo restaurar las señales paraSa
,Sb
al final. He agregado un ejemplo patológico que ilustra el problema en la pregunta original anterior.Tal vez estoy trivializando el problema, pero parece que podrías:
Si se consideró que todas las filas eran múltiplos constantes de la fila 0 en las pruebas anteriores, entonces tome la lista de escalares de relación de filasx
No es el método más elegante, y es probable que haya una mejor manera, pero debería funcionar, es bastante simple de implementar y debería ser relativamente rápido para matrices de tamaño modesto.
fuente
(De aproximado-a-convolution-as-a-sum-of-separable-convolutions on math.stackexchange).
fuente