Entropic Regularization·Log Sinkhorn

정규화는 문제 자체를 바꾼다

양의 주변 질량에서 실습의 목적은

Entropy 부호와 상수 관례를 확인해야 한다. 값이 음수일 수 있고 Wasserstein metric이 아니다. 질량 분산을 보상하므로 수송 비용 항은 원래 최솟값보다 커질 수 있다. ε를 줄이는 것과 각 정규화 문제를 정확히 푸는 것은 별개다.

로그 좌표의 행·열 갱신

Entropy conjugate 쌍대는

유한 potential에는 원래 LP의 fᵢ+gⱼ≤Cᵢⱼ를 그대로 걸지 않는다. 지수 conjugate 항이 올바른 벌점을 제공한다.

f 갱신은 행, g 갱신은 열 주변 질량을 맞춘다. 작은 kernel을 직접 나누는 대신 log-sum-exp를 사용한다. 표는 완전한 행·열 cycle을 기록한다. 열 갱신 뒤 열 잔차가 작아도 행 잔차는 남을 수 있다.

유한 반복은 가능 상한이 아닐 수 있다

Raw 계획은 exp((f+g−C)/ε)다. 두 주변 제약을 만족하기 전에는 비용이나 정규화 목적값이 원문제 상한이 아니다. 반면 어떤 유한 potential의 쌍대값도 정규화 문제의 하한이다.

이 2×2 문제는 양의 기준 해를 독립적으로 구할 수 있다.

작은 off-diagonal 질량을 거의 포화된 대각값에서 빼지 않고 안정적인 양의 이차근으로 직접 구한다. 균형 L=1의 경우 그 질량은 1/[2(1+exp(1/ε))]다.

안정적인 Fenchel 잔차

가능 기준 γ의 primal–dual gap은 εΣ[γlog(γ*/γ_raw)−γ*+γ_raw]다. 두 질량이 가까우면 안정적인 국소 나머지를 사용하여 작은 양의 잔차를 보존한다. 거의 같은 두 목적값을 직접 빼는 방식과 구별하자.

a=b=0.5,L=1,ε=0.5에서는 대칭성 때문에 한 cycle로 맞는다. 기준 수송 비용은 약 0.119203, 정규화 목적값은 약 −0.910038이다. 어느 것도 원래 W₂라고 부르면 안 된다.

직접 풀기와 풀이

같은 대칭 예에서 ε=0.05이면 작은 기준 질량은 약 1.030577×10⁻⁹로 여전히 양수다. 다음 비대칭 초기 kernel을 선택하자. Raw 목적값이 진짜 최솟값보다 낮을 수 있는 이유는 불가능성이다. 먼저 행·열 오차를 확인한다.

작은 주변 잔차, 정규화 gap, 원래 수송에 대한 작은 편향은 서로 다른 정확도 조건이다. 이 유한 예제가 고정 반복 수로 모든 수송 문제가 풀린다는 보장은 아니다.

더 읽기: Peyré와 Cuturi의 최적수송 교재.