Data Assimilation for Sign-indefinite Priors: A generalization of Sinkhorn's algorithm

Anqi Dong, Tryphon T. Georgiou, Allen R. TannenbaumAutomatica 2023 · arXiv · OpenReview

TL;DR

This paper introduces a generalized Sinkhorn algorithm capable of calibrating "sign-indefinite" data arrays to match specified marginals. This extends the classical Sinkhorn algorithm, traditionally used for positive probability distributions, to scenarios where data can be positive or negative, opening up new applications in fields like gene regulatory networks and financial modeling.

What Problem Does This Paper Address?

Many real-world datasets, particularly in areas like gene regulatory networks, financial modeling, or even certain aspects of quantum mechanics, involve relationships that can be both positive (promoting) and negative (suppressing). Traditional data assimilation and optimal transport methods, like the Sinkhorn algorithm, are designed for non-negative probability distributions. This limitation prevents them from directly handling and calibrating datasets with sign-indefinite entries, which are crucial for accurately modeling these complex interactions. The paper addresses this gap by developing a framework to revise sign-indefinite multi-dimensional arrays so that their updated values (the "posterior") are consistent with specified marginals, even when the initial data ("prior") has mixed signs.

Methods

The core contribution is a generalized Sinkhorn algorithm. This algorithm is derived by minimizing a relative entropy-like objective function (specifically, a generalized form of the Kullback-Leibler divergence) between a prior distribution $Q$ and a posterior distribution $P$, subject to matching specified marginals. The key innovation lies in how the algorithm handles the sign-indefinite nature of the prior $Q$.

The derivation involves:

  • Formulating an optimization problem: Minimizing $S(P, Q) = \sum P \log(P/Q) - \sum (P-Q)$ subject to marginal constraints.
  • Introducing sign-dependent scaling: Unlike the standard Sinkhorn algorithm, where scaling factors are applied uniformly, the generalized version applies multiplicative scaling for positive entries of $Q$ and inverse-multiplicative scaling for negative entries. This is achieved by introducing sign-dependent update rules for the scaling parameters.
  • Iterative updates: The algorithm iteratively refines scaling parameters along different coordinate directions until the marginal constraints are met. This process is shown to be a coordinate ascent on a dual functional, inheriting the convergence properties of the standard Sinkhorn algorithm.

Datasets

The paper does not use pre-existing datasets for evaluation. Instead, it introduces synthetic examples to demonstrate the algorithm's functionality:

  • Two-marginal case: A 2D array with entries in $\{0, \pm 1\}$ is used to illustrate the algorithm's ability to match specified positive marginals.
  • Three-marginal cases: Two examples are presented for 3D arrays, one with small dimensions and another with a larger number of entries (2266 positive, 51 negative) to showcase scalability.

These examples serve as benchmarks for the proposed method, visualizing the transformation from a sign-indefinite prior to a consistent posterior.

Key Insights and Ideas

  • Bridging the sign gap: The most significant insight is the successful extension of the Sinkhorn framework to handle sign-indefinite data. This unlocks the potential for applying powerful data assimilation techniques to a much broader range of real-world problems where mixed signs are inherent.
  • Sign-dependent scaling is key: The core algorithmic innovation is the introduction of scaling factors that operate differently based on the sign of the prior entries. This is crucial for ensuring that the posterior distribution respects the underlying relationships (positive or negative) present in the prior.
  • Connection to gene regulatory networks: The paper highlights that sign-indefinite priors naturally arise in modeling gene regulatory networks, where genes can either promote or suppress the expression of others. This provides a strong biological motivation for the developed framework.
  • Generalization of a fundamental algorithm: The work demonstrates that the well-established Sinkhorn algorithm, a workhorse in optimal transport and machine learning, can be generalized while retaining its desirable properties like linear convergence.

Key Results

  • Algorithm 3.1 (Generalized Sinkhorn Algorithm): The paper presents a concrete iterative algorithm that successfully calibrates sign-indefinite priors to match specified positive marginals.
  • Linear Convergence: The generalized Sinkhorn algorithm is shown to converge with a linear convergence rate, similar to its classical counterpart. This is demonstrated through numerical examples (Figure 4), where marginal constraint violation drops rapidly with iterations.
  • Successful Demonstration on Synthetic Data: The algorithm is shown to work effectively on both small and moderately large synthetic examples, producing visually plausible posterior distributions that satisfy the target marginals. For instance, in Example 4.2.2, the algorithm converges within 40 iterations to machine precision.

Limitations and Future Work

  • Complexity of Testing Feasibility: The paper notes that the complexity of testing feasibility for this "signed transport problem" is not yet known, suggesting that the convergence of the algorithm might be the simplest way to assess it.
  • Generalization with Transportation Costs: The authors suggest that a natural extension is to include a "transportation cost" term, which would penalize coupling for combinations of indices. This would lead to a more general optimization problem that can be treated similarly.
  • Applications: While gene regulatory networks and financial modeling are mentioned as motivating applications, further exploration of these and other domains (e.g., quantum mechanics, chemical networks) is implied.
  • Computational Scalability: While the algorithm shows good scalability on a 3D example with over 2000 entries, further investigation into its performance on even larger and higher-dimensional problems might be warranted.

Summary updated

Abstract

The purpose of this work is to develop a framework to calibrate signed datasets so as to be consistent with specified marginals by suitably extending the Schrödinger-Fortet-Sinkhorn paradigm. Specifically, we seek to revise sign-indefinite multi-dimensional arrays in a way that the updated values agree with specified marginals. Our approach follows the rationale in Schrödinger's problem, aimed at updating a "prior" probability measure to agree with marginal distributions. The celebrated Sinkhorn's algorithm (established earlier by R.\ Fortet) that solves Schrödinger's problem found early applications in calibrating contingency tables in statistics and, more recently, multi-marginal problems in machine learning and optimal transport. Herein, we postulate a sign-indefinite prior in the form of a multi-dimensional array, and propose an optimization problem to suitably update this prior to ensure consistency with given marginals. The resulting algorithm generalizes the Sinkhorn algorithm in that it amounts to iterative scaling of the entries of the array along different coordinate directions. The scaling is multiplicative but also, in contrast to Sinkhorn, inverse-multiplicative depending on the sign of the entries. Our algorithm reduces to the classical Sinkhorn algorithm when the entries of the prior are positive.
BibTeX
@article{dong2023data,
  author = {Anqi Dong and Tryphon T. Georgiou and Allen R. Tannenbaum},
  title = {{Data Assimilation for Sign-indefinite Priors: A generalization of Sinkhorn's algorithm}},
  journal = {Automatica},
  year = {2023},
  url = {https://openreview.net/forum?id=KzfT53SBYp},
}
Figure