💻 computer science

Riemannian Optimization for Hadamard Products of Low-Rank Matrices

Dit artikel stelt een Riemanniaans optimalisatiekader voor met een nieuwe blokdiagonaal metriek en een afstemmingsvrij Gauss-Newton algoritme om efficiënt laag-rang matrices onder Hadamard-producten te leren door hun inherente schaalingssymmetrieën aan te pakken.

Oorspronkelijke auteurs: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

Gepubliceerd 2026-06-02

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Dans voor Twee Personen

Stel je voor dat je probeert een complexe schildering (een grote datamatrix) te recreëren met slechts twee eenvoudige, laag-resolutie schetsen.

Schets A legt de brede, algemene vormen vast.
Schets B legt de fijne, gedetailleerde texturen vast.

Het artikel betoogt dat de beste manier om de schildering te recreëren niet is om deze schetsen simpelweg op elkaar te stapelen. In plaats daarvan moet je ze met elkaar vermenigvuldigen, pixel voor pixel (dit wordt de "Hadamard-product" genoemd). Dit stelt het model in staat om zeer efficiënt te zijn, waarbij minder "penseelstreken" (parameters) worden gebruikt dan een standaardmethode zou vereisen.

Maar er is een addertje onder het gras. Omdat je twee schetsen met elkaar vermenigvuldigt, zijn er veel manieren om de helderheid van Schets A en het contrast van Schets B aan te passen die resulteren in exact dezelfde uiteindelijke schildering. Het is alsof je zegt: "Ik kan de schildering helderder maken door het licht op Schets A op te draaien," of "Ik kan hem helderder maken door het licht op Schets B omlaag te draaien." Er zijn oneindige combinaties van deze aanpassingen die leiden tot hetzelfde resultaat.

Dit creëert een verwarrend landschap voor computers die het model proberen te leren. Standaard computermethoden raken verdwaald in deze "oneindige lussen" van equivalente oplossingen, waardoor ze tijd en energie verspillen.

Het Probleem: Verdwalen in de Mist

De auteurs wijzen erop dat bestaande methoden (zoals Alternating Gradient Descent of Block Coordinate Descent) worstelen met dit specifieke type probleem:

Standaardmethoden behandelen het probleem alsof je over een vlakke, rechte weg loopt. Maar het werkelijke landschap is gebogen en bobbelig. Ze zetten stappen die te klein zijn of in de verkeerde richting, omdat ze de vorm van het terrein niet begrijpen.
Gespecialiseerde methoden werken geweldig als het doel is om eenvoudige fouten te minimaliseren (zoals "kwadratische fout"), maar ze breken volledig in wanneer je complexere doelen wilt gebruiken (zoals het voorspellen van gebruikersbeoordelingen of het omgaan met rommelige data). Ze zijn als een auto die alleen werkt op een racecircuit, maar stilvalt op een onverharde weg.

De Oplossing: Een Slimme Kaart (Riemanniaanse Optimalisatie)

De auteurs stellen een nieuwe manier voor om dit probleem te navigeren met behulp van Riemanniaanse Optimalisatie.

Beschouw de probleemruimte niet als een plat vel papier, maar als een gebogen, gevouwen oppervlak (een variëteit of manifold).

De "gevouwen" natuur: Vanwege de eerder genoemde "oneindige lussen" (de symmetrie), vertegenwoordigen veel verschillende punten op de kaart eigenlijk exact dezelfde schildering.
De Quotient-variëteit: De auteurs creëren een "quotient manifold". Stel je voor dat je dat gevouwen oppervlak neemt en alle punten die dezelfde schildering vertegenwoordigen, aan elkaar lijmt. Nu heb je een schone, vereenvoudigde kaart waar elk punt uniek is. Je kunt niet meer verdwalen in de "oneindige lussen", omdat de lussen dichtgelijmd zijn.

Het Geheime Wapen: Een Custom Kompas (De Metriek)

Om efficiënt over dit gebogen oppervlak te lopen, heb je een speciaal kompas nodig. In de wiskunde wordt dit een Riemanniaanse Metriek genoemd.

De auteurs hebben een nieuw, op maat gemaakt kompas uitgevonden.

Het Oude Kompas: Standaardmethoden gebruiken een generiek kompas dat ervan uitgaat dat de grond vlak is. Het raakt in de war door de krommingen.
Het Nieuwe Kompas: Het kompas van de auteurs is "blok-diagonaal". Stel je een kompas voor dat voor elke individuele rij en kolom van je schetsen aparte, onafhankelijke sensoren heeft. Het weet precies hoe de "textuur" van één deel van de schets de "vorm" van een ander deel beïnvloedt.
De Magie: Dit kompas is schaalinvariant. Als je besluit om Schets A twee keer zo helder te maken en Schets B half zo helder, maakt het kompas niet uit. Het weet dat je de schildering niet hebt veranderd, dus het raakt niet in de war. Het negeert de "ruis" van willekeurige schaling en focust alleen op de werkelijke vorm van de data.

Het Algoritme: De Wandelaar Zonder Afstemming

Met deze nieuwe kaart en dit nieuwe kompas hebben de auteurs een wandelalgoritme gebouwd genaamd RGD (Riemannian Gradient Descent).

Geen knoppen draaien: De meeste wandelalgoritmen vereisen dat je handmatig een "stapgrootte"-draaiknop aanpast (het afstemmen van hyperparameters). Als je hem te veel draait, schiet je door; als je hem te weinig draait, beweeg je te langzaam. Dit nieuwe algoritme berekent automatisch de perfecte stapgrootte met een "Gauss-Newton"-truc. Het is als een wandelaar die instinctief precies weet hoe groot de stap moet zijn op basis van de helling van de heuvel, zonder dat er handmatige aanpassingen nodig zijn.
Snelheid: Het is ongelooflijk snel. Het schaalt lineair met de hoeveelheid data, wat betekent dat als je de omvang van de schildering verdubbelt, het slechts twee keer zo lang duurt om de schildering te maken, niet vier of tien keer zo lang.

De Resultaten: Winnen van de Race

De auteurs hebben hun wandelaar getest tegen de oude methoden op echte gegevens (zoals filmbeoordelingen van MovieLens en netwerkkaarten).

Nauwkeurigheid: Op de MovieLens-dataset (het voorspellen van filmbeoordelingen) bereikte hun methode de laagste foutmarge (beste nauwkeurigheid) over alle geteste configuraties heen. Het vond betere oplossingen dan de gespecialiseerde "alleen-voor-het-racecircuit"-methoden.
Robuustheid: Wanneer ze de startomstandigheden kunstmatig verstoorden (door één schets erg helder en de andere erg dim te maken), negeerde hun methode de chaos en vond telkens het juiste antwoord. De oude methoden raakten in de war en presteerden slechter.
Veelzijdigheid: In tegen tegenover de gespecialiseerde methoden die alleen werken voor eenvoudige wiskundige problemen, werkt deze nieuwe methode voor elk vloeiend doel, waardoor het een universeel hulpmiddel is voor dit type data.

Samenvatting

Het artikel introduceert een slimmere manier om computers te leren van data die een "multiplicatieve" structuur heeft. Door te beseffen dat het probleem zich afspeelt op een gebogen, gevouwen oppervlak en door een custom kompas te bouwen dat irrelevante schalingstricks negeert, hebben ze een algoritme gecreëerd dat sneller is, nauwkeuriger is en minder menselijke afstemming vereist dan voorheen gebruikelijke methoden. Het is also wordt het vergelijken met de upgrade van een blindelings wandelende persoon naar een wandelaar met een perfect, zelf-instelbare GPS.

Technische Samenvatting: Riemanniaanse Optimalisatie voor Hadamard-producten van Matrices met een Lage Rang

Probleemformulering
Het artikel behandelt de uitdaging om gegevens te modelleren met een multiplicatieve structuur middels het elementgewijze (Hadamard) product van twee matrices met een lage rang. De doelmatrix $W \in \mathbb{R}^{m \times n}$ wordt gemodelleerd als:
$W = (GH^\top) \circ (UV^\top)$
waarbij $G, U \in \mathbb{R}^{m \times r_1, r_2}$ en $H, V \in \mathbb{R}^{n \times r_1, r_2}$ . Hoewel deze formulering een grotere parameterefficiëntie biedt vergeleken met een standaard rank- $r_1r_2$ factorisatie (wat $(m+n)(r_1+r_2)$ parameters vereist in plaats van $(m+n)r_1r_2$ ), introduceert het een complexe optimalisatielandschap. Specifiek vertoont het model symmetrieën die verder gaan dan de standaard General Linear (GL) herparameterisatie-invariantie. Het product $W$ blijft invariant onder gekoppelde rij- en kolomschalingen tussen de twee factorparen $(G, H)$ en $(U, V)$ . Deze extra vrijheidsgraden creëren een uitdagende geometrie waar standaard Euclidische gradiëntafdaling-methoden moeite mee hebben om efficiënt doorheen te navigeren.

Bestaande solvers kampen met beperkingen: Alternating Gradient Descent (AGD) negeert de specifieke geometrie en schaalingssymmetrieën, terwijl Block Coordinate Descent (BCD) zeer effectief is voor kleinste-kwadratenverliesfuncties, maar geen gesloten vorm oplossingen heeft voor niet-kwadratische verliezen (bijv. logistische link-predictie of cross-entropy), wat de toepasbaarheid in robuuste statistiek en andere domeinen beperkt.

Methodologie
De auteurs stellen voor om het leerprobleem te formuleren als een optimalisatietaak op een Riemanniaanse quotient-variëteit. Deze aanpak houdt expliciet rekening met de natuurlijke invarianties van het Hadamard-product.

Variëteitsgeometrie: De auteurs definiëren de quotient-variëteit $\mathcal{M}$ door de volledige symmetriegroep $\mathcal{G}$ weg te factoriseren, welke de volgende bevat:
- Standaard GL-herparameterisatie-invariantie voor elk factorpaar.
- Nieuwe cross-Hadamard schalingssymmetrieën, waarbij inverteerbare diagonale matrices rijen en kolommen over de twee factorparen invers schalen.
  De variëteit wordt geconstrueerd vanuit de ruimte van matrices met volledige kolomrang modulo deze groepswerking.
Nieuwe Riemanniaanse Metriek: Een cruciale bijdrage is de afleiding van een blokdiagonaal Riemanniaanse metriek ( $g_x$ ) afgeleid van de pullback van de Frobenius-inwendige product.
- De volledige pullback-metriek koppelt alle vier de factorblokken, wat resulteert in een dichte en computationeel dure lineaire systeem.
- De voorgestelde metriek behoudt enkel de diagonale blokken van de pullback en verwerpt de kruistermen.
- De metriek wordt gedefinieerd via gewichtsmatrices ( $S$ -blokken) voor elke rij/kolom van de factoren. Bijvoorbeeld, het gewicht voor de $i$ -de rij van $G$ is $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$ , waarbij $Y = UV^\top$ .
- Invariantie: De metriek is bewezen invariant onder zowel de GL-herparameterisatie als de cross-Hadamard schalingssymmetrieën. Dit zorgt ervoor dat de optimizer ongevoelig is voor willekeurige grootteverdelingen tussen de factoren.
- Connectie met BCD: De gewichtsmatrices in de voorgestelde metriek komen exact overeen met de normale vergelijkingen-matrices die worden gebruikt bij BCD-updates. Zo kan de Riemanniaanse gradiënt worden geïnterpreteerd als het uitvoeren van een "zachte" BCD-stap simultaan op alle rijen voor willekeurige gladde verliesfuncties.
Optimalisatiealgoritme (RGD): De auteurs ontwikkelen een Riemannian Gradient Descent (RGD) algoritme:
- Gradiëntberekening: De Riemanniaanse gradiënt wordt berekend door onafhankelijke $r \times r$ lineaire systemen (één per rij/kolom) op te lossen met behulp van de $S$ -blokken.
- Stapgrootte: Een tuning-vrije Gauss–Newton Cauchy stapgrootte is afgeleid. Deze stapgrootte is invariant onder de symmetriegroep en vereist geen hyperparameter-tuning.
- Retractie: Een additieve retractie wordt gebruikt om updates terug naar de variëteit te mappen.
- Complexiteit: De kosten per iteratie schalen lineair met het aantal geobserveerde elementen $N$ ($O(Nr)$) en polynomiaal met de rangen ( $O((m+n)r^4)$ ), wat het efficiënt maakt voor grote datasets.

Belangrijkste Bijdragen

Geometrische Karakterisering: Formele beschrijving van de quotient-variëteitstructuur voor Hadamard-producten, waarbij zowel de GL- als de cross-Hadamard schalingssymmetrieën worden geïdentificeerd.
Schaal-Invariante Metriek: Voorstel van een nieuwe blokdiagonaal Riemanniaanse metriek die de volledige symmetriegroep respecteert en de optimalisatie ontkoppelt in onafhankelijke rij/kolom subproblemen.
Algoritme Ontwikkeling: Afleiding van een RGD-algoritme met een tuning-vrije Gauss–Newton stapgrootte die elke gladde verliesfunctie ondersteunt, in tegen tegenstelling tot BCD die beperkt is tot kleinste kwadraten.
Empirische Validatie: Demonstratie dat de methode prestaties levert die vergelijkbaar zijn met BCD voor kleinste-kwadraten taken, maar BCD overtreft op niet-kwadratische doelstellingen en superieure resultaten behaalt in specifieke Hadamard-rang configuraties.

Experimentele Resultaten
De auteurs evalueerden RGD op synthetische en real-world datasets:

Synthetische Stress Tests: Op $2.000 \times 1.000$ $2.000 \times 1.000$ synthetische targets toonde RGD aan:
- Schaal-invariantie: De herstel-fout bleef constant over variërende diagonale schalingsscheidingen ( $\kappa_{scale}$ ), wat de invariantie-eigenschap van de metriek empirisch verifieert. In tegenstelling hiertoe was AGD gevoelig voor schaling.
- Conditionering: RGD presteerde vergelijkbaar met BCD over variërende factor conditiegetallen, en presteerde significant beter dan AGD.
- Ruis-robuustheid: RGD convergeerde naar de ruisvloer met dezelfde snelheid als BCD, terwijl AGD achterbleef.
Real-World Datasets:
- Full Matrix Approximatie: Op de Camera, Football en Les Misérables datasets volgde RGD nauwgezet BCD in relatieve fout, wat bevestigt dat de metriek BCD-equivalente preconditioning biedt voor kwadratische verliezen.
- MovieLens-1M: In een matrix completion taak met een vaste parameterbudget ( $r_1+r_2=6$ ), behaalde RGD de laagste Held-out RMSE over alle geteste Hadamard-rang configuraties. Opvallend genoeg presteerde de gebalanceerde configuratie $(3,3)$ beter dan de bijna-vanilla $(1,5)$ , wat suggereert dat de Hadamard interactie-capaciteit ( $r_1r_2$ ) bijdraagt aan de nauwkeurigheid. RGD presteerde consistent beter dan AGD en behaalde een lagere RMSE dan BCD in genuante Hadamard configuraties.

Betekenis en Claims
Het artikel claimt de kloof te overbruggen tussen de efficiëntie van BCD voor kleinste-kwadraten problemen en de flexibiliteit van gradiënt-gebaseerde methoden voor algemene gladde verliezen. Door het probleem te verheffen naar een Riemanniaanse quotient-variëteit, bieden de auteurs een principieel kader dat de complexe symmetrieën van Hadamard-producten afhandelt. Het voorgestelde RGD-algoritme biedt een tuning-vrije, schaal-invariante optimalisatiemethode die lineair schaalt met de datagrootte. De auteurs stellen dat dit framework zich natuurlijk uitbreidt naar producten van $k$ matrices met een lage rang en compatibel is met andere Riemanniaanse solvers (zoals conjugate gradients, trust-region methoden), waardoor het een robuust alternatief biedt voor bestaande solvers voor multiplicatieve low-rank modellering.