Trasporto Ottimo: Regolarizzazione Entropica e l'Algoritmo di Sinkhorn

This thesis addresses the computational challenge of Optimal Transport (OT), demonstrating how entropic regularization overcomes its historical limitations. Commencing with the fundamentals of the discrete Kantorovich problem and its duality, the entropic penalty is introduced as a resolution concept. It is shown that this technique transforms the problem into a strictly convex optimization, guaranteeing a unique solution whose particular product-form structure leads directly to the efficient Sinkhorn algorithm. The analysis of this algorithm constitutes the core of the work: its dual nature is revealed, geometrically, by interpreting it as a sequence of Bregman projections, and analytically, by rigorously proving its linear convergence rate by means of Hilbert's projective metric. The soundness of this theoretical framework is finally validated through a robust implementation in Python. Critical issues related to numerical instability are resolved with a hybrid strategy that utilizes the log-domain to ensure stability. This work thus connects classical theory with modern algorithms, demonstrating that the regularized approach renders Optimal Transport a versatile and scalable tool of crucial importance for modern data science.

Questa tesi affronta la sfida computazionale del trasporto ottimo (OT), dimostrando come la regolarizzazione entropica ne superi i limiti storici. Partendo dai fondamenti del problema discreto di Kantorovich e della sua dualità, si introduce la penalizzazione entropica come concetto risolutivo. Viene dimostrato come questa tecnica trasformi il problema in un’ottimizzazione strettamente convessa, garantendo una soluzione unica la cui peculiare struttura a prodotto conduce direttamente all’efficiente algoritmo di Sinkhorn. L’analisi di quest’ultimo costituisce il fulcro del lavoro: se ne svela la duplice natura, geometrica, interpretandolo come una sequenza di proiezioni di Bregman, e analitica, provandone rigorosamente la convergenza a tasso lineare tramite la metrica proiettiva di Hilbert. La solidità di questo quadro teorico viene infine validata attraverso un’implementazione robusta in Python. Le criticità legate all’instabilità numerica sono risolte con una strategia ibrida che ricorre al dominio logaritmico per garantire stabilità. Il lavoro collega così la teoria classica agli algoritmi moderni, dimostrando come l’approccio regolarizzato renda il trasporto ottimo uno strumento versatile e scalabile, di cruciale importanza per le moderne scienze dei dati.