2
$\begingroup$

I have an iterative sequence for optimizing an EM (Expectation Maximization) algorithm based loss function $L(X)$ with $t$ being the iteration number as: $X_t=ABX_{t-1}+CX_{t-1}+X_{t-1}$ where $A$ is a diagonal matrix, $B$ and $C$ are positive semi-definite matrices. Also the diagonal entries in $A$ are the inverse of the diagonal elements of $C$. i.e, $A=Diag^{-1}(C)$.

I would like to compute the convergence rate (root-convergence rate) of this algorithm as $t\to \infty$. Am assuming it has got to do with taylor expansions, spectral radii and fixed point theorems. How is this approached or done for iterative schemes?

$\endgroup$
  • $\begingroup$ You may get more answers if you state what EM and MM stand for and what problem they're used to solve, in the question title. $\endgroup$ – David Ketcheson Aug 22 '12 at 3:58
  • $\begingroup$ EM stands for Expectation Maximization $\endgroup$ – hearse Aug 22 '12 at 4:09
  • $\begingroup$ What is this scheme supposed to converge to as $t \rightarrow \infty$? Some sort of equilibrium/steady state? $\endgroup$ – Geoff Oxberry Aug 22 '12 at 5:31
  • $\begingroup$ Yes a steady state where $||X_t-X_{t-1}||$ tends to a small value $\epsilon$ or even to zero as $t \to \infty$ where in a local/global minimum is reached. $\endgroup$ – hearse Aug 22 '12 at 6:36
  • $\begingroup$ in the title $\endgroup$ – David Ketcheson Aug 22 '12 at 12:19
2
$\begingroup$

This is just a linear fixed-point iteration

$$ X_t = M X_{t-1}$$

where

$$\DeclareMathOperator{\diag}{diag} M = AB + C + I = (\diag C)^{-1} B + C + I .$$

The convergence rate of this iteration is linear with worst-case convergence factor equal to the spectral radius of $M$ (therefore, if $\rho(M) > 1$, the method does not converge). Furthermore, if $\rho(M) = 1$ and has any eigenvalues of magnitude 1 that are not exactly 1, the iteration also does not converge. Clearly, if $B$ and $C$ can vary independently, the iteration is not generally convergent. Note that if $\rho(M) < 1$, it always converges to 0.

$\endgroup$
  • $\begingroup$ What do you mean by 'eigenvalues of magnitude 1 that are not exactly 1'? Also, if 4(B+C) is the gradient of the loss, would it change the inferences on the convergence? Thanks. $\endgroup$ – hearse Aug 22 '12 at 12:34
  • $\begingroup$ $\lambda = -1$ or $\lambda = i$ are examples with magnitude $1$ that are not equal to $1$. The physical interpretation of the matrices does not change the math. Is the iteration supposed to converge to $0$? If not, perhaps you wrote down the method incorrectly. $\endgroup$ – Jed Brown Aug 22 '12 at 14:17

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.