Symmetric Iterative Proportional Fitting

Sven KurrasAISTATS 2015

Matrix scaling is a fundamental task in data science, used to normalize non-negative matrices to meet specific row and column sum constraints (marginals). While the Iterative Proportional Fitting (IPF) and Sinkhorn-Knopp algorithms are standard solutions, they often struggle with two real-world complexities: symmetry and sparsity. This research, originally presented at AISTATS 2015, provides a mathematically rigorous framework for addressing these challenges, particularly for applications in genomics and optimal transport.

The Problem: Symmetry and Sparsity

In many applications—such as genomics (Hi-C interaction data) or network analysis—the input matrix is inherently symmetric. Standard IPF alternates between row and column scaling, a "zig-zag" approach that breaks symmetry during the optimization process. Even if the input and the final target are symmetric, the intermediate matrices are not.

Furthermore, most classical proofs for IPF assume the input matrix is strictly positive. However, real-world matrices are often sparse. When zeros are present, traditional optimization tools like the Lagrangian approach can break down because the objective function becomes non-smooth. This paper seeks to bridge the gap between theoretical convergence and practical, sparse, symmetric applications.

Proposed Algorithms: PSIPF and SIPF

The author introduces and analyzes three main sequences to solve the symmetric scaling problem:

  1. Traditional IPF: The standard alternating row/column scaling.
  2. Pseudo-Symmetric IPF (PSIPF): A variant that takes an IPF step and then symmetrizes the result using an entry-wise geometric mean.
  3. Symmetric IPF (SIPF): A more direct approach that aggregates row and column projections simultaneously at each step. This ensures every intermediate matrix maintains the form $XWX$ for some diagonal matrix $X$, preserving the "spirit" of the original symmetric matrix throughout the process.

Theoretical Breakthroughs

Local Affinity and Convergence

The core theoretical contribution is a novel convergence proof. Instead of relying on the problematic Lagrangian approach, the author uses Dykstra’s algorithm with Bregman projections. By introducing the concept of "local affinity," the author shows that even though the constraints (fixed marginals) aren't globally linear, they behave linearly enough near the algorithm's path to guarantee convergence to the relative-entropy optimal solution. This elegantly sidesteps the issues caused by zero entries in sparse matrices.

Graph Expansion and Feasibility

The paper links the existence of a scaling solution to the expansion properties of the underlying graph. Specifically, a solution exists if and only if the graph is a "weak f-expander." This provides a precise combinatorial characterization: if a group of nodes is too isolated, the requested marginals simply cannot be satisfied. This is formalized in the paper's characterization of the "non-bipartite decomposition" of the graph.

Key Results and Practical Utility

  • Convergence Guarantee: The paper rigorously proves that both PSIPF and SIPF converge to the same unique, relative-entropy optimal limit as standard IPF in the symmetric setting.
  • Numerical Stability: The "factorized" version of the algorithm (representing the matrix as $XWX$) is shown to be self-stabilizing against numerical errors, making it preferable for practical implementations over recursive scaling.
  • Sparse Optimal Transport: The author suggests that by allowing for zero entries in the cost matrix (representing impossible transport paths), one can compute a "Sparse Earth Mover’s Distance (EMD)" much faster than traditional dense methods, offering a significant win for high-dimensional image analysis.

Limitations and Future Directions

While the paper focuses on the geometric mean (corresponding to relative entropy), it leaves open how sequences using other means (like arithmetic or harmonic) relate to other types of $f$-divergences. Additionally, while the theoretical groundwork for Sparse EMD is laid, the paper does not provide a high-performance software implementation or direct speed benchmarks against state-of-the-art EMD solvers. Characterizing exactly when the limit is "direct" (avoiding entries tending to zero or infinity) also remains a complex task for future research.

Summary updated

BibTeX
@inproceedings{kurras2015symmetric,
  author = {Sven Kurras},
  title = {{Symmetric Iterative Proportional Fitting}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
}
Figure