Tensor CUR Decomposition under the Linear-Map-Based Tensor-Tensor Multiplication

Resumen Técnico: Descomposición Tensor CUR bajo la Multiplicación Tensor-Tensor basada en Mapas Lineales

1. El Problema

La descomposición de tensores de bajo rango es fundamental para la compresión y representación de grandes conjuntos de datos multidimensionales (como videos e imágenes). Tradicionalmente, para aplicar álgebra matricial a los tensores, se recurre al "aplanamiento" (flattening), lo que destruye la estructura multivariante de los datos.

Aunque existen productos tensoriales como el T-product, este es un caso particular. El problema que aborda este artículo es la necesidad de extender las técnicas de descomposición matricial clásicas —específicamente la descomposición CUR (que utiliza filas y columnas reales del dato original en lugar de vectores ortogonales sintéticos)— al marco más general de la multiplicación tensor-tensor basada en mapas lineales ($\ast_M$-product).

2. Metodología

Los autores proponen una nueva técnica de descomposición denominada $\ast_M$-CUR. El enfoque se basa en los siguientes pilares:

• Multiplicación $\ast_M$-product: Es una operación que generaliza el T-product. Utiliza un mapa lineal $M$ para transformar el tensor a un dominio donde la multiplicación se comporta de manera similar a la matricial (mimética de matrices).
• Construcción de la Descomposición:
  1. Se seleccionan conjuntos de índices de columnas ($J$) y filas ($I$) del tensor original $A$.
  2. Se mapea el tensor al dominio transformado mediante el producto modo-3 con $M$ ($\text{b}_A = A \times_3 M$).
  3. En este dominio transformado, se realiza una descomposición CUR de forma independiente en cada "rebanada frontal" (frontal slice).
  4. Se reconstruye la aproximación en el dominio original utilizando la operación $\ast_M$ y la pseudoinversa del mapa lineal.
• Casos de $M$: La metodología es versátil y contempla tres escenarios según la naturaleza de la matriz $M$: invertible (reconstrucción exacta posible), sobreyectiva (aproximación en espacio proyectado) e inyectiva (pseudo-CUR).

3. Contribuciones Clave

• Nuevo Marco de Descomposición: La introducción formal de la descomposición $\ast_M$-CUR, extendiendo el álgebra de tensores más allá de la familia de la SVD (Descomposición en Valores Singulares).
• Análisis Teórico:
  • Demostración de las condiciones de exactitud para el caso invertible (si el multirango de la matriz de selección $U$ es igual al de $A$).
  • Establecimiento de límites de perturbación, demostrando que la descomposición es robusta ante errores o ruido en los datos originales.
• Versatilidad Algorítmica: El método permite utilizar diferentes transformaciones (DCT, DFT, DST o matrices dependientes de los datos) según la aplicación.

4. Resultados Experimentales

Los autores evaluaron el método en la tarea de separación de primer plano y fondo (foreground-background separation) en secuencias de video:

• Rendimiento Cuantitativo: Utilizando métricas como AGE (Error de nivel de gris promedio), pEPs (Porcentaje de píxeles con error) y PSNR (Relación señal-ruido pico), el método $\ast_M$-CUR demostró ser altamente competitivo. En la mayoría de los casos, superó o igualó a métodos robustos de matrices y otras descomposiciones tensoriales (como BM y SS-SVD).
• Rendimiento Visual: Las comparaciones visuales muestran que la propuesta genera menos ruido visual y produce bordes más definidos en los objetos en movimiento en comparación con la descomposición BM y la SS-SVD, las cuales presentan artefactos verticales.
• Eficiencia: Se observó que el tiempo de ejecución varía según el mapa $M$, siendo los casos sobreyectivos los más rápidos.

5. Significancia

Este trabajo es significativo porque cierra una brecha en el álgebra de tensores basada en mapas lineales. Al proporcionar una alternativa a la SVD que utiliza datos reales (filas y columnas originales), la descomposición CUR es más interpretable y útil para la compresión de datos, ya que permite representar un tensor complejo utilizando solo una pequeña fracción de sus elementos originales, manteniendo la estructura multivariante esencial.