Symmetric Iterative Proportional Fitting
Abstract
Iterative Proportional Fitting (IPF) generates from an input matrix W a sequence of matrices that converges, under certain conditions, to a specific limit matrix W*. This limit is the relative-entropy nearest solution to W among all matrices of prescribed row marginals r and column marginals c. We prove this known fact by a novel strategy that contributes a pure algorithmic intuition. Then we focus on the symmetric setting: W=W’ and r=c. Since IPF inherently generates non-symmetric matrices, we introduce two symmetrized variants of IPF. We prove convergence for both of them. Further, we give a novel characterization for the existence of W* in terms of expansion properties of the undirected weighted graph represented by W. Finally, we show how our results contribute to recent work in machine learning.
BibTeX
@InProceedings{pmlr-v38-kurras15,
title = {{Symmetric Iterative Proportional Fitting}},
author = {Kurras, Sven},
booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics},
pages = {526--534},
year = {2015},
editor = {Lebanon, Guy and Vishwanathan, S. V. N.},
volume = {38},
series = {Proceedings of Machine Learning Research},
address = {San Diego, California, USA},
month = {09--12 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v38/kurras15.pdf},
url = {https://proceedings.mlr.press/v38/kurras15.html},
abstract = {Iterative Proportional Fitting (IPF) generates from an input matrix W a sequence of matrices that converges, under certain conditions, to a specific limit matrix W*. This limit is the relative-entropy nearest solution to W among all matrices of prescribed row marginals r and column marginals c. We prove this known fact by a novel strategy that contributes a pure algorithmic intuition. Then we focus on the symmetric setting: W=W’ and r=c. Since IPF inherently generates non-symmetric matrices, we introduce two symmetrized variants of IPF. We prove convergence for both of them. Further, we give a novel characterization for the existence of W* in terms of expansion properties of the undirected weighted graph represented by W. Finally, we show how our results contribute to recent work in machine learning.}
}