3
$\begingroup$

Let $A$ denote a symmetric matrix of non-negative entries, whose rows (and columns) sum up to the all-positive vector $d := A\mathbf{1}$ with $\mathbf{1}$ the all-one-vector. Denote $D := diag(d)$ by a capital letter, similar for any other vector. Let $b$ denote any all-positive vector.

Assume there exists a positive diagonal matrix $S$ such that $A^*:=SAS$ provides $b$ as its row (and column) sums, that is $A^*\mathbf{1} = b$.

It is well-known that iterated proportional fitting provides a sequence $(A=:\tilde A_{(0)}, \tilde A_{(1)}, \tilde A_{(2)}, \ldots)$ that converges to $A^*$. It alternately scales rows appropriately, then columns, then rows, and so forth. This implies that no $\tilde A_{(k)}$ for $k>0$ is symmetric.

However, I am interested in the following symmetrization:

  1. Set $A_{(0)} := A$ and $k:=0$
  2. Set $d_{(k)} := A_{(k)} \mathbf{1}$
  3. Set $A_{(k+1)} := B^{1/2}D_{(k)}^{-1/2} \cdot A_{(k)} \cdot D_{(k)}^{-1/2}B^{1/2}$
  4. Increase $k \gets k+1$ and continue at Step 2

This provides a sequence of symmetric matrices $(A=:\tilde A_{(0)}, \tilde A_{(1)}, \tilde A_{(2)}, \ldots)$. It is known that it converges to $A^*$ in the case that $b = \mathbf{1}$, thus, if the limit is doubly stochastic.

But does this also hold for $b \ne \mathbf{1}$?

I strongly believe this, but I cannot find any results on this, and the proof of the case $b = \mathbf{1}$ seems not to generalize.

| cite | improve this question | | | | |
$\endgroup$
0
$\begingroup$

Now, one year later, I found a recent publication by S. Kurras that answers my above question in all aspects. See here for the paper plus its supplement: Proceedings of AISTATS 2015

Indeed he proves that SIPF converges to the same limit as IPF, for any all-positive vector $b$.

This further implies that the limit matrix $A^*$ is precisely the Bregman projection of $A$ onto the set $\mathcal{S}(b,A)$ defined by all symmetric non-negative matrices of row/column sums $b$, where the projection is with respect to relative entropy error (generalized Kullback-Leibler divergence) $$D(X\|Y) := \sum_{i,j} x_{ij} \log(x_{ij}/y_{ij}) - x_{ij} + y_{ij}.$$

Thus, it holds that both SIPF and IPF iteratively approximate the following optimum/projection:

$$A^* \ = \ \text{arg}\,\text{min}_{X \in S(b,A)} \ D(X\|A)$$

(whenever existing, i.e., whenever $\mathcal{S}(b,A) \ne \emptyset$).

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.