Neue Beschleunigte Sinkhorn-Algorithmen verbessern Partial Optimal Transport

Ein neues arXiv-Papier präsentiert ASPOT, eine beschleunigte Variante des Sinkhorn-Algorithmus, die speziell für Partial Optimal Transport (POT) entwickelt wurde. POT ermöglicht es, nur einen Teil der Gesamtmasse zwischen zwei Verteilungen zu transportieren – ein Ansatz, der besonders nützlich ist, wenn die Randverteilungen ungleich groß sind oder Ausreißer enthalten.

Während Sinkhorn-basierte Verfahren weit verbreitet sind, bleiben ihre Komplexitätsgrenzen für POT oft suboptimal, was die Skalierbarkeit einschränkt. ASPOT kombiniert abwechselnde Minimierung mit Nesterov‑beschleunigten Schritten und erzielt damit eine Komplexität von O(n7/3 ε−5/3). Diese Verbesserung bedeutet, dass große Datensätze effizienter verarbeitet werden können.

Darüber hinaus zeigt die Studie, dass eine gezielte Wahl des Entropieparameters γ die Laufzeit des klassischen Sinkhorn-Algorithmus weiter verkürzt. Praktische Experimente auf realen Anwendungsfällen bestätigen die theoretischen Erkenntnisse und demonstrieren die überlegene Leistung von ASPOT im Vergleich zu bestehenden Methoden.