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

Sintesi Tecnica: NMF Esatta Sensibile al Gap (Gap-Aware Exact Nonnegative Matrix Factorization)

Definizione del Problema
Questo articolo affronta la sfida della Fattorizzazione di Matrici Non Negative Esatta (Exact NMF) nel "regime di gap", dove il rango non negativo target $r_+$ è strettamente superiore al rango della matrice $r$ ($r_+ > r$). Il lavoro precedente [1] ha stabilito una pipeline "cone-ray" per il regime di supporto uniforme ($r_+ = r$), ma tale approccio è restrittivo: assume che la dimensione interna sia uguale al rango della matrice, limita il fattore $W$ recuperato al rango $r$ e manca di libertà nella gauge della Decomposizione in Valori Singolari (SVD). Gli autori mirano ad estendere questa pipeline al caso $r_+ > r$, dove la geometria dello spazio delle soluzioni cambia significativamente, e a classificare le fattorizzazioni recuperabili in base alla struttura del rango del fattore $W$.

Metodologia
Il contributo principale è un framework di gauge SVD a due lati che generalizza la pipeline cone-ray.

1. Parametrizzazione Simmetrica: Invece di utilizzare i fattori della SVD troncata di rango $r$ ($U_r$ e $V_r$), il metodo costruisce frame ortonormali estesi:
   $$U_{r_+}(G) = [U_r \mid U_\perp G], \quad V_{r_+}(K) = [V_r \mid V_\perp K]$$
   dove $U_\perp$ e $V_\perp$ generano i complementi ortogonali degli spazi colonna e riga di $M$, e $(G, K)$ sono matrici sulle varietà di Stiefel $St(m-r, r_+-r) \times St(n-r, r_+-r)$.
2. Consistenza Quadrata: Il vincolo di fattorizzazione $WH = M$ viene trasformato in una condizione di consistenza quadrata sui fattori intermedi $Q$ e $P$:
   $$QP = \text{diag}(S_r, 0) \in \mathbb{R}^{r_+ \times r_+}$$
   Ciò consente a $Q$ e $P$ di avere ranghi indipendenti compresi tra $r$ e $r_+$, a patto che il loro prodotto abbia rango $r$.
3. Pipeline Algoritmica: Il metodo impiega un approccio a due fasi:
   • Fase A (SVD-Gauge Cone-Ray): Per una data gauge $(G, K)$, calcola i raggi estremi dei coni definiti da $U_{r_+}(G)$ e $V_{r_+}(K)$ utilizzando il Metodo della Doppia Descrizione (DDM). Classifica i sottoinsiemi di raggi per "obtusità" e tenta di trovare un testimone (witness) in forma chiusa. Se ciò fallisce, ricorre a un programma lineare alternato (alt-LP).
   • Fase B (Ramo W a Rango Deficiente): Un ramo complementare che enumera direttamente i sottoinsiemi di $r_+$ colonne di $M$. Testa la fattibilità colonna per colonna tramite programmazione lineare (LP). Questo ramo mira a soluzioni in cui $W$ è un sottoinsieme di colonne di $M$ (implicando $\text{rank}(W) = r$).

Tassonomia a Tre Regimi
L'articolo classifica i problemi di NMF esatta in tre regimi basati sul rango del fattore $W$:

• Regime A ($\text{rank}(W) = r_+$): Rango pieno nelle colonne. Il cono dei dati ha codimensione $r_+ - r$ all'interno del cono esterno. Gli autori dimostrano che per matrici casuali dense, il fenomeno dell' "involucro di slack" (le dimensioni extra forniscono uno slack generoso) e lo "spessore" della varietà di fattorizzazione a rango non negativo (NRF) valida permettono alla scelta cieca della SVD di $(G, K)$ di avere successo con probabilità uno.
• Regime B ($\text{rank}(W) = r$): $W$ è un sottoinsieme di colonne di $M$. In questo caso, la varietà NRF valida degenera in un insieme di misura zero (spesso un singolo punto nella Grassmanniana) a causa di vincoli strutturali (ad esempio, matrici blocco-diagonali). La SVD cieca fallisce quasi certamente, e il campionamento uniforme di Stiefel non può rimediare. Tuttavia, il ramo Rank-Deficient W (Fase B) risolve questi casi in modo efficiente.
• Regime C ($r < \text{rank}(W) < r_+$): $W$ non è un sottoinsieme di colonne e il suo rango è strettamente compreso tra $r$ e $r_+$. La matrice di slack dell'ottagono regolare è l'esempio principale. Sebbene la formulazione simmetrica possa rappresentare tali soluzioni (verificato tramite una gauge oracle), la ricerca cieca della corretta $(G, K)$ rimane irrisolta. Il panorama di perdita (loss landscape) è a tratti costante su celle combinatorie, causando il blocco dei metodi di ottimizzazione riemanniana locale (discesa del gradiente, gradiente coniugato).

Risultati Chiave

• Matrici Dense (Regime A): Su matrici casuali dense $10 \times 10$ con $r=4$ e $r_+ \in \{5, 6\}$, la pipeline raggiunge il 100/100 di recupero utilizzando solo la fase del testimone in forma chiusa. Questo supera il caso $r_+ = r$ (che satura tra 79 e 87/100), grazie allo "slack" geometrico fornito dal gap.
• Matrici Strutturate (Regime B): Sulla famiglia di matrici $M_k = \text{diag}(C, J_k)$ (dove $C$ è una matrice circulante di rango 4 e $J_k$ è una matrice di soli uno), la pipeline SVD cieca fallisce completamente per $k \ge 2$ (0/4 successi). Anche i restart uniformi su Stiefel falliscono (0/50 successi). Tuttavia, il ramo Rank-Deficient W ripristina 4/4 successi in millisecondi.
• L'Ottagono (Regime C): Per la matrice di slack dell'ottagono regolare ($r=3, r_+=6$), esiste una NRF di dimensione 6 che viene trovata dai solver NMF standard (sklearn) con alta precisione. Tuttavia, il toolkit proposto fallisce nel trovarla in modo cieco. Esperimenti con oracle confermano che la formulazione è capace di rappresentare la soluzione, ma i metodi di ricerca cieca (campionamento Stiefel/Grassmanniano e GD riemanniana) falliscono, rimanendo bloccati in minimi locali con residui lontani dallo zero.
• Toolkit Combinato: Un orchestratore che esegue la Fase B seguita dalla Fase A copre sia il Regime A che il Regime B senza regressioni sulle matrici dense, ottenendo il 100% di successo sull'unione testata di questi regimi.

Significatività e Rivendicazioni
L'articolo sostiene di estendere la pipeline cone-ray per l'Exact NMF al regime di gap, fornendo un framework geometrico unificato. La sua significatività risiede in:

1. Intuizione Geometrica: Dimostrare che il regime di gap ($r_+ > r$) rilassa il problema dell'involucro per le matrici dense, rendendo efficace la scelta cieca della SVD, mentre le matrici strutturate con vincoli di rango stretti creano spazi di soluzione a misura zero che gli euristiche cieche non riescono a intercettare.
2. Robustezza Pratica: Introdurre un ramo "Rank-Deficient W" che bypassa il problema della gauge per le matrici strutturate, garantendo che il toolkit funzioni sia per dati casuali densi che per specifiche famiglie strutturate (come le somme blocco-diagonali).
3. Limitazioni e Problemi Aperti: Gli autori riconoscono con modestia che il Regime C rimane irrisolto. Il fallimento dei metodi di ottimizzazione locale sull'ottagono evidenzia una patologia fondamentale: il panorama di perdita è a tratti costante su celle combinatorie, impedendo ai metodi basati sul gradiente di attraversare i confini tra le celle. Il lavoro identifica la necessità di perdite surrogate più fluide o strategie di basin-hopping come ricerca futura, ma non pretende di aver risolto la ricerca cieca per il Regime C.

Il lavoro è presentato come una "gauge SVD a due lati" e una "tassonomia a tre regimi" che chiarisce la copertura degli strumenti di Exact NMF, distinguendo tra i casi in cui la SVD cieca è sufficiente, i casi in cui è necessaria l'enumerazione dei sottoinsiemi di colonne e i casi che rimangono aperti.