Finite first-order boundary transport

For finite persistence diagrams with finite deaths, allowing real mass to split between occurrence labels does not lower the first-order partial-matching minimum. The transport problem here uses a boundary reservoir, unit input mass per occurrence, and the birth–death maximum norm. An integral plan attains its infimum, although fractional plans can also attain it.

Occurrences, real plans and costs

Let x : I → ℝ × ℝ and y : J → ℝ × ℝ, with finite, possibly empty label types. For the persistence-diagram interpretation every pair has birth < death. Births may be negative; all coordinates are real, and essential bars are absent. Equal point values keep their separate labels and contribute unit mass each. The supporting real-cost algebra also holds without the positive-lifetime condition.

Write c(i,j) = ‖x i - y j‖∞ and δx(i) = |death(x i)-birth(x i)|/2, with the analogous δy. These are the existing finitePairCost and diagonalCost, converted to real numbers. diagonalCost_le_max proves that every diagonal destination costs at least δx; diagonalCost_midpoint proves attainment at the midpoint.

A FiniteBoundaryPlan I J is a real matrix a whose entries are nonnegative and whose row and column sums are at most one. Its residual masses are

u(i) = 1 - Σⱼ a(i,j),     v(j) = 1 - Σᵢ a(i,j).

deletionMass_nonneg, insertionMass_nonneg, source_balance and target_balance verify the residual signs and the unit marginal equations. Sources may send their residual mass to the boundary; targets may receive theirs from it. No equality of the two input cardinalities is assumed. Every feasible real matrix is admitted, including fractional ones.

The plan's cost is the unnormalized sum

C(a) = Σᵢⱼ a(i,j)c(i,j) + Σᵢ u(i)δx(i) + Σⱼ v(j)δy(j).

The all-zero matrix is feasible, and cost_nonneg bounds all candidate costs below by zero. finiteFirstOrderBoundaryTransportCost x y is their real infimum. Neither the input mass nor the cost is normalized by a cardinality.

Equality and attainment

finiteFirstOrderBoundaryTransportCost_eq_matchingCost proves

finiteFirstOrderBoundaryTransportCost x y = finiteFirstOrderMatchingCost x y.

The right side is the attained finite partial-matching minimum. ofMatching embeds its partial injections as 0–1 incidence plans, and cost_ofMatching preserves their paired and both unmatched costs exactly. The converse inequality, matchingCost_le_cost, quantifies over every feasible real plan. Consequently exists_minimizing_boundaryPlan supplies an incidence-plan minimizer, and exists_matching_cost_le supplies a partial matching of no greater cost than any given plan. These are noncomputable existence results; no numerical optimization algorithm is supplied.

Exact one-empty and both-empty formulas and invariance under arbitrary label equivalences follow from the equality. The matching distance laws and existing PI bounds can likewise be used by rewriting; their hypotheses and constants remain those of their original APIs.

Boundary augmentation and the fractional inequality

Use rows I ⊕ J and columns J ⊕ I. The first summands are occurrences; the second are dummies labelled by the opposite diagram. The raw cost blocks are

             target J       source dummies I
source I     c(i,j)          δx(i)
target       δy(j)           0
dummies J

The deletion block is constant across each entire source row, and the insertion block across each entire target column. A dummy with a different label is allowed at exactly the same boundary cost.

OccurrenceMatching.ofBoundaryAssignment restricts any augmented bijection to its occurrence-to-partial injection. totalFiniteCost_ofBoundaryAssignment proves exact cost preservation by reindexing the dummy charges: an unmatched target has precisely a dummy predecessor. toBoundaryAssignment completes a partial matching using its reverse: unmatched sources use their own dummies, unmatched target dummies go to their targets, and matched target dummies go to the dummies of their matched sources. Restriction of this completion is the original matching. This is a section, not a bijection of representations; other dummy permutations can encode the same partial matching.

For a real plan, the augmented mass matrix is

D(a) = [ a           diag(u) ]
       [ diag(v)     aᵀ      ].

Each row and column sums to one. paddedMatrix reindexes columns by Equiv.sumComm so that paddedMatrix_doublyStochastic has one square index type. The linear cost of this matrix is exactly C(a); its lower-right block has zero cost.

The pinned mathlib theorem exists_eq_sum_perm_of_mem_doublyStochastic expresses the padded matrix as a finite convex combination of permutation matrices, including the empty-index case. Each permutation restricts to a partial matching with the same cost, so each cost is at least the matching minimum. Applying the linear cost to the convex combination gives that lower bound for C(a). The incidence plan of an already minimizing matching proves the reverse inequality and attainment.

Concrete controls

The examples compile against the definitions:

  • For (0,2) and (0,4), sending mass 1/2 between them leaves boundary mass 1/2 on each side and costs 5/2. Pairing costs 2; deleting both costs 3.
  • For (0,2) and (10,12), deleting both costs 2, while pairing costs 10. The raw cost after collapsing the boundary therefore fails the triangle inequality.
  • An augmented permutation deletes a source through a differently labelled dummy and inserts a target from a differently labelled dummy. Their costs are 1 and 3, with one additional pair of cost zero.
  • Two source copies and one target copy of (0,2) have minimum 1. Sending half of each source to the target is a fractional optimum, alongside an integral optimum. Removing duplicate occurrences would change this result.
  • Empty inputs, both one-empty directions, empty padding, completion's section identity, and label reindexing are also checked.

Primary-source correspondence and limits

Figalli–Gigli, Problem 1.1, has priority for boundary-reservoir transport. Its original domain is bounded and open in Euclidean space and its cost is quadratic Euclidean distance. This library result does not attribute the later upper-half-plane, general-p or maximum-norm setting to that manuscript.

Divol–Lacombe corrected v4, formula (1), separates the matching exponent from the ground norm; the present choice is p=1, q=∞. Definition 2.1 and §3 develop measure transport on the unbounded upper half-plane. Proposition 3.2's proof invokes the finite result of Lacombe–Cuturi–Oudot, Proposition 1 and Supplement §7.1. Their boundary augmentation and assignment argument is the proof pattern used here. Their displayed norm is tied to p; its use here with ground norm ∞ is a library adaptation justified by the explicit cost-matrix argument.

Equality of the finite reservoir optimization with all Borel boundary plans on the closed upper half-plane is proved separately for the canonical atomic measures of unit-mass diagrams (boundaryTransportPowerValue_ofIndexed_unit, boundaryTransportDistance_ofIndexed_unit; see finite weighted boundary transport). That bridge aggregates and splits repeated occurrences and compares arbitrary boundary destinations with the diagonal cost. Divol–Lacombe's formula (20) and Proposition 3.7 use a shortened quotient metric; the raw cost blocks above do not supply an ordinary metric Wasserstein interpretation. Real-exponent powered costs separately reuse this assignment argument for finite p≥1 and take roots after optimization. Their rooted distance laws follow from finite matching composition and Minkowski. Essential bars, noninteger input masses, infinite diagrams, completeness and barycenters remain outside these finite-plan results. Fractional transported mass does not change the unit input mass per occurrence.