Gap-Aware Exact Nonnegative Matrix Factorization: A Two-Sided SVD Gauge and a Three-Regime W-Rank Taxonomy

Resumen Técnico: Factorización de Matrices No Negativas Exacta con Sensibilidad al Gap (Gap-Aware)

Planteamiento del Problema
Este artículo aborda el desafío de la Factorización de Matrices No Negativas Exacta (Exact NMF) en el "régimen de gap", donde el rango no negativo objetivo $r_+$ es estrictamente mayor que el rango de la matriz $r$ ($r_+ > r$). Un trabajo previo [1] estableció un flujo de trabajo de "cono-ray" para el régimen de soporte uniforme ($r_+ = r$), pero este enfoque es restrictivo: asume que la dimensión interna es igual al rango de la matriz, limita el factor $W$ recuperado al rango $r$ y carece de libertad en el gauge de la Descomposición en Valores Singulares (SVD). Los autores pretenden extender este flujo de trabajo al caso $r_+ > r$, donde la geometría del espacio de soluciones cambia significamente, y clasificar las factorizaciones recuperables basándose en la estructura de rango del factor $W$.

Metodología
La contribución central es un marco de gauge SVD de dos lados que generaliza el flujo de trabajo de cono-ray.

1. Parametrización Simétrica: En lugar de utilizar los factores de la SVD truncada de rango-$r$ ($U_r$ y $V_r$), el método construye marcos ortonormales extendidos:
   $$U_{r_+}(G) = [U_r \mid U_\perp G], \quad V_{r_+}(K) = [V_r \mid V_\perp K]$$
   donde $U_\perp$ y $V_\perp$ abarcan los complementos ortogonales de los espacios columna y fila de $M$, y $(G, K)$ son matrices en las variedades de Stiefel $St(m-r, r_+-r) \times St(n-r, r_+-r)$.
2. Consistencia Cuadrática: La restricción de factorización $WH = M$ se transforma en una condición de consistencia cuadrática sobre los factores intermedios $Q$ y $P$:
   $$QP = \text{diag}(S_r, 0) \in \mathbb{R}^{r_+ \times r_+}$$
   Esto permite que $Q$ y $P$ tengan rangos que oscilan independientemente entre $r$ y $r_+$, siempre que su producto tenga rango $r$.
3. Flujo de Trabajo Algorítmico: El método emplea un enfoque de dos fases:
   • Fase A (SVD-Gauge Cone-Ray): Para un gauge $(G, K)$ fijo, computa los rayos extremos de los conos definidos por $U_{r_+}(G)$ y $V_{r_+}(K)$ utilizando el Método de Doble Descripción (DDM). Clasifica subconjuntos de rayos por "obtusidad" e intenta encontrar un testigo de forma cerrada. Si esto falla, recurre a un programa lineal alternante (alt-LP).
   • Fase B (Rama de $W$ con Deficiencia de Rango): Una rama complementaria que enumera directamente $r_+$-subconjuntos de las columnas de $M$. Prueba la factibilidad columna por columna mediante programación lineal (LP). Esta rama se dirige a soluciones donde $W$ es un subconjunto de columnas de $M$ (implicando $\text{rank}(W) = r$).

Taxonomía de Tres Regímenes
El artículo clasifica los problemas de NMF exacta en tres regímenes basados en el rango del factor $W$:

• Régimen A ($\text{rank}(W) = r_+$): Rango de columna completo. El cono de datos tiene una codimensión $r_+ - r$ dentro del cono exterior. Los autores demuestran que para matrices aleatorias densas, el fenómeno de "envolvente de holgura" (las dimensiones extra proporcionan una holgura generosa) y la "densidad" de la variedad de la factorización de rango no negativo (NRF) válida permiten que la elección ciega de SVD de $(G, K)$ tenga éxito con probabilidad uno.
• Régimen B ($\text{rank}(W) = r$): $W$ es un subconjunto de columnas de $M$. Aquí, la variedad de la NRF válida degenera a un conjunto de medida cero (a menudo un único punto en la variedad de Grassmann) debido a restricciones estructurales (por ejemplo, matrices diagonales por bloques). El SVD ciego casi con seguridad falla, y el muestreo uniforme de Stiefel no logra rescatarlo. Sin embargo, la rama de $W$ con deficiencia de rango (Fase B) resuelve estos casos de manera eficiente.
• Régimen C ($r < \text{rank}(W) < r_+$): $W$ no es un subconjunto de columnas, y su rango está estrictamente entre $r$ y $r_+$. La matriz de holgura del octágono regular es el ejemplo principal. Aunque la formulación simétrica puede representar tales soluciones (verificado mediante un gauge oráculo), la búsqueda ciega del $(G, K)$ correcto sigue sin resolverse. El paisaje de pérdida es constante por partes sobre celdas combinatorias, lo que causa que los métodos de optimización de Riemann local (descenso de gradiente, gradiente conjugado) se estanquen.

Resultados Clave

• Matrices Densas (Régimen A): En matrices gap aleatorias densas de $10 \times 10$ con $r=4$ y $r_+ \in \{5, 6\}$, el flujo de trabajo logra una recuperación de 100/100 utilizando únicamente la fase de testigo de forma cerrada. Esto supera el caso $r_+ = r$ (que se satura en 79–87/100), atribuido a la "holgura" geométrica proporcionada por el gap.
• Matrices Estructuradas (Régimen B): Sobre la familia $M_k = \text{diag}(C, J_k)$ (donde $C$ es una matriz circulante de rango-4 y $J_k$ es una matriz de unos), el flujo de trabajo de SVD ciego falla completamente para $k \ge 2$ (0/4 éxitos). Los reinicios uniformes de Stiefel también fallan (0/50 aciertos). Sin embargo, la rama de $W$ con deficiencia de rango restaura 4/4 éxitos en milisegundos.
• El Octágono (Régimen C): Para la matriz de holgura del octágono regular ($r=3, r_+=6$), existe una NRF de tamaño 6 que es hallada por solucionadores de NMF estándar (sklearn) con alta precisión. Sin embargo, el kit de herramientas propuesto falla en encontrarla de forma ciega. Los experimentos de oráculo confirman que la formulación es capaz de representar la solución, pero la búsqueda ciega (muestreo de Stiefel/Grassmann y GD de Riemann) falla en localizar el gauge factible, quedando atrapada en mínimos locales con residuales lejos de cero.
• Kit de Herramientas Combinado: Un orquestador que ejecuta la Fase B seguida de la Fase A cubre tanto el Régimen A como el Régimen B sin regresiones en los casos densos, logrando un 100% de éxito en la unión de los regímenes probados.

Significancia y Reivindicaciones
El artículo afirma extender el flujo de trabajo de la NMF exacta de cono-ray al régimen de gap, proporcionando un marco geomético unificado. Su importancia radica en:

1. Perspectiva Geométrica: Demostrar que el régimen de gap ($r_+ > r$) relaja el problema de la envolvente para matrices densas, haciendo que la elección ciega de SVD sea efectiva, mientras que las matrices estructuradas con restricciones de rango estrictas crean espacios de solución de medida cero que los heurísticos ciegos no pueden captar.
2. Robustez Práctica: Introducir una rama de "W con deficiencia de rango" que evita el problema del gauge para matrices estructuradas, asegurando que el kit de herramientas funcione tanto para datos aleatorios densos como para familias estructurales específicas (como sumas de bloques diagonales).
3. Limitaciones y Problemas Abiertos: Los autores reconocen modestamente que el Régimen C permanece sin resolver. El fallo de los métodos de optimización local en el octágono resalta una patología fundamental: el paisaje de pérdida es constante por partes sobre celdas combinatorias, lo que impide que los métodos basados en gradientes crucen las paredes de las celdas. El artículo identifica la necesidad de pérdidas sustitutas más suaves o estrategias de basin-hopping como trabajo futuro, pero no pretende haber resuelto la búsqueda ciega para el Régimen C.

El trabajo se presenta como un "gauge SVD de dos lados" y una "taxonomía de tres regímenes" que clarifica la cobertura de las herramientas de NMF exacta, distinguiendo entre los casos donde el SVD ciego es suficiente, los casos donde se requiere la enumeración de subconjuntos de columnas, y los casos que permanecen abiertos.