2
$\begingroup$

I created a certain algorithm and now I try to prove it's convergence. Here is the essence of the algorithm:

Given are finite sets $A_i$, positive constants $\alpha_a$, and a sequence $ \vec{\delta}^{(k)} \in \mathbb{R}^n$: $$ A_1,\; \ldots,\; A_n \subset \mathcal{A} $$ $$ B_a = \{i : a \in A_i\}$$ $$ \sum_{a\in \mathcal{A}}\alpha_a = n, \quad 0 < \alpha_a < |B_a| $$ $$\delta_i^{(0)} = 1 \quad i = 1,2,\; \ldots, \;n$$ $$ \beta_a^{(k)} = \sum_{i \in B_a} \delta_i^{(k)} $$ $$ \delta_i^{(k+1)} = \left(\sum_{a\in A_i} \frac{\alpha_a}{\beta_a^{(k)}}\right)^{-1} $$ Prove that $\vec{\delta}^{(k)}$ converges.

I did some numerical experiments but I am not sure that the bounds on $\alpha_a$ are sufficient. You can make stronger assumptions if you want. I'm just lookgin for an idea how to prove this.

Edit: This may help: in experiments this function is always increases: $$ \sum_{a \in A} \alpha_a \log\frac{\alpha_a}{\beta_a} - \sum^n_{i=1} \log \sum_{a\in A_i} \frac{\alpha_a}{\beta_a}$$

Edit 2: You can assume $|A_i| \geq 2 $

  • 1
    Is the third line a condition you impose on the constants $\alpha_a$ ?2011-02-17
  • 0
    I suppose the $\alpha_a$ can be positive reals? Otherwise, if you pick singletons for all the sets in $\mathcal{A}$, the third line implies that no integer $\alpha_a$ can satisfy the inequalities. I'm trying to figure out what this all means and I can't see why you would need such a contrived sequence. Some background would definitely help!2011-02-17
  • 0
    Looking at the final line, I can see a problem. Suppose $a \notin A_i$, then the sum is empty and $\delta_i^{(k+1)}$ is infinite.2011-02-17
  • 0
    @Raskolnikov: $a$ is the summation variable, it's not free. The sum is only empty if $A_i$ is empty; I presume it was a tacit assumption that the $A_i$ are non-empty.2011-02-17
  • 0
    @joriki: You're right, I overlooked that.2011-02-17
  • 0
    The third like is a condition I know to be true, yes.2011-02-17
  • 1
    BTW, I agree with Raskolnikov that some background would definitely help. I pointed out some of the structure of the problem in my attempt at an answer, but since you came up with all this, and from what your doing with the logarithms, I would expect that you could tell us a bit more about what it all means?2011-02-17
  • 0
    The thing with the logarithms looks to me like the result of some convexity property for entropies.2011-02-17
  • 0
    It is a modified version of of Expectation-MAximization or as you prefer Minorization-Maximization algorithm. I designed it to maximize the functions given in the Edit but I'm not sure if it is dooing the right job.2011-02-17

1 Answers 1

1

It's not quite clear what you mean by "$\vec{\delta}^{(k)}$ converges to a unique point", since you've specified initial values, so if $\vec{\delta}^{(k)}$ converges this will by definition be to a unique point. I assume that you mean that it converges to a point which is independent of the initial values? If so, that is not the case, since multiplying the initial values by a constant factor results in the entire sequence being multiplied by a constant factor, so the limit could only be "unique" in the above sense up to a constant factor.

It seems that a useful way to approach these equations is to eliminate $\beta_a^{(k)}$ by substituting it from the upper iteration step into the lower iteration step, and then bringing the reciprocal on the right-hand side over to the left-hand side, yielding

$$\sum_{a\in A_i} \frac{\alpha_a \delta_i^{(k+1)}}{\sum_{j\in B_a} \delta_j^{(k)}} = 1\;.$$

If we drop the superscripts labeling the iterations steps, we get the equation that determines the fix point(s). Note a) that the sum of these equations over all $i$ is automatically satisfied, and b) all $n$ equations would be satisfied if $\sum_{j\in B_a} \delta_j$ were independent of $a$. So the iteration can be viewed as solving the problem of choosing weights $\delta_i$ for the sets such that for each point $a$ the sum over the weights of the sets in which it is contained is the same. This also makes sense of the fact that a constant factor in the weights is irrelevant.

  • 0
    I updated the quesion. The problem is to show that the sequence does not diverge to infinity.2011-02-17
  • 0
    @Łukasz Lew: That's not what you wrote in the updated question. It says there whether $\delta$ converges. It can either converge, diverge to infinity, or diverge without going to infinity.2011-02-17
  • 0
    Indeed. I want it to converge. I hope it converges.2011-02-17