Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Ornstein-Uhlenbeck Pinball and the Poincaré Inequality in a Punctured Domain Read chapter Read first chapter

2018 | OriginalPaper | Chapter

3. Iterated Proportional Fitting Procedure and Infinite Products of Stochastic Matrices

Authors : J. Brossard, C. Leuridan

Published in: Séminaire de Probabilités XLIX

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The iterative proportional fitting procedure (IPFP), introduced in 1937 by Kruithof, aims to adjust the elements of an array to satisfy specified row and column sums. Thus, given a rectangular non-negative matrix X 0 and two positive marginals a and b, the algorithm generates a sequence of matrices (X n)n≥0 starting at X 0, supposed to converge to a biproportional fitting, that is, to a matrix Y whose marginals are a and b and of the form Y = D 1X 0D 2, for some diagonal matrices D 1 and D 2 with positive diagonal entries.
When a biproportional fitting does exist, it is unique and the sequence (X n)n≥0 converges to it at an at least geometric rate. More generally, when there exists some matrix with marginal a and b and with support included in the support of X 0, the sequence (X n)n≥0 converges to the unique matrix whose marginals are a and b and which can be written as a limit of matrices of the form D 1X 0D 2.
In the opposite case (when there exists no matrix with marginals a and b whose support is included in the support of X 0), the sequence (X n)n≥0 diverges but both subsequences (X 2n)n≥0 and (X 2n+1)n≥0 converge.
In the present paper, we use a new method to prove again these results and determine the two limit-points in the case of divergence. Our proof relies on a new convergence theorem for backward infinite products ⋯M 2M 1 of stochastic matrices M n, with diagonal entries M n(i, i) bounded away from 0 and with bounded ratios M n(j, i)∕M n(i, j). This theorem generalizes Lorenz’ stabilization theorem. We also provide an alternative proof of Touric and Nedić’s theorem on backward infinite products of doubly-stochastic matrices, with diagonal entries bounded away from 0. In both situations, we improve slightly the conclusion, since we establish not only the convergence of the sequence (M n⋯M 1)n≥0, but also its finite variation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Probabilistic Look at Conservative Growth-Fragmentation Equations
next chapter Limiting Eigenvectors of Outliers for Spiked Information-Plus-Noise Type Matrices
Footnotes
1
Namely \(\displaystyle {\sum _{i=1}^d U^\uparrow (d+1-i)V^\uparrow (i) \le \sum _{i=1}^d U(i)V(i) \le \sum _{i=1}^d U^\uparrow (i)V^\uparrow (i)}\) for every U and V in R d.
 
Literature
1.
E. Aas, Limit points of the iterative scaling procedure. Ann. Oper. Res. 215(1), 15–23 (2014)
2.
M. Bacharach, Estimating nonnegative matrices from marginal data. Int. Econ. Rev. 6(3), 294–310 (1965)
3.
L.M. Bregman, Proof of the convergence of Sheleikhovskii’s method for a problem with transportation constraints. USSR Comput. Math. Math. Phys. 7(1), 191–204 (1967)
4.
J.B. Brown, P.J. Chase, A.O. Pittenger, Order independence and factor convergence in iterative scaling. Linear Algebra Appl. 190, 1–39 (1993)
5.
I. Csiszár, I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3(1), 146–158 (1975)
6.
S. Fienberg, An iterative procedure for estimation in contingency tables. Ann. Math. Stat. 41(3), 907–917 (1970)
7.
C. Gietl, F. Reffel, Accumulation points of the iterative scaling procedure. Metrika 73(1), 783–798 (2013)
8.
C.T. Ireland, S. Kullback, Contingency tables with given marginals. Biometrika 55(1), 179–188 (1968)
9.
10.
J. Lorenz, A stabilization theorem for dynamics of continuous opinions. Phys. A Stat. Mech. Appl. 355(1), 217–223 (2005)
11.
O. Pretzel, Convergence of the iterative scaling procedure for non-negative matrices. J. Lond. Math. Soc. 21, 379–384 (1980)
12.
F. Pukelsheim, Biproportional matrix scaling and the iterative proportional fitting procedure. Ann. Oper. Res. 215, 269–283 (2014)
13.
R. Sinkhorn, Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Mon. 74(4), 402–405 (1967)
14.
B. Touri, Product of random stochastic matrices and distributed averaging. Springer Thesis (2012)
15.
B. Touri, A. Nedic, Alternative characterization of ergodicity for doubly stochastic chains, in Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), Orlando, FL (2011), pp. 5371–5376
16.
B. Touri, A. Nedić, On ergodicity, infinite flow and consensus in random models. IEEE Trans. Autom. Control 56(7), 1593–1605 (2011)MathSciNetCrossRef
17.
18.
R. Webster, Convexity (Oxford University Press, Oxford, 1994)MATH
Metadata
Title
Iterated Proportional Fitting Procedure and Infinite Products of Stochastic Matrices
Authors
J. Brossard
C. Leuridan
Copyright Year
2018
Book
Séminaire de Probabilités XLIX

Print ISBN: 978-3-319-92419-9

Electronic ISBN: 978-3-319-92420-5

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-92420-5_3