Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For $i=1, \dots, n$ ($n$ could be large) we have variables $x_i$ and $y_i$ relating to probability bounds s.t. $x_i, y_i \geq 0, x_i+y_i \leq 1 \; \forall i$. Each $i$ has a constant $\theta_i$, and some of the pairs $(i,j)$ have a nonzero constant $w_{ij}$ (weight of interaction, positive or negative) in which case say $j \in N(i)$.

Let $W_i=\sum_{j \in N(i): w_{ij}>0} w_{ij}$ (sum of positive edges), $V_i=-\sum_{j \in N(i): w_{ij}<0} w_{ij}$ (minus sum of negative edges), $\alpha_{ij} =\exp (|W_{ij}|) -1$.

We initialize all $x_i, y_i =0$ then iteratively update as shown below via intermediate variables $\{L_i,U_i\}$. All iterations are monotonically nondecreasing, $x_i, y_i$ are bounded above hence converge, empirically typically rapidly.

Can we prove something on the rate of convergence? (any pointers appreciated)

The problem may be easier if we restrict all $w_{ij}>0$, which would still be very helpful, in which case $V_i=0$ and just rewriting the pseudocode below, each iteration sets e.g. new $x_i \leftarrow \left(1 + \frac{\exp(-\theta_i)}{\prod_{j \in N(i)} \left(1 + \frac{\alpha_ij x_j}{1+\alpha_{ij}(1-y_i)(1-x_j)} \right) } \right)^{-1}$.

REPEAT until convergence {
  FOR each i {
    Li, Ui=1 // Initialize this pass
    FOR each j \in N(i) {
      IF w_{ij}>0 {
        Li *= 1+ \frac{\alpha_{ij} x_j} {1+\alpha_{ij} (1-y_i) (1-x_j)}
        Ui *= 1+ \frac{\alpha_{ij} y_j} {1+\alpha_{ij} (1-x_i) (1-y_j)}  }
      ELSE {
        Li *= 1+ \frac{\alpha_{ij} y_j} {1+\alpha_{ij} (1-y_i) (1-y_j)}
        Ui *= 1+ \frac{\alpha_{ij} x_j} {1+\alpha_{ij} (1-x_i) (1-x_j)}  }
    }
  x_i = 1 / (1+exp(-\theta_i + V_i)/Li)
  y_i = 1 / (1+exp(\theta_i + W_i)/Ui)
}
share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.