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