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?

Improve this question
$\endgroup$
5
  • $\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, 2012 at 3:58
  • $\begingroup$ EM stands for Expectation Maximization $\endgroup$
    – hearse
    Aug 22, 2012 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, 2012 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, 2012 at 6:36
  • $\begingroup$ in the title $\endgroup$
    – David Ketcheson
    Aug 22, 2012 at 12:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2012 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, 2012 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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