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

Resumo Técnico: Fatoração de Matriz Não Negativa Exata com Sensibilidade ao Gap (Gap-Aware)

Definição do Problema
Este artigo aborda o desafio da Fatoração de Matriz Não Negativa Exata (Exact NMF) no "regime de gap", onde o posto não negativo alvo $r_+$ excede estritamente o posto da matriz $r$ ($r_+ > r$). Trabalhos anteriores [1] estabeleceram um pipeline de "cone-ray" para o regime de suporte uniforme ($r_+ = r$), mas esta abordagem é restritiva: assume que a dimensão interna é igual ao posto da matriz, limita o fator $W$ recuperado ao posto $r$ e carece de liberdade no gauge da Decomposição em Valores Singulares (SVD). Os autores visam estender este pipeline para $r_+ > r$, onde a geometria do espaço de solução muda significativamente, e classificar as fatorações recuperáveis com base na estrutura de posto do fator $W$.

Metodologia
A contribuição central é uma estrutura de gauge SVD de dois lados que generaliza o pipeline cone-ray.

1. Parametrização Simétrica: Em vez de usar os fatores da SVD truncada de posto-$r$ $U_r$ e $V_r$, o método constrói frames ortonormais estendidos:
   $$U_{r_+}(G) = [U_r \mid U_\perp G], \quad V_{r_+}(K) = [V_r \mid V_\perp K]$$
   onde $U_\perp$ e $V_\perp$ geram os complementos ortogonais dos espaços coluna e linha de $M$, e $(G, K)$ são matrizes nas variedades de Stiefel $St(m-r, r_+-r) \times St(n-r, r_+-r)$.
2. Consistência Quadrática: A restrição de fatoração $WH = M$ é transformada em uma condição de consistência quadrada sobre os fatores intermediários $Q$ e $P$:
   $$QP = \text{diag}(S_r, 0) \in \mathbb{R}^{r_+ \times r_+}$$
   Isso permite que $Q$ e $P$ tenham postos variando independentemente de $r$ a $r_+$, desde que seu produto tenha posto $r$.
3. Pipeline Algorítmico: O método emprega uma abordagem de duas fases:
   • Fase A (SVD-Gauge Cone-Ray): Para um gauge $(G, K)$ fixo, calcula os raios extremos dos cones definidos por $U_{r_+}(G)$ e $V_{r_+}(K)$ usando o Método de Descrição Dupla (DDM). Ele classifica subconjuntos de raios por "obtusidade" e tenta encontrar uma testemunha de forma fechada. Se isso falhar, recorre a um programa linear alternado (alt-LP).
   • Fase B (Ramo de W com Posto Deficiente): Um ramo complementar que enumera diretamente $r_+$-subconjuntos das colunas de $M$. Ele testa a viabilidade coluna por coluna via programação linear (LP). Este ramo visa soluções onde $W$ é um subconjeto de colunas de $M$ (implicando $\text{rank}(W) = r$).

Taxonomia de Três Regimes
O artigo classifica problemas de NMF exata em três regimes baseados no posto do fator $W$:

• Regime A ($\text{rank}(W) = r_+$): Posto de coluna total. O cone de dados tem codimensão $r_+ - r$ dentro do cone externo. Os autores demonstram que para matrizes aleatórias densas, o fenômeno de "enclausuramento de folga" (dimensões extras fornecem folga generosa) e a "espessura" da variedade de fatoração de posto não negativo (NRF) válida permitem que a escolha cega de SVD de $(G, K)$ tenha sucesso com probabilidade um.
• Regime B ($\text{rank}(W) = r$): $W$ é um subconjunto de colunas de $M$. Aqui, a variedade NRF válida degenera para um conjunto de medida zero (frequentemente um único ponto na Grassmanniana) devido a restrições estruturais (ex: matrizes bloco-diagonais). A SVD cega quase certamente falha, e a amostragem uniforme de Stiefel não consegue resgatá-la. No entanto, o ramo de W com Posto Deficiente (Fase B) resolve esses casos eficientemente.
• Regime C ($r < \text{rank}(W) < r_+$): $W$ não é um subconjunto de colunas, e seu posto está estritamente entre $r$ e $r_+$. A matriz de slack do octógono regular é o exemplo primário. Embora a formulação simétrica possa representar tais soluções (verificado via um gauge oráculo), a busca cega pelo $(G, K)$ correto permanece sem solução. O cenário de perda é constante por partes em células combinatórias, fazendo com que métodos de otimização Riemanniana local (descida de gradiente, gradiente conjugado) estagnem.

Resultos Principais

• Matrizes Densas (Regime A): Em matrizes gap aleatórias densas de $10 \times 10$ com $r=4$ e $r_+ \in \{5, 6\}$, o pipeline alcança 100/100 de recuperação usando apenas a fase de testemunha de forma fechada. Isso supera o caso $r_+ = r$ (que satura em 79–87/100), atribuído à "folga" geométrica proporcionada pelo gap.
• Matrizes Estruturadas (Regime B): Na família $M_k = \text{diag}(C, J_k)$ (onde $C$ é uma circulante de posto-4 e $J_k$ é uma matriz de todos os uns), o pipeline SVD cego falha completamente para $k \ge 2$ (0/4 sucessos). Reinicializações uniformes de Stiefel também falham (0/50 acertos). No entanto, o ramo de W com Posto Deficiente restaura 4/4 de sucesso em milissegundos.
• O Octógono (Regime C): Para a matriz de slack do octógono regular ($r=3, r_+=6$), existe uma NRF de tamanho 6 que é encontrada por solvers de NMF padrão (sklearn) com alta precisão. Contudo, o toolkit proposto falha em encontrá-la cegamente. Experimentos de oráculo confirmam que a formulação é capaz de representar a solução, mas os métodos de busca cega (amostragem de Stiefel/Grassmann e GD Riemanniana) falham em localizar o gauge viável, ficando presos em mínimos locais com resíduos distantes de zero.
• Toolkit Combinado: Um orquestrador que executa a Fase B seguida pela Fase A cobre tanto o Regime A quanto o Regime B sem regressão nos casos densos, alcançando 100% de sucesso na união testada desses regimes.

Significância e Alegações
O artigo alega estender o pipeline cone-ray de exact-NMF para o regime de gap, fornecendo uma estrutura geométrica unificada. Sua significância reside em:

1. Insight Geométrico: Demonstrar que o regime de gap ($r_+ > r$) relaxa o problema de enclausuramento para matrizes densas, tornando a escolha cega de SVD eficaz, enquanto matrizes estruturadas com restrições de posto apertadas criam espaços de solução de medida zero que heurísticas cegas perdem.
2. Robustez Prática: Introduzir um ramo de "W com Posto Deficiente" que contorna o problema do gauge para matrizes estruturadas, garantindo que o toolkit funcione tanto para dados aleatórios densos quanto para famílias estruturadas específicas (como somas bloco-diagonais).
3. Limitações e Problemas Abertos: Os autores reconhecem modestamente que o Regime C permanece sem solução. A falha dos métodos de otimização local no octógono destaca uma patologia fundamental: o cenário de perda é constante por partes em células combinatórias, impedindo que métodos baseados em gradiente cruzem as paredes das células. O artigo identifica a necessidade de perdas substitutas mais suaves ou estratégias de basin-hopping como trabalho futuro, mas não afirma ter resolvido a busca cega para o Regime C.

O trabalho é apresentado como um "gauge SVD de dois lados" e uma "taxonomia de três regimes" que esclarece a cobertura das ferramentas de exact NMF, distinguindo entre casos onde a SVD cega é suficiente, casos onde a enumeração de subconjuntos de colunas é necessária e casos onde o problema permanece aberto.