The Core Answer: Entropy → Exponential Form→ Fast Algorithm

The choice of entropy regularization is not arbitrary - it's the unique regularizer that enables the Sinkhorn algorithm!

Here's the chain:

Entropy regularization → Solution has exponential/Gibbs form → Enables multiplicative updates → Sinkhorn algorithm

Let me unpack this...

1. The Mathematical Magic: KKT Conditions

When you solve:

min Σᵢⱼ Mᵢⱼ Tᵢⱼ - ε·H(T)
subject to: marginals = a, b

The optimal solution has the form:

T*ᵢⱼ = uᵢ · exp(-Mᵢⱼ/ε) · vⱼ

This exponential/Gibbs form is unique to entropy!

Why does this matter?

The constraints Σⱼ Tᵢⱼ = aᵢ become:

uᵢ · Σⱼ exp(-Mᵢⱼ/ε) · vⱼ = aᵢ

⟹ uᵢ = aᵢ / Σⱼ Kᵢⱼ vⱼ    (where K = exp(-M/ε))

This is a simple division! That's why Sinkhorn works - just alternate between computing u and v with divisions and matrix multiplications.

2. Why Other Regularizers Don't Work As Well

Let's see what happens with alternatives: