Exact Nonnegative Matrix Factorization via Cone-Ray Witnesses: Obtuseness Ranking, Saturation Curves, and an Augmented Alt-LP Breakthrough

Technische Samenvatting: Exacte Niet-negatieve Matrix Factorisatie via Kegel-Straal Getuigen

Probleemstelling
Het artikel behandelt het probleem van de Exacte Niet-negatieve Matrix Factorisatie (NMF). Gegeven een niet-negatieve matrix $A \in \mathbb{R}^{m \times n}_{\ge 0}$ met een niet-negatieve rang van maximaal $r$, is het doel om niet-negatieve factoren $W \in \mathbb{R}^{m \times r}_{\ge 0}$ en $H \in \mathbb{R}^{n \times r}_{\ge 0}$ te vinden waarvoor geldt dat $A = WH^\top$ met een residu van nul. In tegenstelling tot benaderende NMF (gebruikt bij topic modeling en aanbevelingssystemen), die streeft naar een benadering met lage fout, richt dit werk zich op het terugvinden van een exacte factorisatie zonder de separabiliteitsvoorwaarde (waarbij de kolommen van $A$ een deelverzameling zijn van de basisvectoren) te veronderstellen. Het artikel richt zich op kleinschalige instanties waar exacte reconstructie theoretisch mogelijk is, maar computationeel uitdagend door combinatorische beperkingen.

Methodologie
De auteurs stellen een "cone-ray pipeline" voor die het NMF-probleem transformeert naar een zoektocht over polyhedrale kegels. De methodologie verloopt via vier stadia:

1. SVD-truncatie: De invoermatrix $A$ wordt gedecomposeerd via dunne SVD ($A = U S V^\top$). De auteurs definiëren orthogonale bases $A_{orth} = U_{:,1:r} \sqrt{S_{1:r,1:r}}$ en $A_{orth1} = V_{:,1:r} \sqrt{S_{1:r,1:r}}$. Elke exacte factorisatie kan worden uitgedrukt als $W = A_{orth}Q$ en $H = A_{orth1}P$, waarbij $Q, P \in \mathbb{R}^{r \times r}$ voldoen aan $QP^\top = I_r$.
2. Constructie van Polyhedrale Kegels: De niet-negativiteitsbeperkingen op $W$ en $H$ impliceren dat de kolommen van $Q$ en $P$ binnen specifieke polyhedrale kegels moeten liggen, gedefinieerd door $A_{orth}$ en $A_{orth1}$. De auteurs gebruiken de Double Description Method (DDM), geïmplementeerd via cddlib, om de extreme stralen ($R_{orth}$ en $R_{orth1}$) van deze kegels te berekenen.
3. Uniform-Support Witness (Gesloten Vorm): De kerninnovatie is een parametrisering waarbij de kolommen van $Q$ en $P$ worden beperkt tot niet-negatieve combinaties van een specifieke deelverzameling van $r$ stralen uit de extreme stralen van de kegel. Laat $T$ en $K$ $r$-deelverzamelingen van straalindices zijn. Als $Q = R_T \mu$ en $P = R_K \nu$ met $\nu = I_r$, dan vervalt de beperking $QP^\top = I_r$ tot een gesloten vorm conditie:
   $$M_T = R_T^{-1} (R_K^\top)^{-1} \ge 0$$
   Indien de matrix $M_T$ elementgewijs niet-negatief is, wordt een exacte NMF direct teruggevonden. Deze test is computationeel goedkoop (microseconden).
4. Obtuse-gerankte Zoektocht: Omdat het aantal mogelijke $r$-deelverzamelingen combinatorisch is, rangschikken de auteurs kandidaat-deelverzamelingen op basis van een geometrische "obtuse" score: $|\det(R_T)| / \prod \|R_{T,i}\|$. Deze score meet de bijna-orthogonaliteit van de stralen; hogere scores duiden op een "bredere" kegel, wat waarschijnlijker een niet-negatieve getuige oplevert. Het algoritme doorloopt de top-kandidaten in deze rangschikking.
5. Geaugmenteerde Alt-LP Fallback: Wanneer de closed-form witness $M_T$ niet haalbaar is (d.w.z. negatieve elementen bevat), gooit de methode het paar niet simpelweg weg. In plaats daarvan augmenteert de methode de support-sets $T$ en $K$ door $k=2$ extra stralen toe te voegen die maximaal hoekig gescheiden zijn van de bestaande stralen. Dit creëert een $r \times (r+k)$ support. De auteurs lossen vervolgens de coëfficiënten $\mu, \nu$ op met een Alternating Linear Program (alt-LP) die de slack minimaliseert, waardoor de strikte uniform-support beperking wordt versoepeld terwijl de traceerbaarheid behouden blijft.

Belangrijkste Bijdragen

1. Closed-Form Witness onder Uniform Support: Het artikel stelt vast dat voor exacte-rang inputs de gezamenlijke niet-negativiteitsbeperking reduceert tot een eenvoudige elementgewijze niet-negativiteitscontrole van een vooraf berekende matrix $M_T$. Dit biedt een microseconde-test voor de haalbaarheid van exacte factorisatie.
2. Obtuse-gerankte Zoektocht en Saturatieanalyse: Door middel van een 100-proefs Monte Carlo studie ($m=n=10$) karakteriseren de auteurs de prestaties van de obtuse heuristiek. Ze tonen aan dat de zoektocht verzadigt bij een budget van de top-200 kandidaten; het verhogen van het budget naar de top-400 levert verwaarloosbare winst op. Cruciaal is dat ze aantonen dat mislukkingen voorbij dit punt structureel zijn (de kegels missen bijna-orthogonale deelverzamelingen) in plaats van te komen door een onvoldoende zoekbudget.
3. Identificatie van Schalingsmuren: Het artikel documenteert specifieke faalmodi:
   • Dimensionaliteit: Het verhogen van $m, n$ bij een vaste $r$ (bijv. $m=n=15$) vermindert feitelijk de succesratio omdat de duale kegels "slanker" worden, waardoor ze minder bijna-orthogonale deelverzamelingen missen.
   • DDM Bottleneck: Op grote datasets zoals Olivetti faces ($400 \times 4096$) wordt de DDM-stap onuitvoerbaar door de explosie van ongelijkheden, zelfs voor kleine $r$.
4. Hybride Geaugmenteerde-Alt-LP Doorbraak: De primaire bijdrage is een hybride algoritme dat de closed-form test combineert met een geaugmenteerde support alt-LP. Door de uniform-support restrictie alleen wanneer nodig te versoepelen, doorbreekt deze methode de structurele plafond die wordt waargenomen in de closed-form benadering.

Resultaten

• Kleinschalig ($m=n=10$):
  • De closed-form (top-200) benadering behaalde succesratio's van 79/85/58 uit 100 voor $r=4, 5, 6$.
  • De hybride benadering (closed-form + augmented alt-LP) verbeterde dit naar 99/95/75, waarmee het structurele plafond effectief werd doorbroken.
  • Wanneer succesvol, was de reconstructiefout op machineprecisie ($\sim 10^{-15}$).
• Middelgroot Schaal ($m=n=15$):
  • De closed-form benadering faalde significant (37/7/0 voor $r=4,5,6$).
  • De hybride benadering herstelde 78/28/0 successen, wat verbetering toont maar een nieuwe structurele muur raakt bij $r=6$ waar de kegels zelfs voor $k=2$ augmentatie te slank waren.
• Grootschalig (Olivetti):
  • De pipeline slaagde er niet in om de DDM-stap te voltooien binnen een budget van één uur, wat de ontraceerbaarheid van exacte extreme-ray enumeratie voor hoog-dimensionale data benadrukt.

Betekenis en Claims
Het artikel claimt een volledig uitvoerbare toolkit te bieden voor exacte NMF die niet afhankelijk is van separabiliteitsaannames. De significantie ligt in:

• Certificering: In tegen tegenover benaderende methoden geeft de toolkit een certificaat van exactheid (machineprecisie reconstructie) wanneer deze slaagt.
• Geometrisch Inzicht: Het karakteriseert rigoureus de geometrische condities (bijna-orthogonaliteit van kegelstralen) die vereist zijn voor exacte factorisatie, en toont aan dat "brede" kegels noodzakelijk zijn voor de closed-form oplossing.
• Praktische Doorbraak: De hybride augmented-Alt-LP methode is de eerste variant in de studie die de structurele plafond van de closed-form witness beslist doorbreekt en de succesratio's boven de 90% brengt voor kleine dimensies.

De auteurs blijven bescheiden over de beperkingen en erkennen dat de pipeline te maken heeft met vier "schalingsmuren": de explosie van het aantal stralen in DDM, de uniform-support restrictie (gedeeltelijk opgeheven), numerieke conditionering, en de verzadiging van de slack-LP op volledig niet-uniforme varianten. Ze suggereren dat toekomstig werk de schaalbaarheid van DDM (via sampling) en diepere augmentatie of alternatieve solvers (NNLS) moet aanpakken voor de resterende structurele defecten.