Résumé

Continuity of f-projections on discrete spaces

Métriques

655
156
636.72 Ko
 application/pdf
bitcache://1eeca9b36ac4390e347ea578786302a5a692c7b6

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/5103</identifier><creators><creator><creatorName>Christoph Gietl</creatorName></creator><creator><creatorName>Fabian Reffel</creatorName></creator></creators><titles>
            <title>Continuity of f-projections on discrete spaces</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Fri 11 Oct 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 25 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">1eeca9b36ac4390e347ea578786302a5a692c7b6</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9913</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Continuity of f-projections on discrete spaces Christoph Gietl Fabian Reffel Universit¨at Augsburg Geometric Science of Information 2013 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 1 / 25 Motivation and outline Motivation Motivation Common problem in statistics: Given a set of vectors M, find the element s ∈ M closest to a given vector t with respect to some “distance functional”. → “projection problem” C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 2 / 25 Motivation and outline Motivation Motivation Common problem in statistics: Given a set of vectors M, find the element s ∈ M closest to a given vector t with respect to some “distance functional”. → “projection problem” Difficulty: The given vector t may be an observation and contain errors. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 2 / 25 Motivation and outline Motivation Motivation Common problem in statistics: Given a set of vectors M, find the element s ∈ M closest to a given vector t with respect to some “distance functional”. → “projection problem” Difficulty: The given vector t may be an observation and contain errors. Question: Does the projection continuously depend on the given vector t? C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 2 / 25 Motivation and outline Motivation Motivation Common problem in statistics: Given a set of vectors M, find the element s ∈ M closest to a given vector t with respect to some “distance functional”. → “projection problem” Difficulty: The given vector t may be an observation and contain errors. Question: Does the projection continuously depend on the given vector t? Agenda: Many popular “distance functionals” belong to the family of f-divergences. Define f-projection as the minimization of f-divergence. Examine the continuity of f-projections. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 2 / 25 Motivation and outline Outline Outline 1 Continuity and convexity of f-divergence 2 Continuity of f-projections 3 Application to the IPF procedure 4 Conclusion and perspectives C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 3 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 4 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. Step 1: Define f : [0; ∞)2 → R ∪ {∞} by f(v, w) =    w · f ( v w ) v ≥ 0, w > 0, v · limx→∞ f (x) x v > 0, w = 0, 0 v = 0, w = 0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 4 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. Step 1: Define f : [0; ∞)2 → R ∪ {∞} by f(v, w) =    w · f ( v w ) v ≥ 0, w > 0, v · limx→∞ f (x) x v > 0, w = 0, 0 v = 0, w = 0. Properties: (i) (v, w) → f(v, w) is lower semicontinuous. (ii) For fixed v ≥ 0, w → f(v, w) is continuous. (iii) For fixed w > 0, v → f(v, w) is strictly convex ⇔ f is strictly convex. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 4 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. Step 2: Define Df : Rk ≥0 × Rk ≥0 → R ∪ {∞} by Df (s | t) := k i=1 f(si , ti ). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 5 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. Step 2: Define Df : Rk ≥0 × Rk ≥0 → R ∪ {∞} by Df (s | t) := k i=1 f(si , ti ). Remarks: If limx→∞ f (x) x < ∞, then Df (s | t) < ∞. If limx→∞ f (x) x = ∞, then Df (s | t) < ∞ ⇔ s ≪ t. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 5 / 25 Continuity and convexity of f-divergence Definition: f-divergence Definition: f-divergence (Csisz´ar 1963, Ali/Silvey 1966) Idea: Given a convex and continuous function f : [0; ∞) → R, define the f-divergence Df : Rk ≥0 × Rk ≥0 → R ∪ {∞}. Step 2: Define Df : Rk ≥0 × Rk ≥0 → R ∪ {∞} by Df (s | t) := k i=1 f(si , ti ). Remarks: If limx→∞ f (x) x < ∞, then Df (s | t) < ∞. If limx→∞ f (x) x = ∞, then Df (s | t) < ∞ ⇔ s ≪ t. f-divergences are defined for probability measures in the pertinent literature (cf. Liese/Vajda 1987). The vectors s and t can be interpreted as finite measures. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 5 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. f is strictly convex and continuous. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. f is strictly convex and continuous. limx→∞ f (x) x = ∞. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. f is strictly convex and continuous. limx→∞ f (x) x = ∞. f(v, w) =    w · f ( v w ) v ≥ 0, w > 0, v · limx→∞ f (x) x v > 0, w = 0, 0 v = 0, w = 0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. f is strictly convex and continuous. limx→∞ f (x) x = ∞. f(v, w) =    v log v w v ≥ 0, w > 0, ∞ v > 0, w = 0, 0 v = 0, w = 0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: I-divergence (Kullback/Leibler 1951) Choose f (x) = x log x. f is strictly convex and continuous. limx→∞ f (x) x = ∞. f(v, w) =    v log v w v ≥ 0, w > 0, ∞ v > 0, w = 0, 0 v = 0, w = 0. Df (s | t) = I (s | t) = i si log si ti < ∞ s ≪ t, ∞ s ≪ t. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 6 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: χ2 -divergence Choose f (x) = (x − 1)2. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 7 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: χ2 -divergence Choose f (x) = (x − 1)2. f is strictly convex and continuous. limx→∞ f (x) x = ∞. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 7 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: χ2 -divergence Choose f (x) = (x − 1)2. f is strictly convex and continuous. limx→∞ f (x) x = ∞. Df (s | t) = χ2 (s | t) = i (si −ti )2 ti < ∞ s ≪ t, ∞ s ≪ t. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 7 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: Total variation distance Choose f (x) = |x − 1|. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 8 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: Total variation distance Choose f (x) = |x − 1|. f is convex and continuous but not strictly convex. limx→∞ f (x) x = 1. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 8 / 25 Continuity and convexity of f-divergence Definition: f-divergence Example: Total variation distance Choose f (x) = |x − 1|. f is convex and continuous but not strictly convex. limx→∞ f (x) x = 1. Df (s | t) = i |si − ti | = s − t 1 < ∞. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 8 / 25 Continuity and convexity of f-divergence Continuity and convexity Continuity and convexity of f-divergence Theorem (Continuity and convexity of f-divergence) (i) (s, t) → Df (s | t) is lower semicontinuous. (ii) For fixed s ∈ Rk ≥0, t → Df (s | t) is continuous. (iii) For fixed t ∈ Rk ≥0, s → Df (s | t) is strictly convex for all s ≪ t ⇔ f is strictly convex. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 9 / 25 Continuity and convexity of f-divergence Continuity and convexity Continuity and convexity of f-divergence Theorem (Continuity and convexity of f-divergence) (i) (s, t) → Df (s | t) is lower semicontinuous. (ii) For fixed s ∈ Rk ≥0, t → Df (s | t) is continuous. (iii) For fixed t ∈ Rk ≥0, s → Df (s | t) is strictly convex for all s ≪ t ⇔ f is strictly convex. Proof: (i), (ii) and (iii) follow from the properties of f. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 9 / 25 Continuity and convexity of f-divergence Continuity and convexity Continuity and convexity of f-divergence Theorem (Continuity and convexity of f-divergence) (i) (s, t) → Df (s | t) is lower semicontinuous. (ii) For fixed s ∈ Rk ≥0, t → Df (s | t) is continuous. (iii) For fixed t ∈ Rk ≥0, s → Df (s | t) is strictly convex for all s ≪ t ⇔ f is strictly convex. Proof: (i), (ii) and (iii) follow from the properties of f. Remarks: (i) and (iii) can be found in Liese/Vajda (1987). (ii) is the crucial property for continuity of f-projections. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 9 / 25 Continuity and convexity of f-divergence Continuity and convexity Examples: Continuity and convexity of f-divergence I-divergence and χ2-divergence are lower semicontinuous, continuous in the second argument and strictly convex in the first argument. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 10 / 25 Continuity and convexity of f-divergence Continuity and convexity Examples: Continuity and convexity of f-divergence I-divergence and χ2-divergence are lower semicontinuous, continuous in the second argument and strictly convex in the first argument. Total variation distance Df (s | t) = s − t 1 is continuous and convex but not strictly convex. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 10 / 25 Continuity and convexity of f-divergence Continuity and convexity Examples: Continuity and convexity of f-divergence I-divergence and χ2-divergence are lower semicontinuous, continuous in the second argument and strictly convex in the first argument. Total variation distance Df (s | t) = s − t 1 is continuous and convex but not strictly convex. For example, choose s(α) := (1 − α, α)′ and t := (1, 1)′. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 10 / 25 Continuity and convexity of f-divergence Continuity and convexity Examples: Continuity and convexity of f-divergence I-divergence and χ2-divergence are lower semicontinuous, continuous in the second argument and strictly convex in the first argument. Total variation distance Df (s | t) = s − t 1 is continuous and convex but not strictly convex. For example, choose s(α) := (1 − α, α)′ and t := (1, 1)′. Then ∀α ∈ [0; 1] : Df s(α) t = |(1 − α) − 1| + |α − 1| = 1. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 10 / 25 Continuity and convexity of f-divergence Continuity and convexity Examples: Continuity and convexity of f-divergence I-divergence and χ2-divergence are lower semicontinuous, continuous in the second argument and strictly convex in the first argument. Total variation distance Df (s | t) = s − t 1 is continuous and convex but not strictly convex. For example, choose s(α) := (1 − α, α)′ and t := (1, 1)′. Then ∀α ∈ [0; 1] : Df s(α) t = |(1 − α) − 1| + |α − 1| = 1. Hence, ∀α ∈ [0; 1] : Df s(α) t = (1 − α) Df s(0) t + α Df s(1) t . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 10 / 25 Continuity of f-projections Definition: f-projection Definition: f-projection Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then s∗ ∈ M is an f-projection of t on M when Df (s∗ | t) = inf s∈M Df (s | t) . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 11 / 25 Continuity of f-projections Definition: f-projection Definition: f-projection Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then s∗ ∈ M is an f-projection of t on M when Df (s∗ | t) = inf s∈M Df (s | t) . Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 11 / 25 Continuity of f-projections Definition: f-projection Definition: f-projection Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then s∗ ∈ M is an f-projection of t on M when Df (s∗ | t) = inf s∈M Df (s | t) . Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 11 / 25 Continuity of f-projections Definition: f-projection Definition: f-projection Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then s∗ ∈ M is an f-projection of t on M when Df (s∗ | t) = inf s∈M Df (s | t) . Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 11 / 25 Continuity of f-projections Definition: f-projection Definition: f-projection Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then s∗ ∈ M is an f-projection of t on M when Df (s∗ | t) = inf s∈M Df (s | t) . Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 11 / 25 Continuity of f-projections Definition: f-projection Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 12 / 25 Continuity of f-projections Definition: f-projection Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 χ2-divergence: χ2 s(α) t = (α−1)2 1 + ((2−α)− 1 2 )2 1 2 + ((1−α)−1)2 1 + (α−1)2 1 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 12 / 25 Continuity of f-projections Definition: f-projection Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 χ2-divergence: χ2 s(α) t = 2 α − 1 2 + 2 α − 3 2 2 + α2 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 12 / 25 Continuity of f-projections Definition: f-projection Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 χ2-divergence: χ2 s(α) t = 2 α − 1 2 + 2 α − 3 2 2 + α2 Unique minimizer: α∗ = 1 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 12 / 25 Continuity of f-projections Definition: f-projection Example: Choose M := α 2 − α 1 − α α α ∈ [0; 1] and t := 1 1 2 1 1 . I-divergence: I s(α) t = 2 · α log α 1 + (2 − α) log 2−α 1 2 + (1 − α) log 1−α 1 Unique minimizer: α∗ = 3 − √ 5 ≈ 0.764 Unique I-projection: s∗ = 3 − √ 5 √ 5 − 1√ 5 − 2 3 − √ 5 χ2-divergence: χ2 s(α) t = 2 α − 1 2 + 2 α − 3 2 2 + α2 Unique minimizer: α∗ = 1 Unique χ2-projection: s∗ = 1 1 0 1 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 12 / 25 Continuity of f-projections Existence and uniqueness Example: Non-unique f-projections Let Df denote total variation distance and choose M := (1 − α, α)′ α ∈ [0; 1] and t = (1, 1)′ . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 13 / 25 Continuity of f-projections Existence and uniqueness Example: Non-unique f-projections Let Df denote total variation distance and choose M := (1 − α, α)′ α ∈ [0; 1] and t = (1, 1)′ . Then ∀s(α) ∈ M : Df s(α) t = |(1 − α) − 1| + |α − 1| = 1. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 13 / 25 Continuity of f-projections Existence and uniqueness Example: Non-unique f-projections Let Df denote total variation distance and choose M := (1 − α, α)′ α ∈ [0; 1] and t = (1, 1)′ . Then ∀s(α) ∈ M : Df s(α) t = |(1 − α) − 1| + |α − 1| = 1. Hence, all s(α) ∈ M are f-projections of t on M. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 13 / 25 Continuity of f-projections Existence and uniqueness Example: Non-unique f-projections Let Df denote total variation distance and choose M := (1 − α, α)′ α ∈ [0; 1] and t = (1, 1)′ . Then ∀s(α) ∈ M : Df s(α) t = |(1 − α) − 1| + |α − 1| = 1. Hence, all s(α) ∈ M are f-projections of t on M. Reason: We cannot expect uniqueness of f-projection if f is not strictly convex. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 13 / 25 Continuity of f-projections Existence and uniqueness Lemma (Existence and uniqueness of f-projections) Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then: (i) There exists an f-projection of t on M. (ii) If f is strictly convex and ∀s ∈ M : s ≪ t, then the f-projection of t on M is unique. (iii) If f is strictly convex and ∃s ∈ M : s ≪ t and limx→∞ f (x)/x = ∞, then the f-projection of t on M is unique. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 14 / 25 Continuity of f-projections Existence and uniqueness Lemma (Existence and uniqueness of f-projections) Let M ⊆ Rk ≥0 be a compact and convex set and let t ∈ Rk ≥0. Then: (i) There exists an f-projection of t on M. (ii) If f is strictly convex and ∀s ∈ M : s ≪ t, then the f-projection of t on M is unique. (iii) If f is strictly convex and ∃s ∈ M : s ≪ t and limx→∞ f (x)/x = ∞, then the f-projection of t on M is unique. Proof: (i) follows from lower semicontinuity of s → Df (s | t) and compactness of M. (ii) and (iii) follow from the convexity properties of s → Df (s | t) and convexity of M. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 14 / 25 Continuity of f-projections Continuity Theorem (Continuity of f-projections) Let Df be defined by a strictly convex function f , M ⊆ Rk ≥0 be a compact and convex set and (tn) ⊂ Rk ≥0 be a sequence converging to some t ∈ Rk ≥0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 15 / 25 Continuity of f-projections Continuity Theorem (Continuity of f-projections) Let Df be defined by a strictly convex function f , M ⊆ Rk ≥0 be a compact and convex set and (tn) ⊂ Rk ≥0 be a sequence converging to some t ∈ Rk ≥0. Then: (i) If ∀s ∈ M : s ≪ t, then—for n large enough—the f-projection s∗ of t on M and the f-projection sn,∗ of tn on M exist and are unique. (ii) If ∃s ∈ M : s ≪ t and limx→∞ f (x)/x = ∞, then—for n large enough—the f-projection s∗ of t on M and the f-projection sn,∗ of tn on M exist and are unique. (iii) Under the conditions of (i) or (ii), sn,∗ n→∞ −→ s∗ . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 15 / 25 Continuity of f-projections Continuity Continuity of f-projections Proof: (i) and (ii) follow from the previous Lemma. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 16 / 25 Continuity of f-projections Continuity Continuity of f-projections Proof: (i) and (ii) follow from the previous Lemma. (iii) Let s∗∗ := limn→∞(sηn,∗) ∈ M be an arbitrary acc. point of (sn,∗). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 16 / 25 Continuity of f-projections Continuity Continuity of f-projections Proof: (i) and (ii) follow from the previous Lemma. (iii) Let s∗∗ := limn→∞(sηn,∗) ∈ M be an arbitrary acc. point of (sn,∗). We then have Df (s∗∗ | t) = Df lim n→∞ sηn,∗ lim n→∞ tηn by definition of s∗∗ and t ≤ lim inf n→∞ Df (sηn,∗ | tηn ) by lower semicont. of Df (· | ·) ≤ lim inf n→∞ Df (s∗ | tηn ) by sηn,∗ being f-projection of tηn = Df (s∗ | t) by continuity of Df (s∗ | ·). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 16 / 25 Continuity of f-projections Continuity Continuity of f-projections Proof: (i) and (ii) follow from the previous Lemma. (iii) Let s∗∗ := limn→∞(sηn,∗) ∈ M be an arbitrary acc. point of (sn,∗). We then have Df (s∗∗ | t) = Df lim n→∞ sηn,∗ lim n→∞ tηn by definition of s∗∗ and t ≤ lim inf n→∞ Df (sηn,∗ | tηn ) by lower semicont. of Df (· | ·) ≤ lim inf n→∞ Df (s∗ | tηn ) by sηn,∗ being f-projection of tηn = Df (s∗ | t) by continuity of Df (s∗ | ·). Since s∗ is the unique f-projection of t on M, we conclude s∗∗ = s∗. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 16 / 25 Continuity of f-projections Continuity Continuity of f-projections Proof: (i) and (ii) follow from the previous Lemma. (iii) Let s∗∗ := limn→∞(sηn,∗) ∈ M be an arbitrary acc. point of (sn,∗). We then have Df (s∗∗ | t) = Df lim n→∞ sηn,∗ lim n→∞ tηn by definition of s∗∗ and t ≤ lim inf n→∞ Df (sηn,∗ | tηn ) by lower semicont. of Df (· | ·) ≤ lim inf n→∞ Df (s∗ | tηn ) by sηn,∗ being f-projection of tηn = Df (s∗ | t) by continuity of Df (s∗ | ·). Since s∗ is the unique f-projection of t on M, we conclude s∗∗ = s∗. Thus, all acc. points of (sn,∗) coincide with s∗ and (sn,∗) converges to s∗. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 16 / 25 Application to the IPF procedure Outline 1 Continuity and convexity of f-divergence 2 Continuity of f-projections 3 Application to the IPF procedure 4 Conclusion and perspectives C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 17 / 25 Application to the IPF procedure Setting: IPF procedure Setting: IPF procedure Given: Initial matrix A = (aij ) ∈ Rk×ℓ ≥0 , ∀i : ai+ > 0, ∀j : a+j > 0. Column marginals c = (cj ) ∈ Rℓ >0. Row marginals r = (ri ) ∈ Rk >0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 18 / 25 Application to the IPF procedure Setting: IPF procedure Setting: IPF procedure Given: Initial matrix A = (aij ) ∈ Rk×ℓ ≥0 , ∀i : ai+ > 0, ∀j : a+j > 0. Column marginals c = (cj ) ∈ Rℓ >0. Row marginals r = (ri ) ∈ Rk >0. Sets of matrices with fitted marginals: C := C = (cij ) ∈ Rk×ℓ ≥0 ∀j : c+j = cj . R := R = (rij ) ∈ Rk×ℓ ≥0 ∀i : ri+ = ri . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 18 / 25 Application to the IPF procedure Setting: IPF procedure Setting: IPF procedure Given: Initial matrix A = (aij ) ∈ Rk×ℓ ≥0 , ∀i : ai+ > 0, ∀j : a+j > 0. Column marginals c = (cj ) ∈ Rℓ >0. Row marginals r = (ri ) ∈ Rk >0. Sets of matrices with fitted marginals: C := C = (cij ) ∈ Rk×ℓ ≥0 ∀j : c+j = cj . R := R = (rij ) ∈ Rk×ℓ ≥0 ∀i : ri+ = ri . Aim: Find a matrix B ∈ Rk×ℓ ≥0 that has the marginals c and r, B ∈ C ∩ R, and is ”proportional” to matrix A. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 18 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: Odd steps t + 1 fit row sums to row marginals, aij(t + 1) := ri ai+(t) aij (t) for all entries (i, j). Even steps t + 2 fit column sums to column marginals, aij (t + 2) := cj a+j (t + 1) aij (t + 1) for all entries (i, j). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: Odd steps t + 1 fit row sums to row marginals, aij(t + 1) := ri ai+(t) aij (t) for all entries (i, j). Even steps t + 2 fit column sums to column marginals, aij (t + 2) := cj a+j (t + 1) aij (t + 1) for all entries (i, j). The sequence (A(0), A(1), A(2), A(3), A(4), . . .) is called the IPF sequence. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: Odd steps t + 1 fit row sums to row marginals, aij(t + 1) := ri ai+(t) aij (t) for all entries (i, j). Even steps t + 2 fit column sums to column marginals, aij (t + 2) := cj a+j (t + 1) aij (t + 1) for all entries (i, j). The sequence (A(0), A(1), A(2), A(3), A(4), . . .) is called the IPF sequence. Purpose: If the IPF sequence converges, the limit matrix has desired column and row sums C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: Odd steps t + 1 fit row sums to row marginals, aij(t + 1) := ri ai+(t) aij (t) for all entries (i, j). Even steps t + 2 fit column sums to column marginals, aij (t + 2) := cj a+j (t + 1) aij (t + 1) for all entries (i, j). The sequence (A(0), A(1), A(2), A(3), A(4), . . .) is called the IPF sequence. Purpose: If the IPF sequence converges, the limit matrix has desired column and row sums and ”preserves the proportions”, C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure IPF procedure IPF procedure The IPF procedure (iterative proportional fitting procedure) is defined by the following two steps: Odd steps t + 1 fit row sums to row marginals, aij(t + 1) := ri ai+(t) aij (t) for all entries (i, j). Even steps t + 2 fit column sums to column marginals, aij (t + 2) := cj a+j (t + 1) aij (t + 1) for all entries (i, j). The sequence (A(0), A(1), A(2), A(3), A(4), . . .) is called the IPF sequence. Purpose: If the IPF sequence converges, the limit matrix has desired column and row sums and ”preserves the proportions”, i.e. only scaling of rows and columns are allowed. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 19 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: ai+ A = (aij ) =     5 9 12 5     31 0 6 17 4 27 0 0 13 18 31 0 0 0 11 11 a+j 5 15 42 38 100 Bus route: 1 2 3 4 5 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: ai+ A = (aij ) =     5 9 12 5     31 0 6 17 4 27 0 0 13 18 31 0 0 0 11 11 a+j 5 15 42 38 100 a11 = 5: passengers traveling from station 1 to station 2 a23 = 17: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: ai+ ri A = (aij ) =     5 9 12 5     31 36 0 6 17 4 27 21 0 0 13 18 31 42 0 0 0 11 11 15 a+j 5 15 42 38 100 cj 14 38 21 41 a11 = 5: passengers traveling from station 1 to station 2 a23 = 17: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 0 ai+ ri A = (aij ) =     5 9 12 5     31 36 · 36 31 0 6 17 4 27 21 · 21 27 0 0 13 18 31 42 · 42 31 0 0 0 11 11 15 · 15 11 a+j 5 15 42 38 100 cj 14 38 21 41 a11 = 5: passengers traveling from station 1 to station 2 a23 = 17: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 1 ai+(1) ri A(1) =     5.81 10.45 13.94 5.81     36 36 0 4.67 13.22 3.11 21 21 0 0 17.61 24.39 42 42 0 0 0 15 15 15 a+j (1) 5.81 15.12 44.77 48.30 114 cj 14 38 21 41 a11 = 5.81: passengers traveling from station 1 to station 2 a23 = 17.61: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 1 ai+(1) ri A(1) =     5.81 10.45 13.94 5.81     36 36 0 4.67 13.22 3.11 21 21 0 0 17.61 24.39 42 42 0 0 0 15 15 15 a+j (1) 5.81 15.12 44.77 48.30 114 cj 14 38 21 41 · 14 5.81 · 38 15.12 · 21 44.77 · 41 48.30 a11 = 5.81: passengers traveling from station 1 to station 2 a23 = 17.61: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 2 ai+(2) ri A(2) =     14 26.27 6.54 4.93     51.74 36 0 11.73 6.20 2.64 20.57 21 0 0 8.26 20.70 28.96 42 0 0 0 12.73 12.73 15 a+j (2) 14 38 21 41 114 cj 14 38 21 41 a11 = 14: passengers travelling from station 1 to station 2 a23 = 6.20: passengers travelling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 2 ai+(2) ri A(2) =     14 26.27 6.54 4.93     51.74 36 · 36 51.74 0 11.73 6.20 2.64 20.57 21 · 21 20.57 0 0 8.26 20.70 28.96 42 · 42 28.96 0 0 0 12.73 12.73 15 · 15 12.73 a+j (2) 14 38 21 41 114 cj 14 38 21 41 a11 = 14: passengers travelling from station 1 to station 2 a23 = 6.20: passengers travelling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 3 ai+(3) ri A(3) =     9.74 18.28 4.55 3.43     36 36 0 11.97 6.33 2.70 21 21 0 0 11.98 30.02 42 42 0 0 0 15 15 15 a+j (3) 9.74 30.25 22.86 51.14 114 cj 14 38 21 41 a11 = 9.74: passengers traveling from station 1 to station 2 a23 = 6.33: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 3 ai+(3) ri A(3) =     9.74 18.28 4.55 3.43     36 36 0 11.97 6.33 2.70 21 21 0 0 11.98 30.02 42 42 0 0 0 15 15 15 a+j (3) 9.74 30.25 22.86 51.14 114 cj 14 38 21 41 · 14 9.742 · 38 30.25 · 21 22.86 · 41 51.14 a11 = 9.74: passengers traveling from station 1 to station 2 a23 = 6.33: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Example: IPF procedure Example (inspired by McCord et al 2010) IPF procedure: Step 46 ai+(46) ri A(46) =     14 20.11 1.32 0.57     36.00 36 0 17.89 2.50 0.61 21.00 21 0 0 17.18 24.81 42.00 42 0 0 0 15.00 15.00 15 a+j(46) 14 38 21 41 114 cj 14 38 21 41 a11 = 14: passengers traveling from station 1 to station 2 a23 = 2.50: passengers traveling from station 2 to station 4 C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 20 / 25 Application to the IPF procedure Convergence and characterization Convergence and characterization Theorem (Accumulation points of the IPF sequence, G./R. 2013) 1 The even step IPF subsequence (A(t))t=0,2,4,... converges. 2 The odd step IPF subsequence (A(t + 1))t=0,2,4,... converges. The IPF sequence (A(t))t=0,1,2,3,4,... has at most two accumulation points. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 21 / 25 Application to the IPF procedure Convergence and characterization Convergence and characterization Theorem (Accumulation points of the IPF sequence, G./R. 2013) 1 The even step IPF subsequence (A(t))t=0,2,4,... converges. 2 The odd step IPF subsequence (A(t + 1))t=0,2,4,... converges. The IPF sequence (A(t))t=0,1,2,3,4,... has at most two accumulation points. Theorem (Convergence the IPF sequence, Csisz´ar 1975) The IPF sequence (A(t)) converges if and only if C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 21 / 25 Application to the IPF procedure Convergence and characterization Convergence and characterization Theorem (Accumulation points of the IPF sequence, G./R. 2013) 1 The even step IPF subsequence (A(t))t=0,2,4,... converges. 2 The odd step IPF subsequence (A(t + 1))t=0,2,4,... converges. The IPF sequence (A(t))t=0,1,2,3,4,... has at most two accumulation points. Theorem (Convergence the IPF sequence, Csisz´ar 1975) The IPF sequence (A(t)) converges if and only if C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅. Then, the limit matrix is the I-projection of A on the set C ∩ R, i.e., lim t→∞ A(t) = argminB∈C∩R I (B | A) . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 21 / 25 Application to the IPF procedure Continuous dependence Continuous dependence Difficulty: Initial matrix A based on observations. These observations may vary or have errors. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 22 / 25 Application to the IPF procedure Continuous dependence Continuous dependence Difficulty: Initial matrix A based on observations. These observations may vary or have errors. Question: Does the limit matrix continuously depend on the initial matrix A? C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 22 / 25 Application to the IPF procedure Continuous dependence Continuous dependence Difficulty: Initial matrix A based on observations. These observations may vary or have errors. Question: Does the limit matrix continuously depend on the initial matrix A? Answer: Theorem (Continuous dependence, G./R. 2013) Let (An) be a sequence of input matrices with An n→∞ −→ A. Let B∗ be the limit matrix of the IPF procedure applied to (A, c, r). Let (An(t))t∈N0 be the IPF sequence corresponding to (An, c, r). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 22 / 25 Application to the IPF procedure Continuous dependence Continuous dependence Difficulty: Initial matrix A based on observations. These observations may vary or have errors. Question: Does the limit matrix continuously depend on the initial matrix A? Answer: Theorem (Continuous dependence, G./R. 2013) Let (An) be a sequence of input matrices with An n→∞ −→ A. Let B∗ be the limit matrix of the IPF procedure applied to (A, c, r). Let (An(t))t∈N0 be the IPF sequence corresponding to (An, c, r). Then: 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 22 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . Proof: 1 As An n→∞ −→ A, we have A ≪ An for n large enough. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . Proof: 1 As An n→∞ −→ A, we have A ≪ An for n large enough. Hence C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ An ⊇ C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅ and the sequence (An(t))t∈N0 converges by Csisz´ar’s Theorem. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . Proof: 1 As An n→∞ −→ A, we have A ≪ An for n large enough. Hence C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ An ⊇ C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅ and the sequence (An(t))t∈N0 converges by Csisz´ar’s Theorem. 2 By assumption it holds C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . Proof: 1 As An n→∞ −→ A, we have A ≪ An for n large enough. Hence C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ An ⊇ C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅ and the sequence (An(t))t∈N0 converges by Csisz´ar’s Theorem. 2 By assumption it holds C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅. For I-divergence it holds limx→∞ f (x)/x = ∞. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Continuous dependence Continuous dependence - Proof Theorem (Continuous dependence, G./R. 2013) 1 For n large enough, the IPF sequence (An(t))t∈N0 converges to some limit matrix Bn,∗. 2 The limit matrix Bn,∗ converges to B∗, Bn,∗ n→∞ −→ B∗ . Proof: 1 As An n→∞ −→ A, we have A ≪ An for n large enough. Hence C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ An ⊇ C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅ and the sequence (An(t))t∈N0 converges by Csisz´ar’s Theorem. 2 By assumption it holds C ∩ R ∩ B ∈ Rk×ℓ ≥0 B ≪ A = ∅. For I-divergence it holds limx→∞ f (x)/x = ∞. Hence Theorem ”Continuity of f-projections” is applicable. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 23 / 25 Application to the IPF procedure Example: Continuous dependence Example Let An = 1 n−1 1 1 for all n ∈ R>0, c = (1, 2) and r = (2, 1). C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 24 / 25 Application to the IPF procedure Example: Continuous dependence Example Let An = 1 n−1 1 1 for all n ∈ R>0, c = (1, 2) and r = (2, 1). It holds Bn,∗ = 2 − bn bn bn − 1 2 − bn , where bn = n − 4 + √ n2 + 8n 2(n − 1) . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 24 / 25 Application to the IPF procedure Example: Continuous dependence Example Let An = 1 n−1 1 1 for all n ∈ R>0, c = (1, 2) and r = (2, 1). It holds Bn,∗ = 2 − bn bn bn − 1 2 − bn , where bn = n − 4 + √ n2 + 8n 2(n − 1) . It holds bn n→∞ −→ 1 and therefore Bn,∗ n→∞ −→ 1 1 0 1 . C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 24 / 25 Application to the IPF procedure Example: Continuous dependence Example Let An = 1 n−1 1 1 for all n ∈ R>0, c = (1, 2) and r = (2, 1). It holds Bn,∗ = 2 − bn bn bn − 1 2 − bn , where bn = n − 4 + √ n2 + 8n 2(n − 1) . It holds bn n→∞ −→ 1 and therefore Bn,∗ n→∞ −→ 1 1 0 1 . Applying the IPF procedure to (limn→∞ An, c, r) yields C∗ = 1 0 0 2 and R∗ = 2 0 0 1 , C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 24 / 25 Application to the IPF procedure Example: Continuous dependence Example Let An = 1 n−1 1 1 for all n ∈ R>0, c = (1, 2) and r = (2, 1). It holds Bn,∗ = 2 − bn bn bn − 1 2 − bn , where bn = n − 4 + √ n2 + 8n 2(n − 1) . It holds bn n→∞ −→ 1 and therefore Bn,∗ n→∞ −→ 1 1 0 1 . Applying the IPF procedure to (limn→∞ An, c, r) yields C∗ = 1 0 0 2 and R∗ = 2 0 0 1 , since r2/a2+(t) ≤ 1/2 and c1/a+1(t + 1) ≤ 1/2 for all even t ≥ 0. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 24 / 25 Conclusion and perspectives Conclusion and perspectives Conclusion: The crucial property is the continuity in the f-divergence’s second argument. This yields continuity of f-projections. This leads to the continuous dependence of the limit matrix of the IPF sequence on the initial matrix. C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 25 / 25 Conclusion and perspectives Conclusion and perspectives Conclusion: The crucial property is the continuity in the f-divergence’s second argument. This yields continuity of f-projections. This leads to the continuous dependence of the limit matrix of the IPF sequence on the initial matrix. Perspectives: Continuous dependence when varying the marginals c and r within the IPF procedure? Continuous dependence when minimizing within the second argument of f-divergence? C. Gietl, F. Reffel (Universit¨at Augsburg) Continuity of f-projections GSI 2013 25 / 25